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. 