FCRC 2011. Part 2 of... probably 2.

(A workshop on Coding, Complexity and Sparsity will be held at Ann Arbor, August 1-4, 2011. See this website.)

More thoughts on FCRC.

1. Russell Impagliazzo is one of the Luddites (spellcheck made me use a capital L) in the field (I'm another, and I know of one more person in Complexity who could be called a Luddite) who famously uses transparencies at talks. BUT, he has entered the 1990's- he gave a talk on PowerPoint (or something like it). (Spellcheck made me use two capital P's). I asked him why he made the change. The ability to SCAN IN his old transparencies was one of the keys. (Of course, he probably could have done that 10 years ago...) The talk was on his world view. I don't mean how he feels about the debt ceiling or Libya or Global Warm ning or the problems in FILL IN ANY COUNTRY THAT HAS PROBLEMS. I mean his worlds:
   1. Algorithmica: P=NP
   2. Algorithmica: NP ⊆ BQP. This was in a talk he gave at a workshop. Its in a link below but was not in his CCC talk.
   3. Heristica: P ≠ NP but NP problems are tractable on average for any samplable distribution.
   4. Pessiland: There are NP problems hard an average AND there are no one-way functions.
   5. Minicrypt: P ≠ NP, one-way functions exist, but public key crypt is impossible.
   6. Cryptomania: P ≠ NP, public key crypto is possible.
   For the CONTENT of his talk see Lance's blog entry. Blogs on his world are here and here. There was a workshop in 2009 on the worlds. You can actually see Russell talk about it, with transparencies, as a link from this page Russell's paper on the worlds was hard for me to find since its title is A personal view of Average Case Complexity which you can find on his web page. A POLL on which of Russell's works we live in would be interesting, but I leave that for someone else to do.
2. Les Valiant made the cover of CACM! I hope that eases the pain of no longer being the best theorist who had not won a Turing award.
3. Alan Borodin was the only one at STOC who had been to the first STOC (1969). I asked him if, at the time, he thought there would be a STOC 2011. He said that as a grad student at his first conference he thought more of it as being HIS first conference than STOCs first conference.
4. Several of my lunches were with people NOT going to STOC or CCC. A bunch of PLDI grad students asked me what he hot area in Theory was. I told them (1) Quantum is still strong, which surprised me, and (2) Algorithmic Game Theory seems hot now. Any other candidates for a short answer to this question if asked? Be prepared with an answer before the next FCRC.
5. I heard that one of the logistic problems was that different conferences gave out different stuff (bags, pens, paperweights. Paperweights?). I also heard some sniping How come that conference got so much better pens than we got?.
6. Jin Yi Cai gave a great talk at CCC about dichotomy for #CSP. Certain counting problems are in P and other ones are #CSP complete. Cai has managed to classify exactly which are which. I asked him about the CSP problem- is there any hope of a dichotomy theorem there. He said This talk is on Counting CSP. I asked him How Narrow are you?. He challenged me to read a 300 page paper in the field before accusing him of being narrow. Over lunch he gave me a better answer: Counting problems are hard in general so they have to be rather special to be in P, so classifying is doable. By contrast, CSP problems can be easy so its much harder to tell which are which.
7. The only ones at CCC that were at the first CCC were probably Fortnow, Allender, Gasarch, Selman, Homer. The founders of the conference were Book, Hartmanis, Mahaney, Selman, and Young. Selman is the only one who is still doing theory. (Book and Mahaney are deceased, Hartmanis and Young are retired.)
8. I don't bring a laptop to conference (I don't have one); however, I borrowed Marius Zimand laptop to catch up on some websites during one of the breaks. Then a talk came that I wanted to see and I could not pull myself away from the laptop. It can be addictive. I will never do that again. Other distractions such as doing math on paper I can break away from, but web surfing was hard to break away from. What are your experiences with this?