2012-2013 Seminars

For all practical purposes, the Micali-Vazirani algorithm, discovered in 1980, is still the most efficient known maximum matching algorithm (for very dense graphs, slight asymptotic improvement can be obtained using fast matrix multiplication)...

In this talk we will discuss information complexity -- a measure of the amount of information Alice and Bob need to exchange to solve a problem over distributed inputs. We will present an information-theoretically optimal protocol for computing the...

Some important mechanisms considered in game theory require solving optimization problems that are computationally hard. Solving these problems approximately may not help, as it may change the players’ rational behavior in the original mechanisms...

Polynomial Identity Testing (PIT) is the problem of identifying whether a given algebraic circuit computes the identically zero polynomial. It is well-known that this problem can be solved with small error probability by testing whether the circuit...

Many problems from complexity theory can be phrased in terms of tensors. I will begin by reviewing basic properties of tensors and discussing several measures of the complexity of a tensor. I'll then focus on the complexity of matrix multiplication...

Holant Problems are a broad framework to describe counting problems. The framework generalizes counting Constraint Satisfaction Problems and partition functions of Graph Homomorphisms. We prove a complexity dichotomy theorem for Holant problems over...

I present some of the very fundamental notions in game theory, with emphasis on their role in the theory of mechanism design and implementation. Examples include (1) normal-form games: Nash equilibrium and full implementation, dominant strategy...