This work is licensed under a
Creative Commons License.
|
Monday, June 30, 2003
Expanders from Epsilon-Biased Sets
Posted by Lance
Expander graphs informally are graphs that given any subset S that is not too large, the set of vertices connected to S contains a large number of vertices outside of S. There are many constructions and applications for expander graphs leading to entire courses on the subject.The adjacency matrix A of a graph G of n vertices is an n×n matrix such that ai,j is 1 if there is an edge between vertices i and j and 0 otherwise. Noga Alon noticed that a graph that has a large gap between the first and second eigenvalue of the adjacency matrix will be a good expander.
We can use ε-biased sets to get expanders. Let S be a ε-biased set for Fm for F the field of 2 elements. Consider the graph G consisting of 2m vertices labelled with the elements of Fm and an edge from x to y if y=x+s or x=y+s. This kind of graph G is known as a Cayley graph.
By looking at the eigenvalues the adjacency matrix A of G we can show G is an expander. The eigenvectors v are just the vectors corresponding to the functions g in L described earlier. For any vector a we have
(Ag)(a) = Σs in S g(a+s) = g(a) Σs in S g(s) since g(a+s) = g(a)g(s). Let g(S) = Σs in S g(s). We now have thatAg = g(S) g. So g is an eigenvector with eigenvalue g(S). If g is the constant one function then g(S)=|S|. Since S is an ε-biased set, g(S)≤ε|S| for every other g, so the second eigenvalue is much smaller than the largest eigenvalue and G must be an expander.3:16 PM #
Wednesday, June 25, 2003
SIGACT
Posted by Lance
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 #
Tuesday, June 24, 2003
Epsilon-Biased Sets
Posted by Lance
ε-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 #
Monday, June 23, 2003
Whose hands are on the FOCS cover?
Posted by Lance
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 #
Wednesday, June 18, 2003
Walter Savitch
Posted by Lance
After the FCRC meetings I attended were concluded, I headed up to UCSD for the celebration of Walter Savitch for his sixtieth birthday and upcoming retirement. He gained his fame in complexity for Savitch's Theorem that shows "P=NP" for space.I learned quite a bit at the meeting. Walt Savitch was Steve Cook's first student, his only student while Cook was at Berkeley in his pre-Toronto pre-"SAT is NP-complete" days. Also as Cook said, Savitch is the only student he has had with a theorem named after him. That theorem made up a good part of Savitch's Ph.D. thesis. At the celebration Cook gave an overview on propositional proof systems.
After coming to UCSD, Savitch did some work on computational linguistics and one of the leaders of the field, Aravind Joshi, gave a talk on combining trees to keep the structure when parsing sentences.
Savitch is probably best known now in computer science for his textbooks in introductory programming that likley many of you have used.
Congrats Walt on a fine career and here's hoping retirement doesn't slow you down.
7:16 AM #
Tuesday, June 17, 2003
FOCS 2003
Posted by Lance
The list of accepted papers for FOCS 2003 has been posted. As usual, many (but not all) of the papers are available on the authors' web sites.9:34 AM #
Monday, June 16, 2003
Boosting
Posted by Lance
As promised I added links to the papers in the post on the STOC business meeting. Let me say some more words on the winner of the Gödel prizeValiant developed the concept of PAC (Probably Approximably Correct) learning as roughly where a learner sees a small number of labelled examples from a distribution and with high confidence will generate a hypothesis that with high probability will correctly label instances drawn from the same distribution.
A strong learner has confidence close to 100%; a weak learner has confidence only slightly better than 50%. Schapire, using a technique called boosting, showed how to convert a weak learner to a strong learner. This is a wonderful theoretical result but the algorithm had problems that made it difficult to implement.
In their Gödel prize winning paper, A decision-theoretic generalization of on-line learning and an application to boosting, Freund and Schapire develop the adaboost algorithm that solves many of these issues and has become a staple of the theoretical and practical machine learning community.
Boosting has its own web site where you can find much more information about the algorithms and applications.
10:31 AM #
Saturday, June 14, 2003
Alonzo Church
Posted by Lance
Alonzo Church was born a hundred years ago today in Washington, DC. Church is best known for the λ-calculus, a simple method for expressing and applying functions that has the same computational power as Turing machines.With Rosser in 1936, he showed that λ-expressions that reduce to an irreducible normal form have a unique normal form. In that same year he showed the impossibility of decided whether such a normal form existed.
Church's thesis, which he states as a definition: "An effectively calculable function of the positive integers is a λ-definable function of the positive integers."
Again in 1936, Kleene and Church showed that computing normal forms have the equivalent power of the recursive functions of Turing machines. And thus the Church-Turing thesis was born: Everything computable is computable by a Turing machine.
The λ-calculus also set the stage for many of the functional programming languages like lisp and scheme.
Alonzo Church passed away on August 11, 1995 in Ohio.
6:33 AM #
Friday, June 13, 2003
Thoughts on FCRC
Posted by Lance
I have mixed feelings about the Federated Computing Research Conference. It is a good idea to get many different areas of computer science together. I do get to see many people I haven't seen in years who went into non-theoretical areas of CS.On the other hand 2200 participants made the place quite crowded and it seemed to take away from the informal atmosphere of most theory conference. Since STOC and Electronic Commerce had nearly a complete overlap I jumped back and forth between talks never really feeling fully part of either conference.
For the first time the Complexity conference was not part of FCRC because 2003 is a Europe year for Complexity. In an informal poll I took of STOC people interested in complexity most liked having both conferences at the same place but would rather that happen in isolation, like last year in Montreal, rather than as part of the much larger FCRC meeting.
In what seems to be a trend in CS conferences, wireless internet was made available at the conference site. As you walked around you would pass many people sitting on chairs and on the ground hunched over their laptops disconnected from the conference and connected into another world. Seemed a bit depressing but I too found the net hard to resist--it is always tempting to simply open my laptop and connect, checking email and posting to this weblog.
8:19 AM #
Tuesday, June 10, 2003
The Business Meeting
Posted by Lance
Update (9/3/03): STOC 2004 CFPLast night was the business meeting for STOC. This used to be a raucous affair with major battles over issues like whether to have parallel sessions, but now in its old age is more for distributing information like
- Awards: Godel Prize for best paper published in a journal in last seven years: Yoav Freund and Rob Schapire for their adaboost algorithm.
Knuth Prize for lifetime research activity: Miklos Ajtai.
STOC Best Paper: Jointly to Impagliazzo and Kabanets for "Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds" (you read it here first) and Oded Regev for "New Lattice Based Cryptographic Constructions".
The Danny Lewin Best Student Paper Award: Thomas Hayes for "Randomly Coloring Graphs of Girth at Least Five" Thomas Hayes is from my once and future department at U. Chicago.- Future Conferences: FOCS 2003 in Boston, STOC 2004 in Chicago and FOCS 2004 in Rome, its first time outside North America. On Friday, a day after agreeing to return to Chicago, Janos Simon asked me to give the presentation on STOC 2004, which is always fun. Laszlo Babai, another member of the Chicago faculty, will be PC chair of that meeting.
- Registration numbers, NSF report, progress on scanning in old papers and redoing submission software. I'm not going to do a full business meeting report--someone else does that and will eventually appear in SIGACT news.
9:14 AM #
Monday, June 09, 2003
Howdy from San Diego
Posted by Lance
This week I'm at the Federated Computing Research Conference (FCRC), a combination of thirty conferences and workshops with 2200 participants. I'm here for the theory conference (STOC) and Electronic Commerce.Last night, Adleman, Rivest and Shamir gave their Turing award lecture, each giving twenty minutes of an hour long talk. Their basic them on how cryptology has changed in the last 25 years:
Adi Shamir made other interesting comments like that perfect cryptography is impossible, though very good cryptography can be had at a modest cost. Most attacks on practical implementations of cryptographic protocols work on the implementation as opposed to the protocol.
- Cryptography is now done publicly rather than in secret. This has led to researchers building on each others ideas to create better and better encryption schemes and protocols. But also it has allowed more people to attack these protocols and weed out the bad ones.
- Cryptography has moved from art to science. Now we have protocols based on mathematical ideas like number theory instead of just creating seemingly complexity functions.
The lectures were taped and may show up on-line someday. I'll let you know if I find them there--definitely recommended viewing.
12:44 PM #
Friday, June 06, 2003
Back to Chicago
Posted by Lance
A personal note: I have accepted an offer to return to the computer science department of the University of Chicago starting this fall. As NEC Labs has been moving its focus away from basic research, it is time for me to go back to an academic life.I plan to keep this weblog going in Chicago as long as I have things to say.
9:46 AM #
Tuesday, June 03, 2003
Foundations of Complexity
Lesson 19: The Immerman-Szelepcsenyi Theorem
Posted by Lance
Previous LessonIn this lesson we will prove the Immerman-Szelepcsényi Theorem.
Theorem (Immerman-Szelepcsényi): For reasonable s(n)≥ log n, NSPACE(s(n))=co-NSPACE(s(n)).
Let M be a nondeterministic machine using s(n) space. We will create a nondeterministic machine N such that for all inputs x, N(x) accepts if and only if M(x) rejects.
Fix an input x and let s=s(|x|). The total number of configurations of M(x) can be at most cs for some constant c. Let t=cs. We can also bound the running time of M(x) by t because any computation path of length more than t must repeat a configuration and thus could be shortened.
Let I be the initial configuration of M(x). Let m be the number of possible configurations reachable from I on some nondeterministic path. Suppose we knew the value of m. We now show how N(x) can correctly determine that M(x) does not accept.
Let r=0 For all nonaccepting configurations C of M(x) Try to guess a computation path from I to C If found let r=r+1 If r=m then accept o.w. rejectIf M(x) accepts then there is some accepting configuration reachable from I so there must be less than m non-accepting configurations reachable from I so N(x) cannot accept. If M(x) rejects then there is no accepting configurations reachable from I so N(x) on some nondeterministic path will find all m nonaccepting paths and accept. The total space is at most O(s) since we are looking only at one configuration at a time.Of course we cannot assume that we know m. To get m we use an idea called inductive counting. Let mi be the number of configurations reachable from I in at most i steps. We have m0=1 and mt=m. We show how to compute mi+1 from mi. Then starting at m0 we compute m1 then m2 all the way up to mt=m and then run the algorithm above.
Here is the algorithm to nondeterministically compute mi+1 from mi.
Let mi+1=0 For all configurations C Let b=0, r=0 For all configurations D Guess a path from I to D in at most i steps If found Let r=r+1 If D=C or D goes to C in 1 step Let b=1 If r<mi halt and reject Let mi+1=mi+1+bThe test that r<mi guarantees that we have looked at all of the configurations D reachable from I in i steps. If we pass the test each time then we will have correctly computed b to be equal to 1 if C is reachable from I in at most i+1 steps and b equals 0 otherwise.We are only remembering a constant number of configurations and variables so again the space is bounded by O(s). Since we only need to remember mi to get mi+1 we can run the whole algorithm in space O(s).
1:09 PM #
Archives
