Monday, June 30, 2003
Expanders from EpsilonBiased 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 a_{i,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
F^{m} for F the field of 2 elements. Consider the graph G
consisting of 2^{m} vertices labelled with the elements of
F^{m} 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 that
Ag = 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
#
0 comments
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
#
0 comments
Tuesday, June 24, 2003
EpsilonBiased 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 BenSasson 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
coordinatewise 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
nontrivial 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≤p1 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 BenSasson, Sudan,
Vadhan and Wigderson that used εbiased sets to get efficient
lowdegree 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 kwise 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
#
0 comments
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 cofounding companies such as Pixar. So next time you are looking up a
FOCS paper take a look at the hands of a onetime theorist who made a
difference.
2:24 PM
#
0 comments
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
preToronto pre"SAT is NPcomplete" 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
#
0 comments
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
#
0 comments
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 prize
Valiant 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
decisiontheoretic generalization of online 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
#
0 comments
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 ChurchTuring 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
#
0 comments
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 nontheoretical 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
resistit is always tempting to simply open my laptop and connect,
checking email and posting to this weblog.
8:19 AM
#
0 comments
Tuesday, June 10, 2003
The Business Meeting
Posted by Lance
Update (9/3/03): STOC 2004 CFP
Last 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 reportsomeone else does that and will eventually
appear in SIGACT news.
9:14 AM
#
0 comments
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:

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.
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.
The lectures were taped and may show up online someday. I'll let you
know if I find them theredefinitely recommended viewing.
12:44 PM
#
0 comments
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
#
0 comments
Tuesday, June 03, 2003
Foundations of Complexity
Lesson 19: The ImmermanSzelepcsenyi Theorem
Posted by Lance
Previous Lesson
In this lesson we will prove the ImmermanSzelepcsényi Theorem.
Theorem (ImmermanSzelepcsényi):
For reasonable s(n)≥ log n, NSPACE(s(n))=coNSPACE(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 c^{s} for some constant c. Let
t=c^{s}. 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. reject
If M(x) accepts then there is some accepting configuration reachable
from I so there must be less than m nonaccepting 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 m_{i} be the number of
configurations reachable from I in at most i steps. We have
m_{0}=1 and m_{t}=m. We show how to compute
m_{i+1} from m_{i}. Then starting at m_{0} we
compute m_{1} then m_{2} all the way up to
m_{t}=m and then run the algorithm above.
Here is the algorithm to nondeterministically compute m_{i+1}
from m_{i}.
Let m_{i+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<m_{i} halt and reject
Let m_{i+1}=m_{i+1}+b
The test that r<m_{i} 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 m_{i} to get m_{i+1} we can run the whole
algorithm in space O(s).
1:09 PM
#
0 comments