Talk:Karloff–Zwick algorithm

This article is rated Start-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects:

Computing This article is within the scope of WikiProject Computing, a collaborative effort to improve the coverage of computers, computing, and information technology on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.ComputingWikipedia:WikiProject ComputingTemplate:WikiProject ComputingComputing ??? This article has not yet received a rating on the project's importance scale.

i would love to either stub this or categorise this to give it some more exposure but what is this about? *puzzled* Tyhopho 22:09, 16 March 2006 (UTC)Reply

This article says nothing —Preceding unsigned comment added by 38.115.166.174 (talk) 21:45, 23 May 2009 (UTC)Reply

Why does this page say nothing about the well-known "trivial" algorithm which independently assigns each variable to true or false (with probability 1/2), and therefore satisfies 7/8 fraction of the clauses in expectation on any instance? That algorithm can also be easily derandomized by the textbook method of conditional expectations. Am I missing something here? Piyush (talk) 03:08, 4 September 2012 (UTC)Reply

Karloff and Zwick allow some of the clauses to have fewer than three variables; the trivial algorithm doesn't work in that case. —David Eppstein (talk) 03:16, 4 September 2012 (UTC)Reply

I think that's a fair point. Though given that Hastad's reduction (as far as I know) only needs clauses with three variables, I think we should still add what the actual motivation for this algorithm is in the article. Should I go ahead and do that? Piyush (talk) 02:22, 6 September 2012 (UTC)Reply

Sure, I think that makes sense. It would probably also be a good idea to clarify the difference in assumptions between the trivial algorithm and the Karloff–Zwick one, since currently we just say "3SAT" without explanation and different authors use that to mean different things. Usually it doesn't make much difference but here I guess it does. —David Eppstein (talk) 02:44, 6 September 2012 (UTC)Reply

OK, I made some changes: it'd be great if you could have a look. Also, I think there is still a slight inaccuracy in the way Hastad's result is stated (the Karloff-Zwick algorithm is optimal only if we assume RP ${\displaystyle \neq }$ NP, since it is a randomized algorithm). But I am not sure if spelling this out in full detail is the right way to fix this for an encyclopedia article. Piyush (talk) 02:39, 8 September 2012 (UTC)Reply

Thanks, the changes look good to me. —David Eppstein (talk) 03:04, 8 September 2012 (UTC)Reply