Knowledge on the average—perfect, statistical and logarithmic

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Knowledge on the average—perfect, statistical and logarithmic

Full text

Pdf (1.18 MB)

Source

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

Las Vegas, Nevada, United States

Pages: 469 - 478

Year of Publication: 1995

ISBN:0-89791-718-9

Authors

William Aiello	Math and Cryptography Research Group, Bellcore, 445 South St. Morristown, NJ
Mihir Bellare	IBM T.J. Watson Research Center, PO Box 704, Yorktown Heights, NY
Ramarathnam Venkatesan	Math and Cryptography Research Group, Bellcore, 445 South St. Morristown, NJ

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): 11, Citation Count: 2

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

	ABV	W. AIBLLO, M. BELLARMAND R. VISNKATE.SAN. Knowl. edge on the average: perfect, statistical and logarith-mic. Manuscript available from authors.
	AH	William Aiello , Johan Hastad, Statistical zero-knowledge languages can be recognized in two rounds, Journal of Computer and System Sciences, v.42 n.3, p.327-345, June 1991 [doi>10.1016/0022-0000(91)90006-Q]
	B	L Babai, Trading group theory for randomness, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.421-429, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22192]
	BM	László Babai , Shlomo Moran, Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity class, Journal of Computer and System Sciences, v.36 n.2, p.254-276, April 1988 [doi>10.1016/0022-0000(88)90028-1]
	BP	Mihir Bellare , Erez Petrank, Making zero-knowledge provers efficient, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.711-722, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129781]
	BS	M. BBLLARB AND M. SUDAN. Improved non-approximability results. STOC 94.
	DDPY	A. DE SANTIS, G. DI CRBSCENZO, G. PERSIANO AND M. YuNc+. On monotone formula closure of SZK. FOCS 94.
	FK	Uri Feige , Joe Kilian, Two prover protocols: low error at affordable rates, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.172-183, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195128]
	F	L. FORTNOW. The Complexity of Perfect Zero-Knowledge. Advances in Computing Ftesearcb Vol. Ed. S. Micali, 1989.
	GP	Oded Goldreich , Erez Petrank, Quantifying knowledge complexity, Proceedings of the 32nd annual symposium on Foundations of computer science, p.59-68, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185349]
	GOP	Oded Goldreich , Rafail Ostrovsky , Erez Petrank, Computational complexity and knowledge complexity (extended abstract), Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.534-543, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195406]
	GMR	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]
	M	H. MAIER, Primes in Short Intervals, Michigan Math, 32, 1985, pp:221-225.
	St	Larry Stockmeyer, The complexity of approximate counting, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.118-126, December 1983 [doi>10.1145/800061.808740]

CITED BY 2

	Oded Goldreich , Salil Vadhan , Avi Wigderson, On interactive proofs with a laconic prover, Computational Complexity, v.11 n.1/2, p.1-53, January 2003
	Amit Sahai , Salil Vadhan, A complete problem for statistical zero knowledge, Journal of the ACM (JACM), v.50 n.2, p.196-249, March 2003