This work is licensed under a
Creative Commons License.
|
Wednesday, June 25, 2003
SIGACTThe 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 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(x1,x2,x3)=(-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 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 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 Fm to the complex pth roots of unity, e2π(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 []