tag:blogger.com,1999:blog-3722233.post1748696564571058785..comments2020-11-24T09:46:09.481-06:00Comments on Computational Complexity: AI Follows TheoryLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-3722233.post-33707630723098497982008-08-15T13:31:00.000-05:002008-08-15T13:31:00.000-05:00While there isn't much excuse for missing the Stoc...While there isn't much excuse for missing the Stockmeyer reference (the Valiant-Vazirani reference is there), one thing not to miss is that the algorithm that they succeeded with does not fit the Stockmeyer analysis (and that algorithm would have failed) because random parity constraints are too expensive to evaluate at every node of a backtracking SAT solver. The key to the effectiveness of the algorithm in the paper is that they get provable bounds with randomly chosen SMALL parities, which are constraints that are easy to evaluate repeatedly. The paper proves the new theoretical result that this is enough to get provable lower bounds on the number of solutions.<BR/><BR/>The bottom line of this should not be "AI people should be giving theory people appropriate credit" but rather that "powerful theoretical ideas may have powerful applications if one understands the applications well enough to suitably modify the theoretical ideas".Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-9774831612689147012008-08-14T17:40:00.000-05:002008-08-14T17:40:00.000-05:00John Mount's point about pdfs hidden behind locked...John Mount's point about pdfs hidden behind locked doors is valid, but a subject for a separate rant. The fact is that the AI researchers didn't do their homework and find Stockmeyer's seminal paper. No excuses for that. A simple google scholar search for "approximate counting" brings up Stockmeyer's paper on the first page of results. The same idea has been (over)-used in counting distinct elements in data stream algorithms (several rehashes of the same idea). What's disappointing is that one of the authors, Sabharwal, has a PhD in theory, having worked with Paul Beame at UW. What's extremely disappointing is that the reviewers for the conference didn't notice the rediscovery of Sipser/Valiant-Vazirani/Stockmeyer idea.<BR/><BR/>On the other hand, the hallmark of a great idea is that several people rediscover it, so we may forgive the authors of the AAAI paper.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-20751482530948710502008-08-14T16:36:00.000-05:002008-08-14T16:36:00.000-05:00Gomes, Sabharwal and Selman give a method only for...Gomes, Sabharwal and Selman give a method only for lower bounding the number of solutions, but do go on to demonstrate its practical viability for some reasonably interesting instances. Their method adapts the Valiant-Vazirani idea of halving the number of solutions in expectation by conjoining with a random parity function. However, for efficiency reasons they use parities of small length, and for these show that the halving is still true as an estimate from one side.<BR/><BR/>Presumably noone has yet shown that a known reduction of approximate counting to NP works as is in conjunction with an existing SAT solver, to solve some interesting instance of a problem.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-11800187504074583872008-08-14T13:16:00.000-05:002008-08-14T13:16:00.000-05:00Regarding John's comment, as a physicist I definit...Regarding John's comment, as a physicist I definitely agree. When I want to read a CS paper related to my work, it is often unavailable. When will theoretical computer scientists start actually using computers? That is, when will they create something like the arxiv?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-49838217502576722862008-08-14T12:18:00.000-05:002008-08-14T12:18:00.000-05:00There's a larger point here, which is that the exi...There's a larger point here, which is that the existence of good SAT solvers means that the boundaries of "feasible" computation have shifted to look a little more like P^NP than P. Except, of course, these solvers don't work on arbitrary length inputs, and they may have specific instance families where they fail. Understanding and characterizing this shift, and the limitations, feels like a theory problem. <BR/><BR/>For example, Richard Beigel's work on bounded queries might be a way to model a computer with a SAT solver. (assuming the SAT solver is only treated as a "black box", which matches how I see them used most of the time). <BR/>http://knight.cis.temple.edu/~beigel/papers/dissertation.htmlAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-21449420490720867572008-08-14T10:29:00.000-05:002008-08-14T10:29:00.000-05:00Although that link to the Stockmeyer paper cost mo...Although that link to the Stockmeyer paper cost money, a scan is available online for free: <A HREF="http://www.geocities.com/stockmeyer@sbcglobal.net/pubs.html" REL="nofollow">http://www.geocities.com/stockmeyer@sbcglobal.net/pubs.html</A>Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-46607709577045843792008-08-14T09:49:00.000-05:002008-08-14T09:49:00.000-05:00I'd say if us theorists want credit for our work (...I'd say if us theorists want credit for our work (and to prevent losing credit to re-invention) then we would should disseminate our work like the AI guys do. Most of the links to the theory work in your article are contents behind locked doors, which in this age of convenience may as well not exist. I can easily find, read and cite the AAAI work- I am not entirely happy citing locked-up work (even if I personally happen to have a copy). I have a medium-sized rant on this issue at: <A HREF="http://www.win-vector.com/blog/2008/04/i-know-i-am-the-one-being-a-jerk/" REL="nofollow">http://www.win-vector.com/blog/2008/04/i-know-i-am-the-one-being-a-jerk/</A> .Anonymousnoreply@blogger.com