Computational Complexity


Creative Commons License
This work is licensed under a Creative Commons License.

Powered by Blogger™

Saturday, June 14, 2003

Alonzo Church

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 # Comments []  

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.

8:19 AM # Comments []  

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 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 # Comments []  

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 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:

  1. 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.
  2. 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 on-line someday. I'll let you know if I find them there--definitely recommended viewing.

12:44 PM # Comments []