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 n^1/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 n^{O(√(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-Velsky, Alberto Bertoni, Ed Blum, Ashok Chandra, Alexey Chervonenkis, Eugene Dynkin, Clarence "Skip" Ellis, Alexander Grothendieck, Ferran Hurtado, Mike Stilman, Ivan Stojmenovic, Berthold Vöcking, Ann Yasuhara, Microsoft Research-Silicon Valley and The New York Times Chess Column.

Thanks to our contributors Andrew Childs, Brittany 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.

Undergraduate Research

I just received the Cornell Math Matters, dedicated to the memory of  Eugene Dynkin who passed away on November 14 at the age of 90. In my freshman year at Cornell, Dynkin recruited me into his undergraduate research seminar building on the success he had with a similar seminar he ran when in Russia. I didn't last long, making the conscious choice not to work on research as an undergrad but to focus on enjoying the college experience. I missed out on a great opportunity but I don't regret that decision.

Reluctantly I wouldn't give that advice to today's undergrads. Getting into a good graduate program has become much more competitive and even a small amount of research experience may make a large difference in your application. I encourage any undergrad who may consider a PhD in their future to talk to some professors and get started in a research program. But don't let it run your life, make sure you enjoy your time at college. You'll have plenty of time to spend every waking moment on research once you start graduate school.

The NIPS Experiment

The NIPS (machine learning) conference ran an interesting experiment this year. They had two separate and disjoint program committees with the submissions split between them. 10% (166) of the submissions were given to both committees. If either committee accepted one of those papers it was accepted to NIPS.

According to an analysis by Eric Price, of those 166, about 16 (about 10%) were accepted by both committees, 43 (26%) by exactly one of the committees and 107 (64%) rejected by both committees. Price notes that of the accepted papers, over half (57%) of them would not have been accepted with a different PC. On the flip side 83% of the rejected papers would still be rejected. More details of the experiment here.

No one who has ever served on a program committee should be surprised by these results. Nor is there anything really wrong or bad going on here. A PC will almost always accept the great papers and almost always reject the mediocre ones, but the middle ground are at a similar quality level and personal tastes come into play. There is no objective perfect ordering of the papers and that's why we task a program committee to make those tough choices. The only completely fair committees would either accept all the papers or reject all the papers.

These results can lead to a false sense of self worth. If your paper is accepted you might think you had a great submission, more likely you had a good submission and got lucky. If your paper was rejected, you might think you had a good submission and was unlucky, more likely you had a mediocre paper that would never get in.

In the few days since NIPS announced these results, I've already seen people try to use them not only to trash program committees but for many other subjective decision making. In the end we have to make choices on who to hire, who to promote and who to give grants. We need to make subjective decisions and those done by our peers aren't always consistent but they work much better than the alternatives. Even the machine learning conference doesn't use machine learning to choose which papers to accept.

Joint Center for Quantum Information and Computer Science

(Guest post by Andrew Childs who is now at the Univ of MD at College Park)



We have recently launched a new Joint Center for Quantum Information and Computer Science (QuICS) at the University of Maryland. This center is a partnership
with the National Institute of Standards and Technology, with the support and participation of the Research Directorate of the National Security Agency/Central Security Service. QuICS will foster research on quantum information and computation.

We are pleased to announce opportunities for Hartree Postdoctoral Fellowships
(deadline: December 30, 2014) and Lanczos Graduate Fellowships. Outstanding postdoctoral and graduate researchers with an interest in quantum information processing are encouraged to apply.

QuICS complements a strong program in quantum physics research at the Joint Quantum Institute. Maryland is also home to a new Quantum Engineering Center.
It's an exciting time for quantum information here.

The Ethics of Saving Languages

The linguist John McWhorter wrote an NYT opinion piece entitled Why Save a Language? where he argues why we should care about saving dying languages, basically that language gives us a window into culture. As a computer scientist I appreciate the scientific value of studying languages but perhaps the question is not whether we should care but is it ethical to save languages?

Languages developed on geographical and geopolitical boundaries. Even as new methods of communication came along such as postal mail, the printing press, the telephone and television there never was a strong reason to learn multiple languages save for some small European nations and some professions such as academics and politics.

Then came the Internet and location mattered less but language barriers still persist. I've certainly noticed a marked increase in the number of young people around the world who know basic conversational English, much from the content they consume online. There's also a sizable amount of content in all the major languages.

But if you speak a small language where all the other native speakers are geographically very close to you, you lose this networked connection to the rest of humanity. Your only hope is to learn a second language and that second language might become a first language and so many of these small languages start to disappear.

I understand the desire of linguists and social scientists to want to keep these languages active, but to do so may make it harder for them to take advantage of our networked society. Linguists should study languages but they shouldn't interfere with the natural progression. Every time a language dies, the world gets more connected and that's not a bad thing.

Godel and Knuth Prize Nominations due soon. Which would you rather win? Or ...

(Alg Decision Theory conference in Kentucky: here.)

Knuth Prize Nominations are due Jan 20, 2015.
For info on the prize see here, if you want to nominate someone
go here.

Godel Prize Nominations are due Jan 31, 2015.
For info on the prize see here, if you want to nominate someone
go here

Would you rather:

1. Win a Godel Prize
2. Win a Knuth Prize
3. Have a prize named after you when you are dead
4. Have a prize named after you when you are alive

I pick 4; however, I doubt I'll have of 1,2,3,4 happen to me.

How about you?

Favorite Theorems Recap

We've now completed five decades of favorite theorems.

• 1965-1974
• 1975-1984
• 1985-1994 (PDF)
• 1995-2004

And to recap the ten we chose this year from 2005-2014

• Undirected Connectivity in Log Space
• Optimal Inapproximability for Max-Cut
• Limitations of linear programming
• Complexity of Nash Equilibrium
• Combinatorial Proof of PCP Theorem
• Constructive Proof of the Lovász Local Lemma
• Polylogarithmic independence fools AC⁰
• QIP = PSPACE
• Lower Bounds on Multilinear Formulas
• NEXP not in ACC⁰

Ten more in ten years. 

Cliques are nasty but Cliques are nastier

BILL: Today we will show that finding large cliques is likely a nasty problem

STUDENT: Yes! In my High School the Cliques were usually at most six people and they gossiped about everyone else. They were very nasty.

BILL: Um, yes, picture in your school that everyone is a node in a graph and that two nodes are connected if they are friends. In your school a clique of size 6 would be 6 people who all liked each other

STUDENT: Actually, the people in a clique secretly hated each other and sometimes belonged to other cliques that would gossip about people in the first clique.

BILL: We might need  the Hypergraph version to model your school.


Computer Scientists and Graph Theorists call a set of nodes that are all connected to each other a CLIQUE - pronounced CLEEK

High School Kids call a group of people who hang out together a CLIQUE- pronounced CLICK.

Which term came first? Why are they pronounced differently when they are quite related to each other? Do the members of a high school clique really hate each other?