Talk:PCP theorem

Mathematics High‑priority

	Mathematics portal This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics 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.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics articles
High	This article has been rated as High-priority on the project's priority scale.

Computer science High‑importance

This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles 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.Computer scienceWikipedia:WikiProject Computer scienceTemplate:WikiProject Computer scienceComputer science articles

High

This article has been rated as High-importance on the project's importance scale.

Things you can help WikiProject Computer science with:

Here are some tasks awaiting attention:

Article requests :
- Requested articles/Applied arts and sciences/Computer science, computing, and Internet
Cleanup :
- Computer science articles needing attention
- Computer science articles needing expert attention
Copyedit :
- Computing
Expand :
- Computer science
Infobox :
- Computer science articles without infoboxes
Maintain :
- Timeline of computing 2020–present
Photo :
- Find pictures for the biographies of computer scientists (see List of computer scientists)
- Computing articles needing images
Stubs :
- Computer science stubs
Unreferenced :
- WikiProject Computer science/Unreferenced BLPs
Project-related :
- Tag all relevant articles in Category:Computer science and sub-categories with {{WikiProject Computer science}}

Proofs

I feel that the proof of Lemma 1 is unnecessarily detailed. Also, the proof sketch of Lemma 2 skips the main point completely (!) in favor of elaborating the trivial equivalence between the PCP theorem and reductions to Max 3SAT in an unclear way. Dinur's proof should be cited and some sort of intuition given. It seems misleading to give lots of details on trivial pieces of the proof without saying anything about the interesting part of the proof. 131.215.48.236 (talk) 01:24, 9 July 2008 (UTC)[reply]

Irit Dinur

Why Irit Dinur's is worth mentioning? Where are the third-party references which demonstrate its notability? - Altenmann >t 21:55, 21 July 2009 (UTC)[reply]

See, for example, this survey Bravely, Moderately: A Common Theme in Four Recent Results, and also this one: On Dinur's Proof of the PCP Theorem. Also, beside the fact that the paper appeared in a really prestigious journal (J. ACM), it received the STOC/FOCS best paper award in 2006. Probably it would be valuable to explain in a few words why the new proof is worth mentioning (one reason is that it is by far simpler than the original one). Hermel (talk) 22:58, 21 July 2009 (UTC)[reply]

Universal Constant

What is know about the mentioned universal constant K? Have we named it? 195.77.88.65 (talk) 13:23, 23 March 2014 (UTC)[reply]

Explanation about formalization of maximum fraction problem

I don't get how the promise problem presented relates to the problem of approximating the "maximum fraction of satisfiable constraints". I think for the discussion to make sense, the problems should be equivalent, or at least you should be able to reduce the promise problem to the approximation problem. I don't see how an approximate value for the maximum can help you solve the promise problem. Suppose a = 0.9 and suppose the for a particular \Phi the approximate value for the maximum is m = 0.9 +/- 0.2 . Then you won't be able to tell whether \Phi is in L_{yes} (m=1) or whether \Phi is in L_{no} (any m < 0.9). Maybe it should explain better what criterion for approximation is this using? 92.25.22.177 (talk) 19:22, 5 April 2015 (UTC)[reply]

Problems with the History

As far as I can tell, Feige, Goldwasser, Lund, Safra, and Szegedy did not publish any papers together in 1991. However, "Feige, Goldwasser, Lund, Safra, and Szegedy (1991)" is referenced in the article (with no references link I might add). U Feige, S Goldwasser, L Lovász, S Safra, and M Szegedy published "Approximating clique is almost NP-complete" in the same year; if Lund was credited in place of Lovász, this citation would make sense. Previously, the 1998 paper "Probabilistic checking of proofs: A new characterization of NP" by Arora and Safra was cited, while giving the year as 1992. I believe this to have been a miscitation, and have cited their 1992 paper, "Approximating clique is NP-complete" in its place. With this in mind, it certainly seems as though the 1991 paper by Feige, S Goldwasser, L Lovász, S Safra, and M Szegedy was the intended citation. --Cyrus Cousins (talk) 20:50, 30 April 2016 (UTC)[reply]