Talk:Karloff–Zwick algorithm
Latest comment: 12 years ago by David Eppstein in topic The "trivial" algorithm
 | This article is rated Start-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | ||||||||||
| |||||||||||
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)
This article says nothing —Preceding unsigned comment added by 38.115.166.174 (talk) 21:45, 23 May 2009 (UTC)
The "trivial" algorithm
editWhy 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)
- 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)
- 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)
- 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)
- 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 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)
- Thanks, the changes look good to me. —David Eppstein (talk) 03:04, 8 September 2012 (UTC)
- 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 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)
- 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)
- 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)
