Algorithms and Complexity Seminar

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