Computer Science/Discrete Mathematics Seminar II

The main goal of this talk will be to present a proof of the following theorem. Theorem 1: For every fixed \delta >0 here is a polynomial time (in n = log N) computable function(s) f:[N]x[N]-->{0,1}, for which the following hold. For every two sets A, B of [N], each of size at least K=N^{\delta}, we have f(AxB)={0,1}. If one thinks of f as a 2-coloring of the edges of the complete NxN bipartite graph, then the edges of no KxK subgraph are monochromatic (indeed we'll guarantee that each color will be represented in a constant fraction of all edges). No explicit construction was known for \delta < 1/2. Quite a few other new constructions (interesting in their own right) are needed on the way to construct f itself, and we will describe them too. They include a constant seed condenser, a constant seed 2-source extractor, a deterministic 3-source extractor, among others. Similar techniques allow us to achieve another explicit Ramsey construction: For every \delta we have an explicit 2-coloring of the n-dimensional cube GF(2)^n, such that no affine subspace of dimension (\delta)n is monochromatic. Again, nothing was known for \delta <1/2. If time permits we will sketch what is needed for this result as well. An essential ingredient in all constructions is the recent "multiple source" extractor of Barak, Impagliazzo and Wigderson, which in turn was based on the sum-product theorem for finite fields of Bourgain, Katz and Tao. The talk will be self contained. Joint work with Benny Sudakov, Ronen Shaltiel and Avi Wigderson.