2006-2007 seminars

A Property P of functions is said to be testable if there exists a probabilistic algorithm that makes few (constant) queries for the value of f and accepts those satisfying P while rejecting functions that are far from any function satisfying P. In...

Sipser and Gács, and independently Lautemann, proved in '83 that probabilistic polynomial time is contained in the second level of the polynomial-time hierarchy, i.e. BPP is in \Sigma_2 P. This is essentially the only non-trivial upper bound that we...

Suppose we have n players who wish to jointly perform a quantum computation, but some of them are faulty and are trying to learn privileged information and/or sabotage the computation. How many cheaters can we tolerate and still have a secure...

Polynomial Identity Testing is the following problem: given an arithmetic circuit C, determine if the polynomial computed by it is the identically zero polynomial. This problem admits a randomized polynomial-time algorithm but no efficient...

Let $M$ be an arbitrary $n$ by $n$ matrix. We study the condition number a random perturbation $M+N_n$ of $M$, where $N_n$ is a random matrix, motivated by a problem raised by Spielman and Teng. It is shown that, under very general conditions on $M$...

We describe a short and easy-to-analyze construction of constant-degree expanders. The construction relies on the replacement product, applied by Reingold et. al. [2002] to give an iterative construction of bounded-degree expanders. Here we give a...

Suppose you ran a chess tournament, everybody played everybody, and you wanted to use the results to rank everybody. Unless you were really lucky, the results would not be acyclic, so you could not just sort the players by who beat whom. A natural...

We prove that Cayley graphs of SL_2(Z/qZ) are expanders with respect to the projection of any fixed elements in SL_2(Z) generating a non-elementary subgroup. This expansion property plays crucial role in establishing almost prime version of "SL_2(Z)...

In 1950, Nash showed that every non-cooperative game has an equilibrium. Before his work, the result was known only for two-player zero-sum games. While von Neumann's minimax theorem was the mathematical foundation of the two-player zero-sum game...