# Algorithms and Complexity Seminar Ruta Mehta: (Essentially) Resolving the Complexity of Constant Rank Bimatrix Games Wednesday, November 6, 2013 - 4:00pm to 5:00pmThe rank of a bimatrix game (A, B) is defined as the rank of (A+B). For zero-sum games, i.e., rank-0, von Neumann (1928) showed that Nash equilibrium are min-max strategies, which is equivalent to the linear programming duality. Property Testing and Communication ComplexityWednesday, September 11, 2013 - 4:00pm to 5:00pmProperty testing, pioneered by Blum, Goldreich, Goldwasser, Luby, Ron, Rubinfeld and Sudan, is the study of extremely fast randomized algorithms for approximate decision making. One algorithm to rule them all: One join query at a time Friday, July 12, 2013 - 4:00pm to 5:00pmWe present a recent algorithm (PODS 2012) that is the first provably optimal (worst-case) algorithm to compute database joins. The Acquaintance Time of a GraphThursday, June 20, 2013 - 11:00am to 12:00pmWe define the following parameter of connected graphs. For a given graph $G = (V,E)$ we place one agent in each vertex $v \in V$. Every pair of agents sharing a common edge are said to be acquainted. Testing Probability Distributions Using Conditional Samples Wednesday, June 12, 2013 - 1:30pm to 2:30pmOne of the most fundamental problem paradigms in statistics is that of inferring some information about an unknown probability distribution D, given access to independent samples drawn from it. More than a decade ago, Batu et al. Approximating Large Frequency Moments with Pick-and-Drop SamplingWednesday, May 22, 2013 - 4:00pm to 5:00pmGiven data stream $D = \{p_1,p_2,...,p_m\}$ of size $m$ of numbers from $\{1,..., n\}$, the frequency of $i$ is defined as $f_i = |\{j: p_j = i\}|$. The $k$-th \emph{frequency moment} of $D$ is defined as \$F_k = IP = PSPACE using error correcting codes Wednesday, May 15, 2013 - 4:00pm to 5:00pmThe IP theorem, which asserts that IP = PSPACE (Lund et. al., and Shamir, in J. ACM 39(4)), is one of the major achievements of complexity theory. The known proofs of the theorem are based on the arithmetization technique, which transforms a quantified Boolean formula into a related polynomial. A Simple, Combinatorial and Nearly-Linear-Time Algorithm for Solving Ax=b When A is Symmetric Diagonally Dominant Wednesday, May 8, 2013 - 4:00pm to 5:00pmFast algorithms for solving linear systems Ax=b when A is symmetric diagonally dominant (SDD) or graph Laplacian have found broad applications across both the theory and practice of computer science, playing a foundational role in scientific computing, machine learning, random processes, image pr Explicit Noether Normalization for Simultaneous Conjugation via Polynomial Identity TestingWednesday, April 24, 2013 - 3:00pm to 4:00pmPolynomial identity testing asks whether a given algebraic circuit C computes the identically zero polynomial. Randomized algorithms are known for this problem, via the Schwartz-Zippel lemma, and in recent years there has been Every locally characterized affine-invariant property is testableWednesday, April 17, 2013 - 4:00pm to 5:00pmLet F = F_p for any fixed prime p >= 2. An affine-invariant property is a property of functions on F^n that is closed under taking affine transformations of the domain. We prove that all affine-invariant property

## Pages 