tag:blogger.com,1999:blog-3722233.post5709989275400936523..comments2020-02-19T03:43:18.369-05:00Comments on Computational Complexity: NOT So PowerfulLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger2125tag:blogger.com,1999:blog-3722233.post-57248266132901201682017-09-01T07:14:46.922-04:002017-09-01T07:14:46.922-04:00More details about Tardos' function can be fou...More details about Tardos' function can be found <a href="http://www.thi.informatik.uni-frankfurt.de/~jukna/boolean/tardos.html" rel="nofollow">here</a>.Stasyshttp://www.thi.informatik.uni-frankfurt.de/~jukna/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-37581140375760424432017-08-31T11:12:34.338-04:002017-08-31T11:12:34.338-04:00The Shannon capacity is interesting but I feel thi...The Shannon capacity is interesting but I feel this post is misleading in several ways by trying very hard to avoid talking about SDPs and the Lovasz theta function. Tardos's function is in fact the Lovasz theta function, appropriately rounded, and I don't think the theta function approximates Shannon capacity to any useful factor in general. So I don't think it's true that we know how to use the ellipsoid method to approximate Shannon capacity. However, we know how to solve SDPs efficiently, and the theta function is the solution to an SDP. It's also monotone and distinguishes k-cliques from complete (k+1)-partite graphs, which is all that's needed.Sashohttps://www.blogger.com/profile/09380390882603977159noreply@blogger.com