Algorithms and Complexity Seminar

Siu On Chan: Approximate Constraint Satisfaction Requires Large LP Relaxations
Wednesday, October 16, 2013 - 4:00pm to 5:00pm

We prove super-polynomial lower bounds on the size of linear programming relaxations for approximation versions of constraint satisfaction problems.

Huy L. Nguyen: Cutting corners cheaply, or how to remove Steiner points
Wednesday, October 9, 2013 - 4:00pm to 5:00pm

Our main result is that the Steiner Point Removal (SPR) problem can always be solved with polylogarithmic distortion, which resolves in the affirmative a question posed by Chan, Xia, Konjevod, and Richa (2006).

Private Analysis of Graphs
Wednesday, October 2, 2013 - 4:00pm to 5:00pm

We discuss algorithms for the private analysis of network data. Such algorithms work on data sets that contain sensitive relationship information (for example, romantic ties).

Ruta Mehta: (Essentially) Resolving the Complexity of Constant Rank Bimatrix Games
Wednesday, November 6, 2013 - 4:00pm to 5:00pm

The 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 Complexity
Wednesday, September 11, 2013 - 4:00pm to 5:00pm

Property 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:00pm

We present a recent algorithm (PODS 2012) that is the first provably optimal (worst-case) algorithm to compute database joins.

The Acquaintance Time of a Graph
Thursday, June 20, 2013 - 11:00am to 12:00pm

We 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:30pm

One 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 Sampling
Wednesday, May 22, 2013 - 4:00pm to 5:00pm

Given 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:00pm

The 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.


Subscribe to Algorithms and Complexity Seminar