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

[My Computational Complexity Web Log] Epsilon-Biased Sets

Expand Messages
  • Lance Fortnow
    -biased sets are an interesting concept that I have seen recently in a few papers but never seemed to have a clear description. At FCRC Eli Ben-Sasson gave me
    Message 1 of 1 , Jun 24 1:05 PM
    • 0 Attachment
      ε-biased sets are an interesting concept that I have seen recently in a few papers but never seemed to have a clear description. At FCRC Eli Ben-Sasson gave me a good explanation and I will try to recreate it here.

      Let F be the field of 2 elements 0 and 1 with addition and multiplication done modulo 2. Fix a dimension m. Let L be the set of functions g mapping elements of Fm to {-1,1} with the property that g(x+y)=g(x)g(y). Here x+y represents addition done coordinate-wise modulo 2. One example of a g in L is g(x,y,z)=(-1)x(-1)z.

      There is the trivial function g in L that always maps to 1. For every non-trivial g in L exactly half of the elements in Fm map to 1 and the others to -1. If one picks a reasonably large subset S of Fm at random then high probability, g will map about half the elements to 1 and the rest to -1. In other words the expected value of g(x) for x uniformly chosen in S is smaller than some small value ε. If this is true we say S is ε-biased for g.

      An ε-biased set is a set S such that for all nontrivial g in L, S is ε-biased for g. Formally this means that

      Σx∈S g(x) ≤ ε|S|.
      Not only do reasonable size ε-biased sets exists but they can be found efficiently. Naor and Naor found the first efficiently constructible ε-biased sets of size polynomial in m and 1/ε.

      One can extend the notion of ε-biased sets to fields F of p elements for arbitrary prime p. L would now be the set of functions g mapping elements of Fm to the complex pth roots of unity, e2π(j/p)i for 0≤j≤p-1. Various constructions have created generalized ε-biased sets of size polynomial in m, 1/ε and log p.

      For applications let me quote from the recent STOC paper by Ben-Sasson, Sudan, Vadhan and Wigderson that used ε-biased sets to get efficient low-degree tests and smaller probabilistically checkable proofs. You can get more information and references from that paper.

      Since the introduction of explicit ε-biased sets, the set and diversity of applications of these objects grew quickly, establishing their fundamental role in theoretical computer science. The settings where ε-biased sets are used include: the direct derandomization of algorithms such as fast verification of matrix multiplication and communication protocols for equality; the construction of almost k-wise independent random variables, which in turn have many applications; inapproximability results for quadratic equation over GF(2); learning theory; explicit constructions of Ramsey graphs; and elementary constructions of Cayley expanders.

      --
      Posted by Lance Fortnow to My Computational Complexity Web Log at 6/24/2003 01:05:35 PM

      Powered by Blogger Pro

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