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