My call for confirmation worked. I got a second member of the FOCS'07 PC to confirm that 15 rejections appeared in STOC'08. So pending new developments, let's treat this number as roughly correct.
The next steps are to:
- also get a 2nd confirmation for SODA'08.
- look at previous FOCS / SODA, and see how many rejects appeared in next STOC to see whether the numbers are really different. If you were on a previous FOCS / SODA PC and would like to help anonymously, please let me know... I think these statistics would be an interesting factoid for everybody, regardless of what we think of the current STOC.
![[home]](http://people.csail.mit.edu/mip/images/home.gif){kind=small}
17 comments:
I think this is just a fact of life we have to accept. Maybe those 15 papers that got rejected were not excellent; but they do have to be published somewhere, don't they? If you've ever had a paper rejected, didn't you patch it up and send it in again (perhaps at another conference)? Do you think a rejection means the paper is dead? Do you think it should mean that?
The argument "they have to be published somewhere" sounds a bit lame for the intended level of STOC/FOCS, don't you think? :)
Of course people resubmit. I'm sure most authors of those 15 papers had the best intentions. My qualms are not about them.
Still, with what confidence can you say "large number of accepted rejects imply bad decisions by committee members"?
Where did you resubmit your rejected STOC papers? Surely not FOCS...
I had one paper rejected from STOC, and I submitted it to FOCS. Evidently I consider whatever decision that STOC PC reached for algorithmic papers to be irrelevant, since they hardly accepted any. I guess the competition among algorithmic papers will higher than usual at this FOCS, since it has to take a double load...
Just for the record: would someone compile a list of algorithmic papers (whatever that means) at STOC 2008? It should not be such a huge task, since there is hardly any (according to mip).
Why doesn't the writer of this blog compile such a list? It's him, after all, who is making the claim. Why not provide us with some evidence? B.t.w., the two best paper awards went to algorithm papers!
If you read my original post, I said that by "algorithms" I mean "non-approximation algorithms." As you point out, there's not much reason to decry the fate of approximation algorithms at this conference.
Depending on exactly what you mean by non-approximation algorithms, a list can look like the following:
Minimum k-way cuts via deterministic greedy tree packing
Mikkel Thorup
Fast Integer Multiplication Using Modular Arithmetic
Anindya De and Piyush P Kurur and Chandan Saha and Ramprasad Saptharishi
Graph Sparsification by Effective Resistances
Daniel Spielman and Nikhil Srivastava
Faster Approximate Lossy Generalized Flow via Interior Point Algorithms
Samuel I. Daitch and Daniel A. Spielman
Some of the algorithmic papers in STOC'08 (at least, the titles suggest that they're algorithmic):
Minimum k-way cuts via deterministic greedy tree packing, Mikkel Thorup
Additive Guarantees for Degree Bounded Directed Network Design, Nikhil Bansal and Rohit Khandekar and Viswanath Nagarajan
Optimal Algorithms and Inapproximability Results For Every CSP? Prasad Raghavendra
A Fixed-Parameter Algorithm for the Directed Feedback Vertex Set Problem, Jianer Chen and Yang Liu and Songjian Lu and Barry O'Sullivan and Igor Razgon
Fast Integer Multiplication Using Modular Arithmetic, Anindya De and Piyush P Kurur and Chandan Saha and Ramprasad Saptharishi
Fast polynomial factorization and modular composition in small characteristic, Christopher Umans
An $O(\log^2 k)$-approximation algorithm for the $k$-vertex connected subgraph problem, Jittat Fakcharoenphol and Bundit Laekhanukit
Randomized Competitive Algorithms for Generalized Caching, Nikhil Bansal and Niv Buchbinder and Joseph (Seffi) Naor
Additive Approximation for Bounded Degree Survivable Network Design, Lap Chi Lau and Mohit Singh
Optimal Hierarchical Decompositions for Congestion Minimization in Networks, Harald Raecke
An optimal SDP algorithm for Max-Cut, and equally optimal Long Code tests, Ryan O'Donnell and Yi Wu
Optimal Algorithms for Finding Graphs, Sung-Soon Choi and Jeong Han Kim
Network Design for Vertex Connectivity, Tanmoy Chakraborty and Julia Chuzhoy and Sanjeev Khanna
Graph and Map Isomorphism and All Polyhedral Embeddings In Linear Time, Ken-ichi Kawarabayashi and Bojan Mohar
Faster Approximate Lossy Generalized Flow via Interior Point Algorithms, Samuel I. Daitch and Daniel A. Spielman
For sure there are more algorithmic papers, but I just went through the titles and took the most obvious ones.
I think, MIP is saying that certain special types of algorithmic papers are poorly represented, but I don't think that we don't see any algorithmic papers.
BTW I haven't seen many data structure papers.
I guess I have my own definition of algorithms that can include, for instance, streaming algorithms, but on the other hand does not include approximation algorithms (and thus does not include mechanism design, price of anarchy etc).
There are many reasons for this distiction. Perhaps the most important is that approximation algorithms are a big big field, which is very independent from the rest of algorithms. They use rather different techniques, and they are studied by a largely disjoint set of people.
I think the distinction between approximation algorithms and exact algorithms is much narrower than you imply, and failing to count them is strange. Fast optimal algorithms tend to use what I would ocnsider to be approximation techniques (cuttings in computational geometry, scaling in flows, etc).
Of course, you have the right to use the word algorithm in any way you see fit, but then you might be in a disagreement with the rest of humanity(*). An adimerable position to be in, but not necessarily benefitial for a discussion on a blog.
Humanity = people currently doing phd in theory of CS in MIT.
So lets sum up:
The argument that there are no algorithm people on the committee: false
The argument that algorithm papers are underrepresented in an unusual way: false
The argument that there are more FOCS/SODA rejected papers than usual: unverified and irrelevant
So, we are left with a blogger who, as mentioned before, enjoys being in disagreement with the rest of humanity. How exciting.
Of course, one could argue (and many do) that STOC/FOCS under represent some fields and over represent others. One could also argue that the acceptance standards are misguided. An effective discussion requires some maturity and civility => not on this blog.
Anon, arguments from frustrated, insignificant members of the community have as much weight as their author. Though you fail to reveal your identity, your tone has just about enough information...
Mihai,
see DH0 in http://www.paulgraham.com/disagree.html
Call me Ishmael.
Thanks for the link; it was an entertaining read. But it seems my intention was misunderstood. I wasn't trying to "disagree" with this guy.
The distinction between approximation and non-approximation algorithms is not quite mine. Talk to people at SODA. There is actually some tension between the fields. People in approximation tend to think improvements to polynomials are not theoretically fundamental and should only be done for the sake of practice. People in non-approximation complain that approximation people form a clique which pushes too many papers in; there are too many problem variants in the field (see the travelling dog and pony); and that the field has ultimately had very little impact outside theory (the common argument that people in practice like to approximate their problems to within 2%, not within a log factor).
Of course there are relations between the fields. But there are also important relations eg between CS and functional analysis, and nobody thinks the fields are identical.
Post a Comment