The sum-product theorem and its applications

Abstract: How "orthogonal" are the basic field operations "+" and "x"? About two years ago Bourgain, Katz and Tao proved the following theorem (stated very informally). 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. In paricular, prime fields have no such subsets! 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 Randomness Extractors and Ramsey Graphs. In this 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.

Speaker's Bio: Avi Wigderson received his BSc degree from the Technion in 1980 and his PhD degree from Princeton University in 1983, both in Computer Science. From 1986 to 2003 he was on the faculty of the Computer Science Institute at the Hebrew University. Since 1999 he is a Professor in the School of Mathematics at the Institute for Advanced Study in Princeton. He has held visiting positions at the University of California in Berkeley, IBM Research in San Jose, the Mathematical Sciences Research Institute in Berkeley, and Princeton University.

His research interests are complexity theory, algorithms, randomness and cryptography. He is the recipient of the 1994 Nevanlinna Prize presented at the International Congress of Mathematicians.