FOCS 2013 is over, and as predicted here it was very successful. I am happy to have taken part in its success (though all of the credit goes of course to the authors).
I also predicted that “A significant fraction of the community will think the PC messed up badly.” Naturally, most of the people with a paper at FOCS were generally happy with the PC work so I did not get too many complaints 🙂 (but I did get some). What I did find was that FOCS/STOC attendees passionately care about FOCS/STOC. I therefore got to hear quite a few personal philosophies about what’s good and bad in FOCS/STOC and what should be changed. The interesting aspect is that the opinions were at times the exact opposite:
- Some think (as also reflected in the comments here) that the conference has become too competitive and selective which is why FOCS/STOC is less important now. Others think that FOCS/STOC are accepting too many papers and in this sense the PC is not doing its job of filtering and therefore FOCS/STOC does not serve the purpose of joining TCS and is less useful.
- Some feel that authors and speakers in FOCS/STOC are drowning the audience in technical details rather than sharing ideas and this happens in part because FOCS/STOC papers are judged by experts in their subfield rather than by the community at large. Others expressed rage that the papers aaccepted in their subfield are far from being the best papers submitted. They say that this happens because they are judged by general TCS experts rather than by the subfield experts.
- Some think that FOCS and STOC should be joined into a single bigger event that will draw the attention of the entire community (but with multiple submission deadlines such as is now happening in other fields). Other think it is a horrible idea and two conferences are extremely important.
- The business meeting saw some exciting arguments on various topics.
- Sanjeev and I had a vigorous discussion (to be continued I am sure) on the no-page-limit policy initiated by the FOCS 2013 PC.
As you might have realized by now, I am passionate about FOCS/STOC as well. The experience of chairing FOCS made me think about it much more and I have various ideas about changes to be made (I did express my ideas even before but I have refined them since). But the abovementioned discussions indicate to me that (1) FOCS/STOC is still extremely important to many of us, (2) changes should be gradual and controlled as we have such a diverse set of expectations.
After things settle in my mind, I may blog some more about what I think should be done, but for now let me just say that I believe the following combination is important and possible: FOCS/STOC should allow wide active participation (in numbers larger than today and by a more diverse community). On the other hand a small enough (and humanly digestible) part of the program should facilitate cross fertilization and information flow between the sub communities. The federated theory conference which so many of us support is a good idea but only part of the solution.
Windows On Theory 
Congratulations Omer on a great FOCS! You set a high bar, and I just hope the next PC chair doesn’t mess up too badly 🙂
Not really related to changing FOCS/STOC but some thoughts I had after attending the conference are:
1) It was inspiring to see how all the award papers involved multi year projects, where the authors, often students or postdocs, dedicated a significant amount of time to the problem, in some cases not publishing for a year or more while working on it. I guess it’s another example of how addictive some TCS problems can be 🙂 While the authors didn’t do it for the awards, it was nice to see their hard work recognized.
2) I was reminded again how much value can be in a 20 minute talk, when done well. There were many great talks but two examples that stuck in my mind were Nikhil Srivastava’s talk on Ramanujan expanders of any degree, and Pritish Kamath’s talk on depth reduction of arithmetic circuits. Also, while I can’t say I followed everything, once the videos are up, check out Daniel Nagaj’s talk on QMA_1 completeness of quantum 3-SAT for a wild ride of quantum clocks that measure time forward, backward, and sideways.
I have a really good feeling about the next chair 🙂
As I said in previous posts, I’m not a big fan of STOC-FOCS. But one thing that is really bothering is the scientific stagnation it leads to: if there is only one bi-annual leading conference for American-style theory, and the PC members are chosen from those who often (and recently) publish in STOC-FOCS themselves, then we are heading to a sort of dictatorship: those who publish in STOC-FOCS will serve as PC members, accepting papers of the areas that interest them, leading to the next PC having approximately the same PC, and so forth.
The solution for this is either more distribution of power, or going for journal publications as Lance Fortnow suggests.
A non-rhetorical question: how are journals, whose editorial boards don’t change much, any different?
Other questions I have are: why should there be more than one *leading* conference? Two annual meetings seems quite appropriate for the size of the community, many bigger communities meet only once a year. And 3-4 meetings annually seems like quite a diluted brand of “leadership”.
Also, do you have some examples of recent significant theoretical results that have appeared outside FOCS/STOC, because the results are in areas that are not of interest to the STOC/FOCS crowd? I say significant, because optimizing for borderline papers is probably not the right way to go.
Hello Sasha. These are good questions.
For your first one, the answer is simply that 1) journals are much more distributed (there are more than one leading journal), and 2) that papers in journals are not competing against other papers, but are judged based on their own merit. Therefore papers in area X would not suffer from unjustified competition from fashionable area Y.
For your second question: it is related to the first. There should never be only one leading conference (or two practically similar conferences), unless you wish to form an intellectual/scientific dictatorship. Things should be distributed among different people, different power-groups, different tastes, different views on what is important in TCS and what is not, what kind of research should be promoted and what should not, etc. These things are subjective, and relates to the personal value system of a researcher. What happens now is a monolithic system. Yes, some people certainly approves of such a system.
About other “communities”, I don’t have knowledge of these, but I don’t see a reason to copy what other “communities” are doing.
For your third question, yes, certainly, I have numerous examples of recent significant results in TCS not published in STOC-FOCS. (Though I would prefer not to point on specific names and titles, as I don’t want to lead to personal debates on these papers and researchers.)
For more thoughtful, and sometimes different, arguments against STOC-FOCS you can look up Goldreich’s essays:
http://www.wisdom.weizmann.ac.il/~oded/on-stocfocs.html
http://www.wisdom.weizmann.ac.il/~oded/my-choice.html
http://www.wisdom.weizmann.ac.il/~oded/on-values.html
And Fortnow’s essay:
http://cacm.acm.org/magazines/2009/8/34492-viewpoint-time-for-computer-science-to-grow-up/fulltext
Also, do you have some examples of recent significant theoretical results that have appeared outside FOCS/STOC, because the results are in areas that are not of interest to the STOC/FOCS crowd?
Here’s a list of significant results not appearing in STOC/FOCS over the last 13 years, scrapped from a web site. One could argue that there are some results there that would look “too algorithmic” (an exact quote from a STOC review to a friend’s paper) for STOC/FOCS.
+ Algorithms, Games, and the Internet, Christos H. Papadimitriou, 2001
+ Cuckoo Hashing, Rasmus Pagh, Flemming Friche Rodler, 2001.
+ External Memory Data Structures, Lars Arge, 2001.
+ Finding Frequent Items in Data Streams, Moses Charikar, Kevin Chen, Martin Farach-Colton, 2002
+ Simple Linear Work Suffix Array Construction, Juha Kärkkäinen, Peter Sanders, 2003
+ Experiments on Graph Clustering Algorithms, Ulrik Brandes, Marco Gaertler, Dorothea Wagner, 2003.
+ Heuristically Optimized Trade-Offs: A New Paradigm for Power Laws in the Internet, Alex Fabrikant, Elias Koutsoupias, Christos H. Papadimitriou, 2002.
+ Influential Nodes in a Diffusion Model for Social Networks, David Kempe, Jon M. Kleinberg, Éva Tardos, 2005
+ Frequency Estimation of Internet Packet Streams with Limited Space, Erik D. Demaine, Alejandro López-Ortiz, J. Ian Munro, 2002.
+ Differential privacy, C Dwork, 2006
+ Symbolic Trace Analysis of Cryptographic Protocols, Michele Boreale, 2001
+ The Structure and Complexity of Nash Equilibria for a Selfish Routing Game, Dimitris Fotakis, Spyros C. Kontogiannis, Elias Koutsoupias, Marios Mavronicolas, Paul G. Spirakis, 2002
+ The whole genome assembly of Drosophila, Gene Myers, 2000.
+ Improved Steiner tree approximation in graphs, Gabriel Robins, Alexander Zelikovsky, 2000.
+ Comparing top k lists, Ronald Fagin, Ravi Kumar, D. Sivakumar, 2003.
+ Efficient oblivious transfer protocols, Moni Naor, Benny Pinkas, 2001.
+ High-order entropy-compressed text indexes, Roberto Grossi, Ankur Gupta, Jeffrey Scott Vitter, 2003.
+ k-means++: the advantages of careful seeding, David Arthur, Sergei Vassilvitskii, 2007.
+ Computing the shortest path: A search meets graph theory, Andrew V. Goldberg, Chris Harrelson, 2005.
+ Tight bounds for worst-case equilibria, Artur Czumaj, Berthold Vöcking, 2002.
+ Succinct indexable dictionaries with applications to encoding k-ary trees and multisets, Rajeev Raman, Venkatesh Raman, S. Srinivasa Rao, 2002.
+ Sampling from a moving window over streaming data, Brian Babcock, Mayur Datar, Rajeev Motwani, 2002.
+ Computing contour trees in all dimensions, Hamish Carr, Jack Snoeyink, Ulrike Axen, 2000.
Since I don’t want to hijack the discussion here, Omer, I congratulate you for your success in chairing FOCS, and I retract my previous comment, which should have appeared in your previous post on STOC and FOCS and not here. Feel free to ignore it.
CS Prof: I welcome the discussion. I think that FOCS/STOC is extremely useful and should be improved for the community who cares about it (regardless of how you want to call this community). I am much less concerned about those who have such a negative opinion, as you seem to reflect in your comments. If you think that journals are better, submit to journals, why do you care to throw stones at something many of us find so useful and important.
As for some of the discussion – of course great theory papers appeared outside of FOCS/STOC. I can add many other examples to the list. This is great, as we do want our more specialized conferences to be successful and we do want researchers to have alternatives. Many of these papers would have been happily accepted by FOCS/STOC. In other cases, it is completely fine that some ideas were first examined by a sub-community before asking for the attention of the entire community. A few cases are failures of FOCS/STOC, and while failures always exist we should improve (I have my own ideas on how to do it, but this is not for here). On the other hand, in this time period there were many more great theory papers within FOCS/STOC. I think all of this completely refutes CS Prof’s claims: (a) FOCS/STOC is anything but stagnated, (b) TCS is not a dictatorship and good papers have many excellent venues. Good research prevails!
The claims about journals makes no sense to me. Imagine the case where everybody submited only to journals. In such a case, a JACM publication could be deciding hiring cases or tenure cases (like Science/Nature/Econometrica/Annal/… in other fields). Imagine how much power would the few and long lasting theory editors in JACM have. Compare this to the number of people that influenced FOCS/STOC decisions in the last 4 years. The fact that things are not perfect in FOCS/STOC does not mean that we can abandon reason when trying to reform it.
I concur with Omer here. The idea is to improve STOC/FOCS as part of their natural evolution, not to do away with them.
CS Prof: if you think about it Omer, Sanjeed, Salil, Boaz and myself are nibbling around the edges. We are talking page limits vs. no page limits, a possible (long overdue) mild increase in the number of papers and perhaps a rebuttal round. None of these are game changers.
Yes, it was a great conference.
Omer, I left a comment on the benefits of page limits as part of the previous discussion.
I second Omer’s comments about the good talks. Daniel Nagaj’s talk was one for the history books. I’d love to know where he learnt those design principles.
I also liked Lorenzo Orechchia’s talk about regularization at the Sat workshop; no theatrics but tying together many disparate ideas in a very interesting way.
I really enjoyed the 1 hour talks at the workshop. Makes me realize that it would be nice to see some longer talks at STOC/FOCS.
ps I used to avoid leaving public praises for individuals in this way but now I think people who put in the work making a good talk deserve positive feedback. We want the quality of talks to stay high.
This was Boaz’ comment not mine. I left a reply to your page limit comment but I have the feeling we cannot resolve it in this blog.
Thoughts on your second bullet: “Some feel that authors and speakers in FOCS/STOC are drowning the audience in technical details rather than sharing ideas and this happens in part because FOCS/STOC papers are judged by experts in their subfield rather than by the community at large.”
I’m not confident about the causal relationship suggested by whomever made this comment; regardless, it would be interesting to figure out how to encourage talks that are better targeted towards the community at large. It seems tricky to tie the paper selection process to encouraging good talks directly, but perhaps there are other approaches. Probably the posting of talk videos (which I assume is happening soon) will help encourage this as broadly accessible talks would be able to reach a wider audience. (I hope to see these videos soon!)