Computational Complexity

Tuesday, July 06, 2004

 
Gems of Additive Number Theory

Posted by Lance

Yesterday Avi Wigderson gave a talk entitled Gems of Additive/Combinatorial Number Theory where he presented three interesting results about the sizes of sets when you add all the possible numbers from one set with another.

Let A and B be subsets of an Abelian group G and define A+B = {a+b | a in A and B in B}. We define AxB as the same with multiplication when we work over a field. Let |A|=|B|=m.

1. Erdös-Szemerédi: Let A be a subset of the reals. Either |A+A|≥m^5/4 or |AxA|≥m^5/4.
2. Ruzsa: For all k, if |A+B|≤km then |A+A|≤k²m.
3. Gowers: Let E be a set of pairs (a,b) with a in A and b in B. Let A+_EB be the set of values a+b with (a,b) in E. For any δ and k, if |E|≥δm² and |A+_EB|≤km then there is an A'⊆A and B'⊆B with |A'|,|B'|≥δ²m and |A'+B'|≤mk³/δ⁵.

Later Russell Impagliazzo showed how to use finite field versions of these results in his upcoming FOCS paper with Barak and Wigderson. They show how to convert poly(1/δ) independent sources of distributions with δn min entropy to n nearly uniform random bits.

7:42 AM # 0 comments

Comment Feeds: This Post All