Recycling queries in PCPs and in linearity tests (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Recycling queries in PCPs and in linearity tests (extended abstract)

Full text

Pdf (1.15 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirtieth annual ACM symposium on Theory of computing table of contents

Dallas, Texas, United States

Pages: 299 - 308

Year of Publication: 1998

ISBN:0-89791-962-9

Author

Luca Trevisan

MIT Laboratory for Computer Science, Room NE43-371, 545 Technology Square, Cambridge, MA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 18, Citation Count: 7

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/276698.276769 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and hardness of approximation problems. In Proc. of the 33rd IEEE FOCS, pages 14-23, 1992.
	2	S. Arora and S. Safra. Probabilistic checking of proofs; a new characterization of NP. In Proc. ofthe 33rdlEEE FOCS, pages 2-13, 1992.
	3	M. Bellare. Proof checking and approximation: Towards fight results. Sigact News, 27(1), 1996.
	4	M. Bellare, D. Coppersmith, J. H~stad, M. Kiwi, and M. Sudan. Linearity testing over characteristic two. IEEE Trans. on Information Theory, 42(6): 1781-1795, 1996.
	5	M. Bellare, O. Goldreich, and M. Sudan. Free bits, PCP's and non-approximability- towards fight results (5th version). Technical Report TR95-24, Electronic Colloquium on Computational Complexity, 1997. Preliminary version in Proc. of FOCS'95.
	6	M. Bellare , S. Goldwasser , C. Lund , A. Russeli, Efficient probabilistically checkable proofs and applications to approximations, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.294-304, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167174]
	7	Mihir Bellare , Madhu Sudan, Improved non-approximability results, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.184-193, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195129]
	8	M. Blum , M. Luby , R. Rubinfeld, Self-testing/correcting with applications to numerical problems, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.73-83, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100225]
	9	D. Coppersmith. Unpublished notes, 1990.
	10	Nadia Creignou, A dichotomy theorem for maximum generalized satisfiability problems, Journal of Computer and System Sciences, v.51 n.3, p.511-522, Dec. 1995 [doi>10.1006/jcss.1995.1087]
	11	Johan Håstad, Testing of the long code and hardness for clique, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.11-19, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237820]
	12	J. Hastad, Clique is hard to approximate within n1-, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.627, October 14-16, 1996
	13	Johan Håstad, Some optimal inapproximability results, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.1-10, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258536]
	14	Howard Karloff , Uri Zwick, A 7/8-Approximation Algorithm for MAX 3SAT?, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.406, October 19-22, 1997
	15	S. Khanna, R. Motwani, M. Sudan, and U. Vazirani. On syntactic versus computational views of approximability. In Proc. of the 35th IEEE FOC$, pages 819-830, 1994.
	16	Sanjeev Khanna , Madhu Sudan , David P. Williamson, A complete classification of the approximability of maximization problems derived from Boolean constraint satisfaction, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.11-20, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258538]
	17	Marcos Kiwi , Michael Sipser, Probabilistically checkable proofs and the testing of hadamard-like codes, 1996
	18	Christos Papadimitriou , Mihalis Yannakakis, Optimization, approximation, and complexity classes, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.229-234, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62233]
	19	Ran Raz, A parallel repetition theorem, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.447-456, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225181]
	20	M. Seres, L. Trevisan, and E Xhafa. The parallel approximability of non-boolean constraint satisfaction and restricted integer linear programming. In Proc. of the 15th STACS, 1998. To appear.
	21	M. Sudan and L. Trevisan. Unpublished Notes, February 1998.
	22	Luca Trevisan, Positive Linear Programming, Parallel Approximation and PCP's, Proceedings of the Fourth Annual European Symposium on Algorithms, p.62-75, September 25-27, 1996
	23	Luca Trevisan, Approximating Satisfiable Satisfiability Problems (Extended Abstract), Proceedings of the 5th Annual European Symposium on Algorithms, p.472-485, September 15-17, 1997
	24	L. Trevisan. Recycling queries in PCPs and in linearity tests. Technical Report TR98-07, Electronic Colloquium on Computational Complexity, January 1998.
	25	L. Trevisan , G. B. Sorkin , M. Sudan , D. P. Williamson, Gadgets Approximation, and Linear Programming, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.617, October 14-16, 1996
	26	Uri Zwick, Approximation algorithms for constraint satisfaction problems involving at most three variables per constraint, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.201-210, January 25-27, 1998, San Francisco, California, United States

CITED BY 7

	Oded Goldreich , Shari Goldwasser , Dana Ron, Property testing and its connection to learning and approximation, Journal of the ACM (JACM), v.45 n.4, p.653-750, July 1998
	Eran Halperin , Uri Zwick, Combinatorial approximation algorithms for the maximum directed cut problem, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.1-7, January 07-09, 2001, Washington, D.C., United States
	Marcos Kiwi , Frédéric Magniez , Miklos Santha, Exact and approximate testing/correcting of algebraic functions: a survey, Theoretical aspects of computer science: advanced lectures, Springer-Verlag New York, Inc., New York, NY, 2002
	Alex Samorodnitsky , Luca Trevisan, A PCP characterization of NP with optimal amortized query complexity, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.191-199, May 21-23, 2000, Portland, Oregon, United States
	Oded Goldreich, Property testing in massive graphs, Handbook of massive data sets, Kluwer Academic Publishers, Norwell, MA, 2002
	Alex Samorodnitsky, Low-degree tests at large distances, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
	Lars Engebretsen , Jonas Holmerin, More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP, Random Structures & Algorithms, v.33 n.4, p.497-514, December 2008