[Computational Complexity] Report from Barriers II Part 1
- On Thursday Aug 26 Lance stated Bill is at Barriers II in Princeton and promises a full report upon his return. Not quite sure I promised that, or what a full report would entail, but here goes.
- When I first heard there would be a BARRIERS II workshop I assumed it would be full of Oracle results, Natural Proofs, Algebrazation, maybe some speculation on independence results (I do not think we have any right now). And indeed, this was at least part of the agenda for Barriers I. (See here for a blog about Barriers I.) Barriers II was (1) Approx algorithms and lower bounds, (2) Crypto, (3) Quantum Computing, (4) Communication Complexity, (5) Geometric Algorithms (NOTE- NOT Ketan's Geometric Complexity Theory program). However I can't say it was false advertising since the program was on the web early enough that one could see what one was getting into. It was misnamed.
- The organizers told me that it was called Barriers because the speakers were urged to talk about where the field is and where it is stuck. I think talks like that have a name already: Open Problems, or Directions or whatnot.
- All of that aside, how was it? It was WONDERFUL!. The talks were uniformly good. They were mostly survey-talks so one outside the field could follow them (that was the intent). This also lead to the following oddity: the day on (say) Quantum had very few quantum people at it (except the speakers) since your standard quantum person has probably heard the talks before or at least knows the material.
- Approx Alg and lower bounds: I was inspired to actually learn what Semi Definite Programming and Iterative Methods are. I finally understand the UGC and its different formulations. Dana Moshkovitz gave a nice rump session about a promising route to PROVE UGC. This was not one of those we doubt it will work but the approach is still interesting talks (this could be a rallying cry for our field) but seemed like a real plan.
- Crypto: Lattice stuff and also stuff about: If your key leaks slowly can you still do crypto? (yes).
- Quantum: Scott introduced the speakers and was the first one. He had a slide warning us to NOT PANIC at the mention of Quantum. All of the talks were outreach--- why complexity theorists should learn quantum methods. I blogged about this non-technically here. One key point I will re-iterate: Even if you don't work in quantum computing you will need to learn their methods. (Analog: even if you don't work in prob you need to know the prob method.) Over dinner we noted the following: there are many quantum books for the layperson but there are few (none?) complexity books for the layperson (hurry up Lance!). Why is this? Quantum seems less abstract then Complexity and some laypeople may thinks they have a notion of it. They may be wrong.
Communication Complexity: Paul Beame gave an hour long talk where he
went over the entire
(NOTE: This book is on Lance's list of
favorite Computational Complexity Books.)
How did he do it? He skipped some stuff.
(I recommended talking fast. Fortunately he didn't take my advice.)
The other talks were applications of Communication Complexity to lower bounds
on data structures (not quite- some of the lower bounds didn't use Comm. Comp.),
data streams, direct sum problems, and a talk on quantum comm. comp.
This raises the question: Is Communication Complexity only interesting
when it applies to something else, or it is interesting for its own
I proposed the following open problem in a rump session, though it
seems like its already out there (that is, its not really MY open problem).
Alice has x, Bob has y, both are n-bits long. We are promised that PARITY(x)=0 and PARITY(y)=1. Alice and Bob want to find i such that xi ≠ yi with d rounds (d a constant) and O(log n) bits-per-round. Show they cannot do this. ANSWER: We already know this statement is true since it is equivalent to PARITY ∉ AC0. (Using Karchmer-Wigderson games, another game that is not much fun.) However, I would like a communication complexity proof of this which would give an alternative proof of PARITY ∉ AC0. In particular it would give a top-down proof instead of a bottom-up proof.
- Geometric Algorithms. Paul Beame said that this session would be a nice counterpoint to the communication complexity talks since the Geometric Algorithms session would prove some upper bounds on problems that the Comm. Comp. Session proved lower bounds on. (Mike Sipser once told me It is good to do an algorithm as a sanity check on your lower bounds.). Alas I had to take off that morning so I don't know if this really happened; however, I assume that it did.
- Not much talk about the alleged P NE NP proof; however, I will discuss what was discussed in my next blog.
Posted By GASARCH to Computational Complexity at 8/31/2010 08:33:00 AM