STOC 2012- workshop and honored talks

I went to an enjoyed STOC this year. Today I talk about the workshops and the papers that either won awards or seem to be in the running. I may blog on other things, or expand on these, at a later point.

1. On Saturday there were two workshops, one on Computational Finance by Mike Kearns and one on the Unique Game Conjecture by Subhash Khot and others (sorry- I don't recall who the other speakers were, though they were quite good- in comments tell me and I'll add it. The program says Arora and Charikar, though they didn't speak. I assume they organized it.) (ADDED LATER- CLARIFICATION AND CORRECTION: There was a Comp Finance TUTORIAL that, when
   it was happening, was the only thing happending, and then later there were FOUR WORKSHOPS going on at the
   same time: Computational Sustainability, Algs for Dist and Streaming Data,
   Algs for Memory-Sensitive Computing, and Unique Game Conjecture.)
   
   1. Computational Finance: A distinguished theorist once told me that he is tired of working on problems nobody cares about so he will now work on Computational Finance. He gave a talk that began A Hedge Fund is a set of Boolean Formulas. By contrast Mike Kearns has actually worked with Lehman brothers (Is that why they were not bailed out? Unlikely.) on REAL questions that arise from Finance. The talk gave the needed background on finance and was excellent. One odd thing: I understood the entire thing. I am not bragging- I suspect that everyone who went did. If I was a snobbish pure math guy I would say Since I understood everything it couldn't have been any good. I of course feel the contrary way- it is WONDERFUL that I understood the whole thing. This is partially because he skipped details which is a good thing to skip. Slides are here.
      
   2. Unique Game Conjecture: For past work on this I can't do any better than Lipton's blog here, Khot's surveys and slides here. Khot's talk were a good review if you already knew the material and a good intro if you didn't. The other talks introduced a possible approach to disproving the conjecture. Very High Level View: There is an algorithm using the eight level of the Lasserre hierarchy of SDPs that MAY disprove the UQC. The usual counterexamples don't work. (I may not be stating this quite right.)
      Note that: (1) The community of people who study UGC seems to NOT have a consensu of whether its true or false.
      And those who think its TRUE or FALSE are not dogmatic. (2) It may be resolved before I do my next Poll. If not then I'll
      ask about it. (3) Even if its false it has lead to results of interest that do not assume it.
      
2. There were poster sessions for graduate students. In some ways these are better than talks since you can interact.
   (ADDED LATER- A commenter helpfully pointed out that the posters were NOT just for graduate students.)
   
3. Kasper Green Larsen won best Student Paper award and co-won Best paper award for The cell Probe Complexity of Dynamic Range Counting
   which proved better lower bounds in the cell probe model. The talk inspired me to read the earlier papers on this material.
   
4. Fiorini, Massar, Pokutta, Tiwary, de Wolf co-won best-paper award for Linear vs Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds. This paper seems to use Quantum Techniques to solve a classical problem.
   
5. Most of the time there were two tracks so there were two talks going on at the same time. There were five exceptions: the best student paper and the two best papers, and in addition three other papers (the numbers work out that way since the best student paper also co-won best paper award). I assume those three are being unofficially acknowledged as runners-up for best paper or some such (I do NOT have inside information). Those three papers were
   
   1. Julia Chozhoy's Routing in undirected graphs with constant congestion.
      
   2. Chan-Kleinberg-Shmoys Improving Christofides algorithm for the s-t path TSP For the METRIC TSP problem the best known upper bounds is STILL 3/2. WOW. There are some lower bounds (see On Approximation Lower Bounds for Tsp with Bounded Metrics for a list of them) but they are pretty weak-- (1+delta)OPT for some small values of delta. (Someone at the conference told me that better was known, like (4/3)OPT, but I have not been able to find it online- if someone can confirm please leave a comment.) This paper is NOT on the TSP, but on s-t-TSP. They give an upper bound of ((1+\sqrt{5})/2)OPT for this problem, breaking the bound of (5/3)OPT. I don't think any lower bounds are known on this problem. (Note that Euclidean TSP can be approximated arb well by the algorithms of Arora and Mitchell.)
      
   3. Virginia Vassilevska Williams Multiplying Matrices Faster Than Coppersmith-Winograd" has been discussed before in in this blog and also in a blog by Lipton. Virginia did not give the talk since she was close to giving birth (I don't know if she has yet). (Prediction: Ryan and Virginia's kid will prove NP is not in ACC₀ by improving the matrix mult bound. Title of the paper: Improving William's Lower Bound by Improving William's Upper Bound by Williams.)