Conference on Computational Complexity

Howdy from the 20^th IEEE Conference on Computational Complexity in San Jose, California. Last night we had a short business meeting with beer and wine but without much controversy. Dieter van Melkebeek was elected to the organizing committee. Next year's conference will be held in Prague July 16-20 and in 2007 we will join STOC and many other conferences at the Federated Computing Research Conference (FCRC) June 9-16 in San Diego. During the Program Committee Chair Report, Luca Trevisan made the point that even by theoretical computer science standards, the computational complexity conference has a small female representation. Something to keep in mind.

My favorite talk on the first day came from the best student paper winner, Ryan Williams on Better Time-Space Lower Bounds for SAT and Related Problems though I'm a bit biased since he's improving on some of my earlier work. He shows SAT cannot be solved by a random-access machine using n^c time and n^o(1) space for c slightly larger than the square root of 3 (about 1.732) improving on the previous lower bound of 1.618. He had several clever ideas recursing on the previous techniques. One can hope that by extending these techniques to push the lower bound to any c<2. Above 2 you seem to lose any advantage from doing recursion.

Today Manuel Blum given an invited talk taking "steps towards a mathematical theory of consciousness." More on that and the rest of the conference later.