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 NearlyLinearTime 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 

Every locally characterized affineinvariant property is testable Wednesday, April 17, 2013  4:00pm to 5:00pm Let F = F_p for any fixed prime p >= 2. An affineinvariant property is a 

Nonseparable utilities are as easy as separable ones  if they are Leontieffree Thursday, March 21, 2013  2:00pm to 3:00pm Conventional wisdom has it that computing an equilibrium for a market under nonseparable utilities is difficult  even if restricted to the piecewiselinear, concave (PLC) case, for which irrationality sets in and no fast algorithms are known. 