2008-2009 Seminars

Affine extractors are maps over F^n that are balanced on every affine subspace of large enough dimension. A random map is, with high probability, a good affine extractor. However so far we do not know how to build explicit affine extractors that are...

We prove that NP is different from coNP and coNP is not a subset of MA in the number-on-forehead model of multiparty communication complexity for up to k=(1 - e)log(n) players, where e>0 is any constant. Prior to our work, the problem was open even...

A local graph partitioning algorithm finds a set of vertices with small conductance (i.e. a sparse cut) by adaptively exploring part of a large graph $G$, starting from a specified vertex. For the algorithm to be local, its complexity must be...

Green and Tao used the existence of a dense subset indistinguishable from the primes under certain tests from a certain class to prove the existence of arbitrarily long prime arithmetic progressions. Tao and Ziegler showed some general conditions...

We bound the time it takes for a group of birds to reach steady state in a standard flocking model. We prove that (i) within single exponential time fragmentation ceases and each bird settles on a fixed flying direction; (ii) the flocking network...

Green and Tao used the existence of a dense subset indistinguishable from the primes under certain tests from a certain class to prove the existence of arbitrarily long prime arithmetic progressions. Tao and Ziegler showed some general conditions...

Submodular functions are a key concept in combinatorial optimization. Algorithms that involve submodular functions usually assume that they are given by a (value) oracle. Many interesting problems involving submodular functions can be solved using...