Search results for "PCP theorem"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
2	Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, Peter W. Shor	The Power of Unentanglement.	IEEE Conference on Computational Complexity	2008	DBLP DOI BibTeX RDF	QMA, 3SAT, PCP Theorem, quantum computing, additivity, entanglement
2	Tianyan Deng, Daoyun Xu	NP-Completeness of (k-SAT, r-UNk-SAT) and (LSAT>=k, r-UNLSAT>=k).	FAW	2008	DBLP DOI BibTeX RDF	PCP theorem, linear CNF formula, LSAT, minimal unsatisfiable(MU) formula, NP-completeness, reduction
2	Irit Dinur	The PCP theorem by gap amplification.	J. ACM	2007	DBLP DOI BibTeX RDF	Gap amplification, PCP
2	Irit Dinur	The PCP theorem by gap amplification.	STOC	2006	DBLP DOI BibTeX RDF	gap amplification, PCP
2	Klaus Meer	Transparent Long Proofs: A First PCP Theorem for NPR.	Foundations of Computational Mathematics	2005	DBLP DOI BibTeX RDF	Real number complexity, Verifiers, Probabilistically checkable proofs
2	Jin-yi Cai, Hong Zhu	Progress in Computational Complexity Theory.	J. Comput. Sci. Technol.	2005	DBLP DOI BibTeX RDF	computational complexity theory, PCP theorem, logspace complexity, Reingold's theorem, GAP problem, complexity of lattice problems, worst-case to average-case reductions, extractors, pseudorandomness, inapproximability, primality testing, theoretical computer science, holographic algorithms
2	Klaus Meer	Transparent Long Proofs: A First PCP Theorem for NPR.	ICALP	2004	DBLP DOI BibTeX RDF
2	Irit Dinur, Omer Reingold	Assignment Testers: Towards a Combinatorial Proof of the PCP-Theorem.	FOCS	2004	DBLP DOI BibTeX RDF
2	Volker Heun, Wolfgang Merkle, Ulrich Weigand	Proving the PCP-Theorem.	Lectures on Proof Verification and Approximation Algorithms	1997	DBLP DOI BibTeX RDF
1	Dana Moshkovitz	The tale of the PCP theorem.	ACM Crossroads	2012	DBLP DOI BibTeX RDF
1	Ran Raz	Quantum Information and the PCP Theorem.	Algorithmica	2009	DBLP DOI BibTeX RDF	Quantum interactive proofs, Quantum advice, Quantum computation, Probabilistically checkable proofs, Quantum information, Low degree test
1	Dorit Aharonov, Itai Arad, Zeph Landau, Umesh V. Vazirani	The detectability lemma and quantum gap amplification.	STOC	2009	DBLP DOI BibTeX RDF	QMA, detectability lemma, gap amplification, local hamiltonians, quantum computation, PCP
1	Irit Dinur	PCPs with small soundness error.	SIGACT News	2008	DBLP DOI BibTeX RDF
1	Dana Moshkovitz, Ran Raz	Two Query PCP with Sub-Constant Error.	FOCS	2008	DBLP DOI BibTeX RDF
1	Tianyan Deng, Daoyun Xu	Hardness of Approximation Algorithms on k-SAT and (k, s)-SAT Problems.	ICYCS	2008	DBLP DOI BibTeX RDF
1	Venkatesan Guruswami, Valentine Kabanets	Hardness Amplification via Space-Efficient Direct Products.	Computational Complexity	2008	DBLP DOI BibTeX RDF	94B35, 68Q25, 94B05, 68P30, Subject classification. 68Q17
1	Irit Dinur, Omer Reingold	Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem.	SIAM J. Comput.	2006	DBLP DOI BibTeX RDF
1	Jaikumar Radhakrishnan	Gap Amplification in PCPs Using Lazy Random Walks.	ICALP	2006	DBLP DOI BibTeX RDF
1	Venkatesan Guruswami, Valentine Kabanets	Hardness Amplification Via Space-Efficient Direct Products.	LATIN	2006	DBLP DOI BibTeX RDF	error-correcting codes, expanders, Direct products, hardness amplification
1	Irit Dinur	The PCP theorem by gap amplification	Electronic Colloquium on Computational Complexity (ECCC)	2005	DBLP BibTeX RDF
1	Ran Raz	Quantum Information and the PCP Theorem	Electronic Colloquium on Computational Complexity (ECCC)	2005	DBLP BibTeX RDF
1	Ran Raz	Quantum Information and the PCP Theorem.	FOCS	2005	DBLP DOI BibTeX RDF
1	Subhash Khot	On the Unique Games Conjecture.	FOCS	2005	DBLP DOI BibTeX RDF
1	Klaus Meer	On Some Relations Between Approximation Problems and PCPs over the Real Numbers.	CiE	2005	DBLP DOI BibTeX RDF
1	Jonas Holmerin, Subhash Khot	A new PCP outer verifier with applications to homogeneous linear equations and max-bisection.	STOC	2004	DBLP DOI BibTeX RDF	max-bisection, hardness of approximation, linear equations, PCPs
1	Oded Goldreich, Shmuel Safra	A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem.	SIAM J. Comput.	2000	DBLP DOI BibTeX RDF
1	Venkatesan Guruswami, Sanjeev Khanna	On the Hardness of 4-Coloring a 3-Colorable Graph. (PDF / PS)	IEEE Conference on Computational Complexity	2000	DBLP DOI BibTeX RDF	Graph Coloring, Hardness of approximation, PCP
1	Oded Goldreich, Shmuel Safra	A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem.	RANDOM	1997	DBLP DOI BibTeX RDF
1	Oded Goldreich, Shmuel Safra	A Combinatorial Consistency Lemma with application to the PCP Theorem	Electronic Colloquium on Computational Complexity (ECCC)	1996	DBLP BibTeX RDF