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_{1},x_{2},x_{3})=(-1)^{x1} (-1)^{x3}.

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

_{x in 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 again with the property that g(x+y)=g(x)g(y). 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.
*

## No comments:

## Post a Comment