### Wednesday, June 25, 2003

**SIGACT**

The June 2003 SIGACT
News is out. Aduri Pavan wrote this months Complexity Theory
Column on "Comparison of Reductions and Completeness
Notions".
As I have mentioned before in this weblog, I heartily encourage
joining SIGACT, the ACM Special
Interest Group on Algorithms and Computation Theory. You get the
SIGACT News, discounts on conferences and as I discovered last night
from home, you apparently get online access to the STOC
proceedings. Not to mention supporting the theory community. All this
for the low price of $18 ($9 for students).

What about the ACM itself? I have
been an ACM member since graduate school since I feel it is important
to support the main computer science organization. But for the
additional $96 ($42 for students) there are no real significant
benefits over joining SIGACT alone.

4:29 PM
#
Comments
[]

### Tuesday, June 24, 2003

**Epsilon-Biased Sets**

ε-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_{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|.
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 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.
*

3:05 PM
#
Comments
[]

### Monday, June 23, 2003

**Whose hands are on the FOCS cover?**

Sometimes
I learn interesting aspects of the history of theory from this
weblog. On an
old post on conference covers, Pekka
Orponen left a comment saying that Alvy Ray Smith originally designed
the FOCS cover back in 1973, when the conference was SWAT: Switching
and Automata Theory. Here is Smith's story about the
cover where he states the hands are his.
Smith had three papers in SWAT before moving into computer graphics
and co-founding companies such as Pixar. So next time you are looking up a
FOCS paper take a look at the hands of a one-time theorist who made a
difference.

2:24 PM
#
Comments
[]