I’m writing from the Barriers in Computational Complexity workshop in Princeton, where too many real things are happening for me to blog about nothing. I understand that streaming video of all the talks will be up eventually; for now, a few highlights:
- On Tuesday I hosted a panel discussion on “Barrier Problems in Boolean Complexity.” The panelists were Steve Cook, Avi Wigderson, Russell Impagliazzo, and Sasha Razborov. We got lots of questions from the floor, about everything from whether P≠NP, to whether P vs. NP is independent of set theory, to whether the laws of physics can be understood as computer programs. Alas, there were few to no serious disagreements among the panelists (indeed, you can probably guess their answers to the last three questions).
- I gave a talk entitled Has There Been Progress on the P vs. NP Question? (The link goes to the PowerPoint slides.)
- Ketan Mulmuley spoke about Geometric Complexity Theory (GCT), his approach to P vs. NP and related problems based on algebraic geometry and group representation theory. For months I’ve been planning a blog post about GCT. Spurred on by people at the workshop, I might actually finish it soon. In the meantime, those of you who can’t wait for your daily helping of plethysms, Weyl modules, G-varieties might want to check out Mulmuley’s new complexity-theoretic overview and complementary mathematical overview of GCT.
- Ben Rossman spoke about recent lower bounds in circuit complexity: an ~nk/4 lower bound on the size of AC0 circuits computing the k-clique function, and (a brand-new result) an ~nk/4 lower bound on the size of monotone circuits computing the k-clique function, even on average.
- Ran Raz gave an awesome talk on “How to Fool People to Work on Circuit Lower Bounds.” (Answer: by giving them completely innocuous-looking mathematical problems, without telling them that the answers would imply breakthroughs in complexity theory. Alas, presumably no one who attended Ran’s talk—or for that matter who’s reading this entry—can be fooled, since we’re in on the secret.) In particular, Ran spoke about his STOC’08 paper on elusive functions, as well as some brand-new work on how lower-bounding the rank of explicit tensors would lead to circuit and formula size lower bounds.
Meanwhile, Lance has a superb survey article in Communications of the ACM about the status of the P vs. NP problem.
(An earlier version of this post discussed a preprint by Gus Gutoski on quantum multi-prover interactive proof systems. That preprint has since been retracted.)
And now I bid adieu, as the next talk is starting and my laptop is running out of batteries.