FOCS 2006
The program of FOCS 2006 is online. According to persistent rumors, the conference will be held in Berkeley.
The program lists Xi Chen (陈 西?) and Xiaotie Deng (邓 小铁?) as winners of the best paper award, for resolving the complexity of the problem of computing Nash equilibria, one of the fundamental (formerly) open questions in computational game theory. Nicholas Harvey receives the best student paper award.
Update (9/4/96): registration is open.
The program lists Xi Chen (陈 西?) and Xiaotie Deng (邓 小铁?) as winners of the best paper award, for resolving the complexity of the problem of computing Nash equilibria, one of the fundamental (formerly) open questions in computational game theory. Nicholas Harvey receives the best student paper award.
Update (9/4/96): registration is open.
posted by Luca at 3:03 PM
25 Comments:
9/01/2006 03:47:00 PM
Chen Xi is pretty young.
http://csxichen.googlepages.com/
9/01/2006 04:52:00 PM
This seems like the perfect scenario for all those anti-best-paper people who say that it doesn't make sense to give out conference best paper awards. I mean, surely we all agree that the PPAD-completeness of 3-player NASH is a more fundamental result than the improvement to the two player case, and yet the former paper won no award (primarily because Irit's paper was in STOC'06).
9/01/2006 05:48:00 PM
The 3 player case is surely more important but the 2 player case was more surprising. Most people that ventured an opinion predicted polynomiality of the 2 player case.
9/01/2006 06:00:00 PM
My only point is that the PPAD-completeness of 4-NASH was proved (after about 15 years of being open), then a couple weeks later, the 3-player version (by two different groups), and finally a couple weeks after that, the 2-player version. Somehow it's obvious that the original 4-player proof contains the breakthrough, no? (p.s. I am not involved in any way in any of these papers...)
9/01/2006 07:31:00 PM
Best paper awards surely make more sense if the winner is chosen from the last three years, with the ability to have more than one winner. This smooths out the differences between very strong and very weak years. A good year could see as many as three-four winners, a weak year might see none.
On a different note, game theory is the topic du jour. It will be interesting to see if in ten years from now this year's winner is still considered a fundamental breakthrough or it the opinion has changed. I'm unwilling to wager in either direction since my crystal ball is in the shop for repairs.
9/01/2006 10:24:00 PM
I wasn't privy to the PC discussion, but I'd like to think that by giving the award to Chen and Deng, the PC also intended to reflect credit on Daskalakis, Goldberg, and Papadimitriou. Of course it's an imperfect way of doing so, but hopefully most people in our community understand. (Incidentally, the same issue of "recognition by proxy" has long plagued Nobel prizes.)
9/02/2006 03:04:00 AM
By the way, Christos Papadimitriou was in the FOCS 2006 comittee.
9/02/2006 03:28:00 AM
"My only point is that the PPAD-completeness of 4-NASH was proved (after about 15 years of being open)"
People in our community have started thinking about complexity of equilibria after 2001 (when Christos Papadimitriou expressed the opinion that the complexity of "Nash" is an important problem in his stoc invited talk).
Nash proved his existence theorem in 1951. The paper of Papadimitriou that defines the class PPAD and places "Nash" in the class (as a special case of Brouwer) was written in 1991. But, in this paper "Nash" is not given any "particular importance".
So, even though I agree that the complexity of Nash equilibrium is of particular importance within computational game theory, I do not think it is a "major breakthrough" for theoretical computer science (or a problem "open for 15 years").
In fact, the publicity that this result was given is a direct corollary of Papadimitriou's opinions and personality.
The reduction for the 4-player case was indeed based on rather interesting and original ideas.
All the subsequent results were incremental (in terms of new ideas) by more carefully designing the gadgets. This is clear, since they were done in a period of one month after the first 2 papers (GP, DGP).
However, for the 2-player case, the result and not the originality of the techniques gave Chen and Deng the best paper award.
I am dead sure that, since Papadimitrou conjectured that the 2-player case is polynomially solvable [which was a quite reasonable conjecture], none in his group (Daskalakis/Goldberg) even tried to prove it hard.
9/02/2006 03:30:00 AM
When there is no truly big result, it is expected that the result with the biggest publicity will get the award.
9/02/2006 07:11:00 AM
I am dead sure that, since Papadimitrou conjectured that the 2-player case is polynomially solvable [which was a quite reasonable conjecture], none in his group (Daskalakis/Goldberg) even tried to prove it hard.
This comment typifies a way of thinking among mathematicians and computer scientists that I think would be astounding to oustiders. To oversimplify a bit:
Sure, A might have disproved B's conjecture, but that's basically a trivial contribution -- since had B known his conjecture was wrong, he could easily have proved it wrong himself.
I'm not criticizing this way of thinking, just pointing it out.
9/02/2006 09:31:00 AM
"When there is no truly big result, it is expected that the result with the biggest publicity will get the award. "
I completely disagree with the above comment; there are very good approximation algorithm papers in this FOCS which solve open questions after almost 10 years, i.e.
Bounded Degree Minimum Spanning Trees
by Michel Goemans
AND
Approximation Algorithms for Non-Uniform Buy-at-Bulk Network Design Problems
by Chandra Chekuri, MohammadTaghi Hajiaghayi, Guy Kortsarz, Mohammad R. Salavatipour
Though I am not involved in any way in any of these papers, I know them because I'm working in approximation algorithms for long time. I really think that the selected best paper is rather incremental.
9/02/2006 02:46:00 PM
Approximation Algorithms for Non-Uniform Buy-at-Bulk Network Design Problems
Is it related to the stochastic, dynamic traveling dog and pony problem with piecewise linear costs?
9/02/2006 03:35:00 PM
The Goemans paper indeed sounds very interesting. However I'm unwilling to second guess the committee without having read the papers at length. This discussion is useful nonetheless, it can serve as informal feedback for the PC of how the community sees the decision.
Lastly, the stakes are rather small. Personally, , when I read a hiring candidate's CV I place almost no value on best paper awards, unless the candidate has over half a dozen of them. Having served in PC committees often, I'm far too aware of how much of a crapshot they are.
9/03/2006 08:25:00 AM
- begin cynic -
The complexity of 2-Nash has not been resolved. While it has been shown to be PPAD complete, we do not know where the PPAD class falls within the hierarchy. As far as I know there's little intuition as to whether PPAD is in P or not.
I treat the result more as: try to find a P time algorithm for the 2-Nash case, since the rest are no harder.
- end cynic -
9/05/2006 12:26:00 PM
Summary of the previous posts:
negative:
1. The 2-Nash paper is incremental; all main ideas were in the previous paper(s).
2. Showing the PPAD completeness does not mean too much.
positive:
1. The result is surprising.
My personal opinion:
First, it's a good result, though technically rather simple. But simple work can be important.
Second, whether it deserves a best paper doesn't matter too much to the community. And we all know that the main contribution of this series of work is by DGP.
Btw, as to the result being surprising, I really don't know why. Simply because Papadimitriou made the opposive conjective? I once looked at the 2-Nash problem for a very short period of time, but didn't get any intuition why it should be in P. (It's far from the LP problem.)
9/05/2006 01:49:00 PM
To the last anonymous: I think that most important work is simple and should be simple. Note that simple doesn't mean easy.
Of course, I am not saying that the work of C-D is simple but not easy. I am a complete outsider and in no position to judge.
9/05/2006 02:30:00 PM
As far as I know there's little intuition as to whether PPAD is in P or not.
For what they're worth, we do have oracle separations of PPAD from P (and a variety of other classes within TFNP). It seems likely that PPAD is of difficulty properly between P and NP.
9/05/2006 02:35:00 PM
As far as I know there's little intuition as to whether PPAD is in P or not.
For what they're worth, we do have oracle separations of PPAD from P (and a variety of other classes within TFNP). It seems likely that PPAD is of difficulty properly between P and NP.
9/05/2006 10:22:00 PM
Incremental, schmincremental.
What I find interesting is that, in this conference, Tsinghua is presenting more papers than Berkeley (and, perhaps more remarkably, as many as Assaf Naor!) including the best paper of the conference. And I think that this is only the beginning.
9/06/2006 09:12:00 PM
Why can't people simply be happy with the decision of FOCS PC and congratulate the winner for their great work?
Each selection of a best paper is a collective subjective opinion.
For example, STOC 06's selection
of the paper of Irit Dinur, for an alternative proof of a known result, over the paper of DGP on 4-NASH (which some of the postings consider a breakthrough), is merely a collective subjective opinion of that PC.
9/08/2006 09:41:00 AM
"For example, STOC 06's selection
of the paper of Irit Dinur, for an alternative proof of a known result, over the paper of DGP on 4-NASH (which some of the postings consider a breakthrough), is merely a collective subjective opinion of that PC."
I'm sorry to say that, but you probably have nothing to do with computational complexity (or mathematics).
Irit's result *is* a major breakthough. There is absolutely no comparison between this work and anything that could ever be done in computational game theory.
And for the record, it is not just a simpler (and conceptually different) proof of an amazing result (which would be more than enough). It also answers several open questions from recent papers.
9/09/2006 04:22:00 AM
So did many people re-proved perelman's result.
http://en.wikipedia.org/wiki/Grigori_Perelman
9/09/2006 10:19:00 AM
The analogy with Perelman is misleading: Dinur was hardly fixing "gaps" in the old proof.
A better analogy is perhaps Gower's proof of Szemeredi's theorem. The result was known, but a "new" proof was Field's medal worthy.
9/09/2006 11:37:00 AM
A better analogy is perhaps Gower's proof of Szemeredi's theorem. The result was known, but a "new" proof was Field's medal worthy.
Gowers also solved or helped solve a number of long-standing open problems in Banach spaces, which is probably the primary reason he received the Fields.
9/09/2006 11:40:00 AM
Irit's result *is* a major breakthough. There is absolutely no comparison between this work and anything that could ever be done in computational game theory.
I think this is a debatable claim. Certainly a polynomial-time algorithm for computing Nash equilbria in general games would have been quite spectacular.
And for the record, it is not just a simpler (and conceptually different) proof of an amazing result (which would be more than enough). It also answers several open questions from recent papers.
Yes, but the open questions that it answers (e.g. very short PCPs) are not nearly as interesting as the proof itself. I suspect that without those applications, it would still have won best paper.
Post a Comment
<< Home