Monday, December 29, 2014

2014 Complexity Year in Review

Theorem of the year goes to 2-Server PIR with Sub-polynomial Communication by Zeev Dvir and Sivakanth Gopi. In Private Information Retrieval you want to access information copied in multiple databases in a way so that no database knows what question you asked. In 1995 Chor, Kushilevits, Goldreich and Sudan showed how to use n1/3 bits of communication with two databases. Razborov and Yekhanin proved that using current techniques the bound could not be broken.  Dvir and Gopi
developed new techniques to break that barrier using nO(√(log log n/log n)) bits with two databases, less than nδ for any δ. Bill posted more on this result back in August.

And of course lots of other great work on extended formulations, circuits, algorithms, communication complexity and many other topics. We also had another round of favorite theorems for the past decade.

2014 will go down as the year computer science exploded. With a big convergence of machine learning/big data, the connectedness of everything, the sharing economy, automation and the move to mobile, we have a great demand for computer scientists and a great demand from students to become computer scientists or have enough computing education to succeed in whatever job they get. Enrollments are booming, CS departments are hiring and demand far outstrips the supply. A great time for computer science and a challenging one as well.

We say goodbye to G.M. Adelson-VelskyAlberto Bertoni, Ed Blum, Ashok Chandra, Alexey Chervonenkis, Eugene DynkinClarence "Skip" Ellis, Alexander Grothendieck, Ferran Hurtado, Mike Stilman, Ivan Stojmenovic, Berthold VöckingAnn Yasuhara, Microsoft Research-Silicon Valley and The New York Times Chess Column.

Thanks to our contributors Andrew ChildsBrittany Terese Fasy and MohammadTaghi Hajiaghayi.

Looking ahead 2015 brings the centenary of the man we know for balls and distance and the fiftieth anniversary of the paper that brought us the title of this blog. Have a great New Years and remember, in a complex world best to keep it simple.


  1. "The man we know for balls and distance"? Can someone decode for me?

  2. Ball/distance man = Hamming

  3. I completely missed Ashok Chandra's death. Any more details anywhere?

    1. He was battling cancer. There is a memorial page set up at!/TributeWall

  4. Chandra-Furst-Lipton paper Multi-party protocols, STOC 1983
    (1) introduced multi-party comm complexity (I think),
    (2) used them to prove lower bounds on branching programs- the first time Comm Comp was used that way (I think)
    (3) Used multi-dim Van Der Warden's theorem which started my life long fascination with Ramsey Theory (this I know to be true)

  5. To Ars Mathematica's excellent discussion "What Did Grothendieck Do?" I have contributed excerpts from the Grothendieck-era mathematical roadmap The Mathematical Sciences; a Report (1968, National Academy of Sciences pub. #1681).

    Observation  There is a considerable computer-science component in this 1968 assessment. Not every roadmap committee gets it right … this one did!

  6. Hi Lance!!! I like your phrase "in a complex world best to keep it simple". Maybe there are simple solutions for some outstanding problems such as the P versus NP problem, but this seems not possible. However, I would like to share you a short proof that intents to show us that E is different of NE.

    The pdf is here:

    This proof could also indicate that P is different to NP too. I know there are big chances that such simple solution would be a flaw. However, I would like to share you anyway, because sometimes even the flaw solutions might contribute in someway. I hope so! Regards.