tag:blogger.com,1999:blog-3722233.post1140776917873866765..comments2024-06-13T23:23:44.643-05:00Comments on Computational Complexity: Foundational ... or simply a curiosity (Guest Post by Vijay Vazirani)Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger8125tag:blogger.com,1999:blog-3722233.post-413089382389156422010-12-25T05:04:18.216-06:002010-12-25T05:04:18.216-06:00Hi.
Dear Vazirani, Please help me.
I have a quest...Hi. <br />Dear Vazirani, Please help me.<br />I have a question. I'm confusing.<br />Chen at "complexity of single minded auction" proved that deciding about existence of walrasian equilibrium where customers are single minded is NP complete. But we know Walrasian equilibrium exists if and only if the efficient allocation and its linear programming relaxation has equal answers. Checking whether the solution of a linear program relaxation is integer or not could be done in polynomial time. I can not resolve this contradition. <br />Regards.<br />please post your answer to:<br />Parand@iust.ac.irAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-84858977257706815552010-06-23T00:25:18.387-05:002010-06-23T00:25:18.387-05:00STOC & FOCS gained prominence by accurately ev...STOC & FOCS gained prominence by accurately evaluating the potential behind computational ideas and hence becoming trend setters. As their role diminishes to that of trend followers, their luster is rapidly eroding. Perhaps the most effective trend setter today is the Internet.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-71220959848479012782010-06-22T14:07:09.235-05:002010-06-22T14:07:09.235-05:00Some of Vijay's work here has actually appeare...Some of Vijay's work here has actually appeared in STOC/FOCS, and if there are any important results, this is exactly the sort of thing STOC/FOCS would be interested in. I think not everyone is convinced this is a promising research direction. But they will be easily convinced by theorems, so anyone who thinks this is an important direction should pursue it.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-38423439559878309532010-06-22T13:50:23.980-05:002010-06-22T13:50:23.980-05:00How come so many people (me included) were
unaware...<i>How come so many people (me included) were<br />unaware of this important development?</i><br /><br />Perhaps you are too mainstream? ;-)<br /><br />The blog post is an update/summary of a speech V. Vazirani gave at the end of ICS 2010, to encourage the audience to pursue this line of research. I didn't mention it in my guest blog posts here about ICS because I didn't (and still don't) really understand what's at stake. I got the impression that some thought the larger community was incorrectly rejecting work in this area. I imagine the "larger community" might think the rejections were justified. If, in fact, the research direction is both important and "unknown," it provides evidence toward the importance of publicizing a broader scope of theoretical results than is currently being done through STOC and FOCS.Aaron Sterlingnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-24421464726616607462010-06-22T13:12:43.372-05:002010-06-22T13:12:43.372-05:00How come so many people (me included) were
unaware...How come so many people (me included) were<br />unaware of this important development?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-75249832500272773022010-06-22T11:50:37.464-05:002010-06-22T11:50:37.464-05:00Why do some convex programs have rational solution...Why do some convex programs have rational solutions? There must be some fundamental reason behind them.<br /><br />Geometrically, if there is a rational solution then one can find it (exactly) in polynomial time, so combinatorial algo should give some further insight.<br /><br />More broadly, is there a syntactic class of convex programs which have rational solutions, just like there are known classes of linear programs with integer solutions (e.g., totally unimodular matrices etc).<br /><br />In general, my guess is that whether a convex program is equivalent to a linear program should itself be a hard problem.Kamal Jainnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-61877384871303395092010-06-22T11:31:31.700-05:002010-06-22T11:31:31.700-05:00Which field do you work in?
If TCS, maybe your lic...Which field do you work in?<br />If TCS, maybe your license needs to be revoked.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-21639697983882884642010-06-22T11:07:10.520-05:002010-06-22T11:07:10.520-05:00What is a "combinatorial" algorithm? Thi...What is a "combinatorial" algorithm? This seems like a silly distinction.Anonymousnoreply@blogger.com