- 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
Kushilevitz-Nisan book.
(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 sake? 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.
Computational Complexity and other fun stuff in math and computer science from Lance Fortnow and Bill Gasarch
Tuesday, August 31, 2010
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.
Did they post slides or video?
ReplyDelete@Bill: Thank you.
ReplyDelete@Dave: Probably they will post the videos sometime (a few months?) after the workshop.
This also lead to the following oddity: the day on (say) Quantum had very few quantum people at it (except the speakers)
ReplyDeleteWell, Barriers II was colliding with AQIS 2010 in Tokyo.
YES- they said Video's should be up within a month. Someone from
ReplyDeleteBarriers Organizing comm- please
confirm, deny, or clarify.
They are doing a great service by making the videos of workshops in CCI available on-line. Thanks to the people in CCI, the organizers, and the speakers.
ReplyDeleteTo his credit, Scott Aaronson already has posted his slides from Barriers II.
ReplyDeleteI was hoping that either Scott or Bill would weblog about this research ... but no such luck (so far) ... and that's why I've gently lobbied Scott to have his student Alex Arkhipov do a guest weblog.
Perhaps inviting more students to do more guest weblogs might be a good thing all-round?
"Better for them, better for us, better for everyone," as Capt. James T. Kirk once said it.
Ahahaha
ReplyDelete"another game that is not much fun"
I don't know if I totally agree with the concept of this joke, having taught a course in game theory, but the sentence is hilarious!
My feeling is that our "barriers" lack clear mathematical ground, are too vague or too "concept dependent". But what about the following REAL barrier.
ReplyDeleteFor a boolean matrix A, let t(A) be the smallest number t for which it is possible to write A as a Hadamard (i.e. entry-wise) product of t boolean matrices, the 0-entries in each of which can be covered by at most t all-0 submatrices.
Easy counting shows that nXn matrices A with t(A) at least n^{1/2} exist.
Problem: Exhibit an explicit matrix A with t(A) at least n^c for an arbitrary small constant c>0$.
This would give the first superlinear lower bound for log-depth circuits, a 30 years old open problem in CC.
To provide an alternative perspective:
ReplyDeleteI thought the only full-on surveys were the ones presented by Sanjeev Arora and Paul Beame. The other presentations, while good, felt job-talky (in fact, one presenter said "The next slides are from my job talk," and another presenter said, "My co-author will be on the job market soon. Hire her!") I got a good sense of what the speaker's strengths were as a researcher, and recent results the speaker obtained, but most talks were more a presentation of recent data points (current best-known results from the work of Speaker X) that could later be used to build a larger theory, instead of being attempts to provide an overarching picture of what was really going on.
(Since John Sidles brought up the Aaronson/Drucker work, I'll use that as an example: it is unclear to me where their computation model stands with respect to other models of optical computing, e.g., the work of Damien Woods. I couldn't help wondering if there was some independent rediscovery possible here, as I've seen that before within natural computing, with so many different models running around, and people focused overmuch on their own thing. Aaronson may well be familiar with optical computing background, I don't know, but his talk offered up his work without providing a larger context. This focus on one's own work, without weighting it relative to the work of others in the field, was a common pattern.)
As a result, I thought the strongest talk was Prasad Raghavendra's -- to the point where I'd say that if you're only going to watch one video, that's the one to watch. Raghavendra not only discussed his own recent results, but presented a (still-unfinished) metatheory of CSPs. It was just beautiful.
To compare Barriers I with Barriers II, more of the talks in Barriers I took the form of surveys and analysis of the field. This was, perhaps, because more of the speakers at Barriers I were senior members of the community, while more of the speakers at Barriers II were at or near the postdoc stage. Even so, I thought Barriers II was a better workshop in the following important sense: there was a much clearer sense of progress, and many more approachable open problems. As an example, a common theme was the generalization of algorithms in Euclidean space to other geometric spaces, such as doubling spaces, or spaces of higher genus than the plane. The "barrier question" with such research was to determine whether there *was* a barrier: can the algorithms be generalized if we are just more careful, or is there a fundamental difference between the spaces?
Aaron Sterling says: A common theme was the generalization of algorithms in Euclidean space to other geometric spaces, such as doubling spaces, or spaces of higher genus than the plane.
ReplyDeleteThe overall theme of "geometric generalization" is immensely interesting to engineers ... the results, the proof technologies, and the verification procedures all are of great practical utility.
Aaron, if nobody else is going to post about this as a Barriers II theme, maybe you might consider doing it?
Aaron, if nobody else is going to post about this as a Barriers II theme, maybe you might consider doing it?
ReplyDeleteThank you for the flattering request, but I didn't take enough notes to present the precision I'm sure you want. However... one of the main speakers who dealt with this theme was Jeff Erickson, who blogs very well. Perhaps, if he's reading this, he might oblige?
Check Suresh's Geomblog for a summery by Piotr Indyk.
ReplyDelete