tag:blogger.com,1999:blog-3722233.post5411407972477250151..comments2014-07-31T02:45:21.340-05:00Comments on Computational Complexity: Where is the youth of TCS/Market Eq/Guest Post by VijayLance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.comBlogger23125tag:blogger.com,1999:blog-3722233.post-69808578256116275702013-01-09T06:52:45.390-06:002013-01-09T06:52:45.390-06:002-NASH is PPAD-complete. "Setting the complex...2-NASH is PPAD-complete. "Setting the complexity of computing a Nash Equilibrium" by Chen and Deng. Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-86124318506576031022012-12-09T16:42:27.380-06:002012-12-09T16:42:27.380-06:00Vijay's post doesn't make the issue quite ...Vijay's post doesn't make the issue quite as clear as it could be. There are two different versions of approximation in our usual bit model of computation. The problem NASH as defined by Papadimitriou, which we now know to be PPAD-complete, asks for a point that is an epsilon-approximate equilibrium. However, though a point is close to being in equilibrium, it does not mean that there is a true equilibrium nearby. The problem considered by Etesammi and Yannakakis is to ask for a point that is within epsilon of a true equilibrium. Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-27486483009571956162012-12-08T23:19:00.638-06:002012-12-08T23:19:00.638-06:00Vijay, it is possible that much of the confusion r...Vijay, it is possible that much of the confusion rests with others in the Market Eq community, who use different definitions of {\sc Nash} than you do. For example, in both their 2006 STOC paper and a 2009 CACM article, Daskalakis, Goldberg, and Papadimitriou make claims such as the following:<br /><br />"We show that finding a Nash equilibrium is complete for a class of problems called PPAD"<br /><br />"Indeed, in this paper we describe a proof that {\sc Nash} is PPAD-complete"<br /><br />"In this paper we show that {\sc Nash} is PPAD-complete, thus answering the open questions discussed above."<br /><br />http://people.csail.mit.edu/costis/journal_ver10.pdf<br />http://people.csail.mit.edu/costis/simplified.pdf<br /><br />You might also get similar mixed results if you asked the audience whether SDP (semidefinite programming) is in P.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-37526657223217331452012-12-08T19:27:46.328-06:002012-12-08T19:27:46.328-06:00Euclidean TSP is not known to NP-complete, but it&...Euclidean TSP is not known to NP-complete, but it's known to be NP-hard. And it's been known a long time before Trevisan's paper. And as Anon 7:42am said, we don't know if the problem is NP-complete because of the tricky problem of dealing with the sum of square roots.<br />However, Vijay's question is not tricky. It's a very basic question which should be taught in complexity classes, and PhD students in theory should be familiar with it. And I think this is what Vijay is pointing out. That too many of us don't know some very basic facts from complexity theory, like whether Euclidean TSP is NP-complete, or whether Nash is PPAD-complete.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-372812658258930502012-12-08T07:42:35.026-06:002012-12-08T07:42:35.026-06:00Not even known to be in NP, due to precision neede...Not even known to be in NP, due to precision needed for the sum of square roots problem: http://cs.smith.edu/~orourke/TOPP/P33.html. A tricky question!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-49750175630420493282012-12-08T06:07:38.870-06:002012-12-08T06:07:38.870-06:00Hi Vijay,
(I'm not anon from 5:03pm.)
I thin...Hi Vijay,<br /><br />(I'm not anon from 5:03pm.)<br /><br />I think Euclidean TSP is NP-complete due to Luca Trevisan's paper "when hamming meets Euclid". But I admit that I am not 100% sure despite being an algorithms person who actually could explain the details of most of the recent progress on graphic TSP results.<br /><br />Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-4758274536082074622012-12-07T22:14:47.472-06:002012-12-07T22:14:47.472-06:00Question to Anon at 5:03pm: Is Euclidean TSP NP-c...Question to Anon at 5:03pm: Is Euclidean TSP NP-complete?Vijay Vaziraninoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-89833485768204823922012-12-07T17:03:04.706-06:002012-12-07T17:03:04.706-06:00I really don't understand why Vijay is "d...I really don't understand why Vijay is "dismayed" at there being a "lot of confusion". 90 percent said that Nash Equilibrium is PPAD-complete, and as Vijay explains in his post, there are several natural, practical problems in Nash Equilibria that are PPAD-complete, such as an epsilon-relaxation of 3-player Nash. So, unless in his question to the audience Vijay specifically said "How hard is 3-player Nash, not the epsilon relaxation of 3-Nash, but 3-Nash itself?", then I'd say that those 90 percent gave a completely reasonable answer.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-52629144458218478192012-12-07T12:46:28.147-06:002012-12-07T12:46:28.147-06:00To hosts of this blog: don't you think that an...To hosts of this blog: don't you think that anonymous commenting should be banned here? The amount of venom and bitterness is sometimes astounding.Michal Kotowskihttp://www.blogger.com/profile/04141417129628388586noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-22477048417211074762012-12-06T17:49:33.316-06:002012-12-06T17:49:33.316-06:00Paul, when is Christofides beaten for TSP? Is it f...Paul, when is Christofides beaten for TSP? Is it for a special metric or a general metric? There were special metrics for which TSP was already broken, e.g., euclidean matrix. Some recent results broke it for graphical metric, but that is just one other metric.<br /><br />Just asking in case I missed some result.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-31695843423469343972012-12-06T17:31:52.472-06:002012-12-06T17:31:52.472-06:00Comments section has reached dangerous levels of d...Comments section has reached dangerous levels of debate fragmentation and social toxicity. Please gather your belongings, thank Prof. Vazirani for the nice open problems, and leave.FEMA ALERTnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-23567114658353901772012-12-06T16:58:59.884-06:002012-12-06T16:58:59.884-06:00This is some perverse reasoning (not limited to TC...This is some perverse reasoning (not limited to TCS, by the way) by which a position at a top-5 US university is a "success" while a position at any lower-ranked university (or a top-ranked university in Europe) is a "failure". Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-81139361121537262512012-12-06T16:51:56.713-06:002012-12-06T16:51:56.713-06:00Never seen this before.
How did it happen?Never seen this before. <br />How did it happen?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1793285514330374292012-12-06T16:37:55.028-06:002012-12-06T16:37:55.028-06:00+1 Paul Beame
Adding: PRIMES \in P solved by two ...+1 Paul Beame<br /><br />Adding: PRIMES \in P solved by two undergraduates (okay, plus one "older" guy)<br /><br />Amit CAChttp://www.blogger.com/profile/14911233583375020356noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-19428498756100282632012-12-06T16:31:08.265-06:002012-12-06T16:31:08.265-06:00As a youth across the hall in mathematical logic, ...As a youth across the hall in mathematical logic, the reason TCS turns me off is because there's the appearance that there's nothing really new or exciting, ever.<br /><br />As a mathematician, I'm interested in being multidisciplinary-- publishing papers in physics and biology and, well, everywhere. TCS seems to be 100% isolated in that sense. Yes, there are TCS papers published in other fields, but it seems every last one of them is a variation on "(insert something here) is NP-hard".<br /><br />You really, really, REALLY need to lose all the acronyms. If you can't think up a good name without resorting to acronyms, that's a sign the object is unworthy of study in the first place.<br /><br />You need to stop over-glorifying petty results-- you're the boy who cried wolf, especially here in the blogosphere. How about this. Before you start talking about groundbreaking-this and gamechanging-that, wait til the paper is accepted in a prestigious *NON-TCS* journal. Model yourselves more after Press and Dyson, 2012, "Iterated Prisonerâ€™s Dilemma contains strategies that<br />dominate any evolutionary opponent", PNAS. I suppose you laugh at this paper because it doesn't have 30-page proofs stuffed full of excruciatingly painful estimations. And yet, it does what a scientist is supposed to do: adds some real insight into how the universe works. TCS hasn't added any such insight in a very, very, very long time.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-65755956383521663922012-12-06T16:13:46.749-06:002012-12-06T16:13:46.749-06:00Which recent theory slot at a top 5 university do ...Which recent theory slot at a top 5 university do you think Madry should have gotten?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-22673406542097212102012-12-06T16:03:26.711-06:002012-12-06T16:03:26.711-06:00Anon at 3:07pm: I am not suggesting that these pr...Anon at 3:07pm: I am not suggesting that these problems are more important than others or that people should drop what they are doing and work on these problems. I am simply lamenting on the massive confusion that is out there due to which most people are not aware of an important new complexity class and its associated open problems. This is not good for the health of our field and you can see the adverse effects it has had already. I am simply trying to do my bit to correct this.<br /><br />Anon at 1:11pm: I agree that overemphasis on fads and flimsy results that will not stand the test of time is not the way to build a solid field. Clearly there have to be forays into new directions and ideas, but it is not good to lose sight of depth and quality.Vijay Vaziraninoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-46661883657786165112012-12-06T15:55:58.103-06:002012-12-06T15:55:58.103-06:00My impression is the converse: I am more often im...My impression is the converse: I am more often impressed by the amazing ways in which the youth of TCS continually DO solve those hard problems that have been around a long time - beating Christofides for TSP, finding a lower bound for ACC^0, improving the exponent for matrix multiplication, proving Yannakakis' extended LP formulation conjecture for TSP - to name just a few recent examples.Paul Beamehttp://www.cs.washington.edu/people/faculty/beamenoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-79944435969247706972012-12-06T15:07:11.004-06:002012-12-06T15:07:11.004-06:00There are a number of brilliant people comparable ...There are a number of brilliant people comparable to or better than Aleksander Madry that are not at a top 5 US institution. There are simply not enough jobs in 5 places. Young and old people should follow their interests and strengths, and good thing will happen in time. It is fine for Vijay to passionately advocate for his area/problems but there is no reason to believe that they are more central/important than many others that people are working on.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-16480330697758904402012-12-06T13:28:32.329-06:002012-12-06T13:28:32.329-06:00TL/DRTL/DRAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-71736324068509368252012-12-06T13:11:20.787-06:002012-12-06T13:11:20.787-06:00Vijay: Look at the perverse incentive system we (...Vijay: Look at the perverse incentive system we ("the old folks") have created. Aleksander Madry didn't get a position at a top 5 U.S. institution. In a hyper competitive job market, the young folks want jobs. Apparently it's easier to chase fads than work on hard problems.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-68329597373842134782012-12-06T12:49:58.359-06:002012-12-06T12:49:58.359-06:00They're working on their own insanely hard ope...They're working on their own insanely hard open problems, on which you old folks are not making any progress either.Jeff Ericksonhttp://www.blogger.com/profile/17633745186684887140noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-85497583525645947182012-12-06T10:56:29.727-06:002012-12-06T10:56:29.727-06:00When I attend STOC/FOCS/SODA, I often ask "Wh...When I attend STOC/FOCS/SODA, I often ask "Where are the old folks in TCS?" I guess they are too busy "doing all the work" to present papers in which they do all the work. Anonymousnoreply@blogger.com