Fast approximate PCPs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Fast approximate PCPs

Full text

Pdf (935 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirty-first annual ACM symposium on Theory of computing table of contents

Atlanta, Georgia, United States

Pages: 41 - 50

Year of Publication: 1999

ISBN:1-58113-067-8

Authors

Funda Ergün	Bell Laboratories, 700 Mountain Avenue, Murray Hill, NJ
Ravi Kumar	IBM Almaden Research Center, 650 Harry Road, San Jose, CA
Ronitt Rubinfeld	Department of Computer Science, Cornell University, Ithaca, NY

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 13, Citation Count: 4

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/301250.301267 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.

	ALM+98	Sanjeev Arora , Carsten Lund , Rajeev Motwani , Madhu Sudan , Mario Szegedy, Proof verification and the hardness of approximation problems, Journal of the ACM (JACM), v.45 n.3, p.501-555, May 1998 [doi>10.1145/278298.278306]
	AS98	Sanjeev Arora , Shmuel Safra, Probabilistic checking of proofs: a new characterization of NP, Journal of the ACM (JACM), v.45 n.1, p.70-122, Jan. 1998 [doi>10.1145/273865.273901]
	BFL91	L. Bahai, L. Formow, and C. Lund. Non-deterministic exponential time has two-prover interactive protocols, Computational Complexity, pp. 3-40, 1991.
	BFLS90	L. Babai, L. Formow, C. Lurid, and M. Szegedy. Checking computations in potylogarithmic time. Proc. 31st Foundations of Computer Science, pp. 16-25, 1990.
	BGKW88	Michael Ben-Or , Shafi Goldwasser , Joe Kilian , Avi Widgerson, Multi-prover interactive proofs: how to remove intractability assumptions, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.113-131, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62223]
	BK95	Manuel Blum , Sampath Kannan, Designing programs that check their work, Journal of the ACM (JACM), v.42 n.1, p.269-291, Jan. 1995 [doi>10.1145/200836.200880]
	BLR93	Manuel Blum , Michael Luby , Ronitt Rubinfeld, Self-testing/correcting with applications to numerical problems, Journal of Computer and System Sciences, v.47 n.3, p.549-595, Dec. 1993 [doi>10.1016/0022-0000(93)90044-W]
	CMS99	C. Cachin, S. Micali, and M. Statler. Computationally private information retrieval with polylogarithmic communication. Manuscript, 1999.
	CLSY90	J. Y. Cai, R. Lipton, R. Sedgewick, and A. Yao. Towards uncheatable benchmarks. Proc. 8th Structure in Complexity Theory, pp. 2-11, 1993
	CEG95	Ran Canetti , Guy Even , Oded Goldreich, Lower bounds for sampling algorithms for estimating the average, Information Processing Letters, v.53 n.1, p.17-25, Jan. 13, 1995 [doi>10.1016/0020-0190(94)00171-T]
	CGKS95	B. Chor , O. Goldreich , E. Kushilevitz , M. Sudan, Private information retrieval, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.41, October 23-25, 1995
	Con91	Anne Condon, Space-bounded probabilistic game automata, Journal of the ACM (JACM), v.38 n.2, p.472-494, April 1991 [doi>10.1145/103516.128681]
	DKLR95	P. Dagum , R. Karp , M. Luby , S. Ross, An optimal algorithm for Monte Carlo estimation, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.142, October 23-25, 1995
	DS92	Cynthia Dwork , Larry Stockmeyer, Finite state verifiers I: the power of interaction, Journal of the ACM (JACM), v.39 n.4, p.800-828, Oct. 1992 [doi>10.1145/146585.146599]
	EK72	Jack Edmonds , Richard M. Karp, Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems, Journal of the ACM (JACM), v.19 n.2, p.248-264, April 1972 [doi>10.1145/321694.321699]
	EKK+98	Funda Ergün , Sampath Kannan , S. Ravi Kumar , Ronitt Rubinfeld , Mahesh Viswanathan, Spot-checkers, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.259-268, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276757]
	FGL+96	Uriel Feige , Shafi Goldwasser , Laszlo Lovász , Shmuel Safra , Mario Szegedy, Interactive proofs and the hardness of approximating cliques, Journal of the ACM (JACM), v.43 n.2, p.268-292, March 1996 [doi>10.1145/226643.226652]
	For89	L. Formow. The complexity of perfect zero-knowledge. Randomness and Computation, 5:327-343,1989.
	FL93	Lance Fortnow , Carsten Lund, Interactive proof systems and alternating time-space complexity, Theoretical Computer Science, v.113 n.1, p.55-73, May 24, 1993
	FRS94	Lance Fortnow , John Rompel , Michael Sipser, On the power of multi-prover interactive protocols, Theoretical Computer Science, v.134 n.2, p.545-557, Nov. 21, 1994 [doi>10.1016/0304-3975(94)90251-8]
	FS88	L. Formow and M. Sipser. Interactive proof systems with a tog space verifier. Manuscript, 1988.
	GLR+91	Peter Gemmell , Richard Lipton , Ronitt Rubinfeld , Madhu Sudan , Avi Wigderson, Self-testing/correcting for polynomials and for approximate functions, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.33-42, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103429]
	GGR98	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 [doi>10.1145/285055.285060]
	GR97	Oded Goldreich , Dana Ron, Property testing in bounded degree graphs, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.406-415, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258627]
	GR98	Oded Goldreich , Dana Ron, A sublinear bipartiteness tester for bounded degree graphs, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.289-298, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276767]
	GMR89	S. Goldwasser , S. Micali , C. Rackoff, The knowledge complexity of interactive proof systems, SIAM Journal on Computing, v.18 n.1, p.186-208, Feb. 1989 [doi>10.1137/0218012]
	GS86	S Goldwasser , M Sipser, Private coins versus public coins in interactive proof systems, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.59-68, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12137]
	KST97	Sanjeev Khanna , Madhu Sudan , Luca Trevisan, Constraint Satisfaction: The Approximability of Minimization Problems, Proceedings of the 12th Annual IEEE Conference on Computational Complexity, p.282, June 24-27, 1997
	Kil	J. Kilian. Zero-knowledge with logspace verifiers. Proc. 29th Foundations of Computer Science, pp. 25-35, 1988.
	Kil92	Joe Kilian, A note on efficient zero-knowledge proofs and arguments (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.723-732, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129782]
	Kil94	Joe Kilian, Improved Efficient Arguments (Preliminary Version), Proceedings of the 15th Annual International Cryptology Conference on Advances in Cryptology, p.311-324, August 27-31, 1995
	KO97	E. Kushilevitz , R. Ostrovsky, Replication is not needed: single database, computationally-private information retrieval, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.364, October 19-22, 1997
	Lip91	R. Lipton. New directions in testing. Proc. DIMACS Workshopon Dism Comp. and Cryptography, pp. 191-202, 199 I.
	LFKN90	Carsten Lund , Lance Fortnow , Howard Karloff, Algebraic methods for interactive proof systems, Journal of the ACM (JACM), v.39 n.4, p.859-868, Oct. 1992 [doi>10.1145/146585.146605]
	Mer90	Ralph C. Merkle, A certified digital signature, Proceedings on Advances in cryptology, p.218-238, July 1989, Santa Barbara, California, United States
	Mic94	S. Micali. CS proofs. Proc. 35th Foundations of Computer Science, pp. 436-453,1994.
	PST95	Serge A. Plotkin , David B. Shmoys , Éva Tardos, Fast approximation algorithms for fractional packing and covering problems, Proceedings of the 32nd annual symposium on Foundations of computer science, p.495-504, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185411]
	RS96	Ronitt Rubinfeld , Madhu Sudan, Robust Characterizations of Polynomials withApplications to Program Testing, SIAM Journal on Computing, v.25 n.2, p.252-271, February 1996 [doi>10.1137/S0097539793255151]
	Sch78	Thomas J. Schaefer, The complexity of satisfiability problems, Proceedings of the tenth annual ACM symposium on Theory of computing, p.216-226, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804350]
	Sha90	Adi Shamir, IP = PSPACE, Journal of the ACM (JACM), v.39 n.4, p.869-877, Oct. 1992 [doi>10.1145/146585.146609]
	Spi96	D. A. Spielman. Linear-time encodabte and decodable errorcorrecting codes. IEEE Trans. on Information Theory, 42(6):1723- 1732, 1996.

CITED BY 4

	Eli Ben-Sasson , Oded Goldreich , Prahladh Harsha , Madhu Sudan , Salil Vadhan, Robust pcps of proximity, shorter pcps and applications to coding, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Gunnar Andersson , Lars Engebretsen, Property testers for dense constraint satisfaction programs on finite domains, Random Structures & Algorithms, v.21 n.1, p.14-32, August 2002
	Bartosz Przydatek , Dawn Song , Adrian Perrig, SIA: secure information aggregation in sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA
	Haowen Chan , Adrian Perrig , Bartosz Przydatek , Dawn Song, SIA: Secure information aggregation in sensor networks, Journal of Computer Security, v.15 n.1, p.69-102, January 2007