Talk:Karloff–Zwick algorithm

Computing Stub‑class

	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
Stub	This article has been rated as Stub-class on Wikipedia's content assessment scale.
???	This article has not yet received a rating on the project's importance scale.
	This article has been automatically rated by a bot or other tool as Stub-class because it uses a stub template. Please ensure the assessment is correct before removing the `\|auto=` parameter.

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]

The "trivial" algorithm

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]