Saturday, June 14, 2003
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
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.
Friday, June 13, 2003
Thoughts on FCRC
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.
Tuesday, June 10, 2003
The Business Meeting
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
- Awards: Godel Prize for best paper published in a journal in last
seven years: Yoav Freund and Rob Schapire for their adaboost
Knuth Prize for lifetime research activity: Miklos Ajtai.
STOC Best Paper: Jointly to Impagliazzo and Kabanets for
"Derandomizing Polynomial Identity Tests Means Proving Circuit
(you read it here first) and Oded Regev for
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.
Monday, June 09, 2003
Howdy from San Diego
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
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
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.