Inapproximability of Combinatorial Optimization Problems Luca Trevisan∗ arXiv:cs 0409043v1 [cs.CC] 24 SepJuly 27, 2004 - Probabilistically checkable proof - Document - PDFSEARCH.IO

First Page		Document Content
Date: 2008-02-01 14:51:28 Computational complexity theory Theory of computation Complexity classes NP-complete problems Mathematical optimization NP-hard problems MAX-3SAT NP Approximation algorithm Probabilistically checkable proof PCP theorem APX		Inapproximability of Combinatorial Optimization Problems Luca Trevisan∗ arXiv:cs/0409043v1 [cs.CC] 24 SepJuly 27, 2004 Add to Reading List Source URL: vigna.di.unimi.it Download Document from Source Website File Size: 460,93 KB Share Document on Facebook

	Assignment Testers: Towards a Combinatorial Proof of the PCP-Theorem∗ Irit Dinur† Omer Reingold DocID: 1mGw3 - View Document
	Inapproximability of Combinatorial Optimization Problems Luca Trevisan∗ arXiv:cs/0409043v1 [cs.CC] 24 SepJuly 27, 2004 DocID: 1mroB - View Document
	2015 Knuth Prize Citation for L´ aszl´ o Babai The 2015 Donald E. Knuth Prize is awarded to L´aszl´o Babai of the University of Chicago for his fundamental contributions to theoretical computer science, including alg DocID: 1kcj5 - View Document
	Annals of Mathematics, [removed]), 439–485 On the hardness of approximating minimum vertex cover By Irit Dinur and Samuel Safra* DocID: RF9X - View Document
	The Tale of the PCP Theorem How the search for the limits of computing led to the discovery of the unexpected power of proofs Dana Moshkovitz, MIT DocID: vxQs - View Document