2006-2007 seminars

We uncover the structure of those languages that have bounded (by a constant) k-party communication complexity in the input on the forehead model, no matter how we partition the input bits into k disjoint sets. This generalizes an earlier result of...

In this talk, I shall present the first randomized polynomial-time simplex algorithm for linear programming. Like the other known polynomial-time algorithms for linear programming, its running time depends polynomially on the number of bits used to...

While a continuation of last week's lecture, I'll try to make it self contained. I will describe some of the ideas and tools used in the proof of the Sum-Product theorem. I will describe a statistical version, and its use in extractor construction.

Consider the minimum cost spanning tree problem under the restriction that all degrees must be at most a given value $k$. The main result I will present is that one can efficiently find a spanning tree of maximum degree at most $k+2$ whose cost is...

About two years ago Bourgain, Katz and Tao proved that in every finite field, a set which does not grow "much" when we add all pairs of elements, and when we multiply all pairs of elements, must be very "close" to a subfield. This theorem revealed...