Algorithms and Complexity Seminar

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.

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

Fast 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 Testing
Wednesday, April 24, 2013 - 3:00pm to 4:00pm

Polynomial 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 testable
Wednesday, April 17, 2013 - 4:00pm to 5:00pm

Let 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

Non-separable utilities are as easy as separable ones -- if they are Leontief-free
Thursday, March 21, 2013 - 2:00pm to 3:00pm

Conventional wisdom has it that computing an equilibrium for a market under non-separable utilities is difficult -- even if restricted to the piecewise-linear, concave (PLC) case, for which irrationality sets in and no fast algorithms are known.


Subscribe to Algorithms and Complexity Seminar