Computer Science/Discrete Mathematics Seminar II

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 its fundamental nature quickly. Shortly afterwards it has found many diverse applications, including in Number Theory, Group Theory, Combinatorial Geometry, and the explicit construction of Extractors and Ramsey graphs. In my talk I plan to explain some of the applications, as well as to sketch the main ideas of the proof of the sum-product theorem. Time permitting, I will also describe some important explicit construction problems which I hope progress can be made on.