ε-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 F

^{m}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 F

^{m}map to 1 and the others to -1. If one picks a reasonably large subset S of F^{m}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Σ 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/ε._{x∈S}g(x) ≤ ε|S|.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 F

^{m}to the complex pth roots of unity, e^{2π(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