tag:blogger.com,1999:blog-3722233.post111504330528411283..comments2022-08-09T23:53:51.029-05:00Comments on Computational Complexity: Leonid Khachiyan (1952-2005)Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-3722233.post-1115226023178581812005-05-04T12:00:00.000-05:002005-05-04T12:00:00.000-05:00This is not a newspaper but a blog; so by definiti...This is not a newspaper but a blog; so by definition it is about whatever Lance feels like talking about. If you want to find out more about Khachiyan, read an obituary instead. Personally I think the quote from the NYT is very interesting. Lance, please ignore that mean comment!!!!!!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1115225853506868362005-05-04T11:57:00.000-05:002005-05-04T11:57:00.000-05:00He was incredibly humble. A great loss to the comm...He was incredibly humble. A great loss to the community.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1115147186260965562005-05-03T14:06:00.000-05:002005-05-03T14:06:00.000-05:00A mathematician who proved a beautiful and highly ...A mathematician who proved a beautiful and highly influential result has passed away. I find it disappointing that Lance uses this news to not reflect on the contributions of Khachiyan and the result but to <BR/>make some point about New York Times coverage.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1115129210946956072005-05-03T09:06:00.000-05:002005-05-03T09:06:00.000-05:00Or perhaps the words "is believed" are at issue. ...Or perhaps the words "is believed" are at issue. As I understand it, the article was written with little regard for the opinions of the actual scientists consulted...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1115062590455546352005-05-02T14:36:00.000-05:002005-05-02T14:36:00.000-05:00I later learned that article has become our standa...<I>I later learned that article has become our standard example of bad science writing, focusing more on an unlikely link to NP-complete problems instead of just describing the important theoretical problem Khachiyan's algorithm does solve.</I><BR/><BR/>I tend to disagree. In the hindsight, the article is rather true. SDP relaxations turned out to be pretty powerful approximation heuristics for NP-complete problems and in fact work well on average for some important ones (for example, optimal multiuser detection in CDMA channels). Since the ellipsoid method can be used to solve convex optimization problems like SDP, what's wrong with the assertion that "Mr. Khachiyan's method is believed to offer an approach for the linear programming of computers to solve so-called "traveling salesman" problems"? Only that they used the word "linear"? This is not a big deal, since SDP is in fact a generalization of LP.<BR/>PeterAnonymousnoreply@blogger.com