loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
21st Annual IEEE Conference on Computational Complexity (CCC'06)
Prague, Czech Republic
July 16-July 20
ISBN: 0-7695-2596-2
ASCII Text
x 
 
Avi Wigderson, "Applications of the Sum-Product Theorem in Finite Fields," Computational Complexity, Annual IEEE Conference on, pp. 111, 21st Annual IEEE Conference on Computational Complexity (CCC'06), 2006.
 
 
BibTex
x
 
@article{ 10.1109/CCC.2006.9,
author = {Avi Wigderson},
title = {Applications of the Sum-Product Theorem in Finite Fields},
journal ={Computational Complexity, Annual IEEE Conference on},
volume = {0},
year = {2006},
issn = {1093-0159},
pages = {111},
doi = {http://doi.ieeecomputersociety.org/10.1109/CCC.2006.9},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Computational Complexity, Annual IEEE Conference on
TI - Applications of the Sum-Product Theorem in Finite Fields
SN - 1093-0159
SP
EP
A1 - Avi Wigderson,
PY - 2006
KW - null
VL - 0
JA - Computational Complexity, Annual IEEE Conference on
ER -
 
Avi Wigderson, Princeton, USA
About two years ago Bourgain, Katz and Tao [1] proved the following theorem, essentially stating 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, mostly described in the references below.

In my talk I plan to explain some of the applications, as well as to sketch the main ideas of the proof of the sumproduct theorem.

Citation:
Avi Wigderson, "Applications of the Sum-Product Theorem in Finite Fields," ccc, pp.111, 21st Annual IEEE Conference on Computational Complexity (CCC'06), 2006
Usage of this product signifies your acceptance of the Terms of Use.