- Accepted Papers
- Accepted Papers with Abstracts
- Accepted Papers with available PDF links (Shiva Kintali)
- Algorithmic Game Theory (Noam Nisan)
- Geometry and Topology (Jeff Erickson)
- Streaming (Muthu Muthukrishnan)
Here are a few of the many interesting looking papers that caught my eye.
- David Doty. Randomized Self-Assembly for Exact Shapes
- You just don't see many STOC/FOCS papers on self-assembly or from Iowa State.
- Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco Servedio and Emanuele Viola. Bounded Independence Fools Halfspaces
- I like results that just sound neat and can be fully stated in the title.
- Zeev Dvir, Swastik Kopparty, Shubhangi Saraf and Madhu Sudan. Extensions to the Method of Multiplicities, with applications to Kakeya sets and Mergers
- And better randomness extractors too.
- Or Meir. Combinatorial PCPs with efficient verifiers
- Sounds interesting and the only FOCS paper that cites one of my papers in the abstract.
- Rahul Jain, Sarvagya Upadhyay and John Watrous. Two-message quantum interactive proofs are in PSPACE
- QIP is known to sit in between PSPACE and EXP and it's an interesting open question which way it goes. This paper makes some progress in resolving that.
- Neeraj Kayal and Shubhangi Saraf. Blackbox Polynomial Identity Testing for Depth 3 Circuit
- Makes progress on deterministic polynomial identity testing, one of the few remaining probabilistic algorithms to derandomize.
- Ravindran Kannan. A new probability inequality using typical moments and concentration results
- Looks like something we will all need to add to our toolboxes. The accepted papers list dropped the word "inequality" which made the paper seem unreal.
- Alexander Sherstov. The Intersection of Two Halfspaces Has High Threshold Degree
- An exciting result in its own right. The Complexity class analogue goes the other way: Beigel, Reingold and Spielman showed the class PP is closed under intersections.
When will these papers be available on the web? Will FOCS be posting the camera-ready versions, or has computer science still not entered the computer age?
ReplyDeleteThose are nice indeed.
ReplyDeleteDiscussions of accepted crypto papers Jon Katz' readers and Adam Smith.
ReplyDeleteI fail to understand the brouhaha twice a year about the "FOCS/STOC accepted papers". Many of these papers have been available via the arxiv or the authors' homepages for a while. Why is it that the mere fact of being "accepted at FOCS/STOC" suddenly elevates their scientific merit compared to those measly "unaccepted ones" ?
ReplyDeleteThat having said, its my impression that the FOCS 2009 committee did a much better job at evaluating the scientific merit of papers (especially those which are slightly out of mainstream) than the STOC 2009 committee. I suspect this might have something to do with the fact the FOCS committee had a higher representation of core theorists (and probably more mature) than the STOC one.
Anon 4's first comment reminds me of what I read about an interview with Alain Connes:
ReplyDelete"The interview also contains quite a few amusing stories. In one of them Connes tells about a well-known string theorist who walked out of his talk at Chicago because he wasn’t very interested, but two years later was paying rapt attention to the same talk when Connes gave it at Oxford. When Connes asked him about this, the physicist told him that the difference was that in the meantime he had heard that Witten had been seen reading Connes’s book in the library at Princeton."
Quote taken from
http://www.math.columbia.edu/~woit/wordpress/?p=313
Re: Anon #4's point about why acceptance makes papers more interesting.
ReplyDeleteThe simple answer of course, is that publication venue has no effect on the scientific value of a paper.
However,
1) Focus of attention: there are zillions of papers out there being written all the time (even in a topic as specific as the theory of cryptography). I don't have time to understand all their abstracts, never mind the specific results. The FOCS accepted paper list represents what some set of good researchers deemed to be interesting (among the submitted papers...) and so it gives me an interesting set of papers on which to focus my attention. For the same reason, receiving a Pulitzer prize increases the sales of a book, and getting linked to from slashdot hugely increases the traffic to a website.
2) Professional development (for lack of a better term): I read FOCS/STOC papers to learn more about what people in the community consider to be interesting research these days.
Here are two ways to think about number 2:
(Cynical version) "my career depends largely on where my papers are published, and FOCS/STOC are usually counted as good venues. It is therefore interesting for me to know what kinds of papers get accepted there, in order for me to adjust my research program to produce more papers like these."
(Slightly less cynical) "I am a young researcher, and I develop my taste in research problems *partly* by seeing examples that others have labeled as interesting, and deciding what I think of them".
Of course, there is also the "groupthink" downside to both of the points above. I assume this is what anon #4 was getting at.
Regarding the comment about the papers being available online: many of them aren't. For example, I heard about Gentry's homormorphic encryption paper from the STOC 2009 accepted papers list.
gentry's paper is still not online if i'm not mistaken ...
ReplyDelete" Focus of attention: there are zillions of papers out there being written all the time (even in a topic as specific as the theory of cryptography). I don't have time to understand all their abstracts, never mind the specific results. "
ReplyDeleteI do not understand why this problem is so specific to TCS, and why people in TCS cannot adopt the mechanism used by most mathematicians -- namely, to subscribe to an arXiv feed in the areas of his/her interest and just browse the daily mailings for papers of interest. It takes less than 10 min and is remarkably efficient. I do not think that the number of papers that TCS produces is more than most active areas of mathematics -- yet, mathematicians do not have to relying on an artifical "vetting process" which is what STOC/FOCS seems to have degenerated into nowadays.
"It is therefore interesting for me to know what kinds of papers get accepted there, in order for me to adjust my research program to produce more papers like these."
I understand the compulsions of young researchers --believe me, I do. At the same time I must say that a research program aimed at "producing more papers like these" is doomed as a scientific endeavor of any sort. But, unfortunately this is the direction the FOCS/STOC system is taking the young researchers into. There are plenty of hard/open questions in TCS that theorists tend to ignore -- because they will not lead immediate FOCS/STOC success. Same goes for unravelling the mathematical mysteries behind already published results -- another sort of research that FOCS/STOC system does not reward. However, for the young and the ambitious -- these are the directions to take, instead of producing "more like these" papers as is the norm today.
I am not a regular commenter, but I find it surprising that no one has called Anonymous 4 on her/his second comment: "That having said, its my impression that the FOCS 2009 committee did a much better job at evaluating the scientific merit of papers (especially those which are slightly out of mainstream) than the STOC 2009 committee."
ReplyDeleteThis is an irresponsible comment - unless you knew exactly what the submissions to both conferences were and which ones were chosen. Making a statement based on the accepted papers list is silly - the best you can say is that you like the focs papers better, not that "[FOCS PC] did a much better job" than the STOC PC.
Wow, what an unbelievably snide comment about David Doty's paper? Yes, maybe someone from Iowa state produced an excellent paper. How is that so hard to believe? Maybe their is more to acceptance bias based on the reputation of the schools or authors? I even recall researchers from places like MIT and other top institutions having to retract STOC papers because the results were shown to be incorrect after they had been accepted. Is this fair?
ReplyDelete>Maybe their is more to acceptance bias >based on the reputation of the schools or >authors?
ReplyDeleteTo answer this question, I will simply refer you to a blog-post by a prominent member of the community:
http://blog.computationalcomplexity.org/2009/03/you-can-separate-art-from-artist.html
This is an irresponsible comment - unless you knew exactly what the submissions to both conferences were and which ones were chosen. Making a statement based on the accepted papers list is silly - the best you can say is that you like the focs papers better, not that "[FOCS PC] did a much better job" than the STOC PC.
ReplyDeleteOh, come on, this is the complexity blog for god's sake -- not the state of the union address. One can express opinions here -- without having to justify everything. Also, how do you know that Anon 4 is not privy to the list of submitted papers to both conferences ? After all such lists are not the biggest secrets out there. Isn't it a bit silly on your part to make such an assumption without knowing ?
Based on their abstracts, no more than a handful of FOCS papers were STOC submissions. In some of the cases the FOCS PC had more expertise in the given area, in some of the cases they had less, so I don't think that one can make sweeping judgements based on the composition of the PCs. In two cases, the STOC reviews complained a lot about poor writing, so one would presume that changes in write-ups have been made. There are also three other FOCS papers where there is clearly overlap with a STOC submission but there has been a very substantial improvement in results.
ReplyDeleteThis level of noise in the system is not that surprising. Is it troubling?
It looks like fewer than half of the accepted papers are available online. What's up with that? The submissions were required to include full proofs, and the arxiv allows revisions anyway. A lot of people need to get their acts together.
ReplyDeleteThe universities in Iowa did well in FOCS. David Doty at Iowa State has a paper and a group at U of Iowa has a paper. Cool!
ReplyDeleteActually, Iowa State is not an uncommon participant in the FOCS/STOC paper list. Offhand, I recall Baker and Selman in the seventies, as well as a number of papers of Jack Lutz (although fewer than in COmplexity and ICALP).
ReplyDeleteActually, Iowa State is not an uncommon participant in the FOCS/STOC paper list. Offhand, I recall Baker and Selman in the seventies, as well as a number of papers of Jack Lutz (although fewer than in COmplexity and ICALP).
ReplyDeleteIowa State as a whole has 2 FOCS papers (Doty 2009, Gu/Lutz/Mayordomo 2006) and 1 STOC paper (Nandakumar 2008).
Baker was at the University of Iowa for two years, but never at Iowa State.
Coincidentally, Jarkko Kari was an author on the only other FOCS self-assembly paper (Adleman/Kari/Kari/Reishus 2002), while visiting the University of Iowa.
If I'm not mistaken, Shang-Hua Teng now holds the record for the most papers in a single STOC/FOCS. He has five in FOCS 09.
ReplyDeleteThe previous record holders had four:
- Madhu Sudan (FOCS 94, 95)
- Mihai Patrascu (FOCS 08)
- Piotr Indyk (FOCS 99)
- Jon Kleinberg (FOCS 05)
(Probably there are others...)