# Algorithms and Complexity Seminar

 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 Non-separable utilities are as easy as separable ones -- if they are Leontief-free Thursday, March 21, 2013 - 2:00pm to 3:00pmConventional 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.