Loading ...
Sorry, an error occurred while loading the content.

[My Computational Complexity Web Log] Gems of Additive Number Theory

Expand Messages
  • 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
    Message 1 of 1 , Jul 6, 2004
    • 0 Attachment
      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|≥m5/4 or |AxA|≥m5/4.
      2. Ruzsa: For all k, if |A+B|≤km then |A+A|≤k2m.
      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|≥δm2 and |A+EB|≤km then there is an A'⊆A and B'⊆B with |A'|,|B'|≥δ2m and |A'+B'|≤mk35.
      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 max entropy to n nearly uniform random bits.

      --
      Posted by Lance to My Computational Complexity Web Log at 7/6/2004 07:42:41 AM

    Your message has been successfully submitted and would be delivered to recipients shortly.