Theory Seminar: Schedule for Fall 2002

Yan Ding
Date: Friday , Sept 6, 2002
Time: 12:15-1:30 pm
Room: CoC 155

PRIMES is in P

Nikhil Devanur
Date: Friday , Sept 13, 2002
Time: 12:30 pm
Room: CoC 155
Market Equilibrium via Primal Dual Type Algorithm

Although the study of market equilibria has occupied center stage within Mathematical Economics for over a century, polynomial time algorithms for such questions have so far evaded researchers. We provide the first such algorithm for the linear version of a problem defined by Irving Fisher in 1891. Our algorithm is modeled after Kuhn's primal-dual algorithm for bipartite matching.
Amin Saberi
Date: Friday , Sept 27, 2002
Time: 12:15 pm
Room: CoC 155
On the Hardness of Optimal Auctions

We study this problem from a computational perspective and show several lower bounds. In particular, we prove that no deterministic polynomial time ascending auction can achieve an approximation ratio better than 3/4. The probability distribution constructed in our example has sensitive dependencies among the agents. On the flip side, we show that if the dependency between the agents' valuations is bounded, the problem can be approximated with a factor close to 1. It is a joint work with Amir Ronen.
Nisheeth Vishnoi
Date: Friday , Oct 4, 2002
Time: 12pm
Room: CoC 354
Deterministic Identity Testing for Multivariate Polynomials

In this talk we present a simple deterministic algorithm for testing whether a multivariate polynomial f(x_1,...,x_n) is identically zero, in time polynomial in m,n,d and H. Here m is the number of monomials in f, d is the maximum degree of a variable in f and 2^H is the least upper bound on the magnitude of the largest coefficient in f. We assume that f has integer coefficients. The main feature of the algorithm is its conceptual simplicity. The proof uses Linnik's Theorem which is a deep fact about distribution of primes in arithmetic progressions. This is a joint work with Richard Lipton.
Madhu Sudan
Date: Thursday , Oct 10, 2002
Time: 3:30pm
Room: MiRC 102

List Decoding and Complexity Theory

The theory of error-correcting codes has long provided many useful concepts, tools and constructions to theoretical computer science. Over the course of the past fifteen years a new strain of applications, revolving around the notion of ``list-decoding'', have linked the two areas. In this talk, I'll describe some of the connections, and explain why this link is here to stay.
Aranyak Mehta
Date: Friday , Oct 25, 2002
Time: 12:30 pm
Room: CoC 155

Playing Large Games using Simple Strategies

We prove the existence of logarithmic support $\epsilon$-Nash equilibrium strategies - strategies from which each player has only a negligible incentive to defect. This leads to the first quasi-polynomial algorithm for computing such equilibria. We also show that if the payoff matrices of a two person game have low rank then the game has a Nash equilibrium with small support.