Date: Friday , Sept 6, 2002

Time: 12:15-1:30 pm

Room: CoC 155

Date: Friday , Sept 13, 2002

Time: 12:30 pm

Room: CoC 155

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.

Date: Friday , Sept 27, 2002

Time: 12:15 pm

Room: CoC 155

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.

Date: Friday , Oct 4, 2002

Time: 12pm

Room: CoC 354

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.

Date: Thursday , Oct 10, 2002

Time: 3:30pm

Room: MiRC 102

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.

Date: Friday , Oct 25, 2002

Time: 12:30 pm

Room: CoC 155

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.