Coherent functions and program checkers

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Coherent functions and program checkers

Full text

Pdf (858 KB)

Source

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

Baltimore, Maryland, United States

Pages: 84 - 94

Year of Publication: 1990

ISBN:0-89791-361-2

Author

A. C.-C. Yao

Department of Computer Science, Princeton University Princeton, New Jersey

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 31, Citation Count: 10

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

	AFK	M. Abadi , J. Feigenbaum , J Kilian, On hiding information form an oracle, Journal of Computer and System Sciences, v.39 n.1, p.21-50, Aug. 1989 [doi>10.1016/0022-0000(89)90018-4]
	AL	D. Angluin and D. Lichtenstein, "Provable security of cryptosystems: a survey," Technical Report TR-288, Yale University, October 1983.
	BeaF	Donald Beaver , J. Feigenbaum, Hiding instances in multioracle queries, Proceedings of the seventh annual symposium on Theoretical aspects of computer science, p.37-48, February 1990, Rouen, France
	BeiF	R. Beigel and J. Feigenbaum, "On the complexity of coherent functions," private communication, February 1990.
	BK	M. Blum , S. Kanna, Designing programs that check their work, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.86-97, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73015]
	BLR	M. Blum, M. Luby, and R. Rubinfeld, "Stronger checkers and general techniques for numerical problems," a talk presented in the DIMACS Workshop on Cryptography and Distributed Computing, Princeton, October 1989.
	FKN	J. Feigenbaum, S. Kannan, and N. Nisan, "Lower bounds on random-selfreducibility," to appear in Proceedings of Structures 90.
	F	M.L. Fredman, "How good is the information theory bound in sorting," Theoretical Computer Science 1(1976), 355-361.
	GGM	Oded Goldreich , Shafi Goldwasser , Silvio Micali, How to construct random functions, Journal of the ACM (JACM), v.33 n.4, p.792-807, Oct. 1986 [doi>10.1145/6490.6503]
	H	M.E. Hellman, "A cryptanalytic timememory trade-off," IEEE Transactions on Information Theory 26 (1980), 401-405.
	KK	C. Kenyon-Mathieu , V. King, Verifying partial orders, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.367-374, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73042]
	K	V. King, "An optimal randomized algorithm for set-maxima," private communication, 1989.
	L	R.J. Lipton, "New directions in testing," manuscript and a talk presented in the DIMACS Workshop on Cryptography and Distributed Computing, Princeton, October 1989.
	MT	Udi Manber , Martin Tompa, The complexity of problems on probabilistic, nondeterministic, and alternating decision trees, Journal of the ACM (JACM), v.32 n.3, p.720-732, July 1985 [doi>10.1145/3828.3838]
	Sch	A. Schonhage, "The production of partial orders," Asterisque 38-39 (1976), 229-246.
	SS	A. Shamir and J. Spencer, private communication, 1979.
	Y1	A.C. Yao, "Probabilistic computations: towards a unified measure of complexity," Proceedings 18th Annual IEEE Symposium on Foundations of Computer Science, October 1977, 222-227.
	Y2	Andrew Chi-Chih Yao, On the complexity of partial order productions, SIAM Journal on Computing, v.18 n.4, p.679-689, Aug. 1989 [doi>10.1137/0218047]

CITED BY 10

	Yair Frankel , Peter Gemmell , Moti Yung, Witness-based cryptographic program checking and robust function sharing, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.499-508, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	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
	Amos Fiat , Moni Naor, Rigorous time/space tradeoffs for inverting functions, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.534-541, May 05-08, 1991, New Orleans, Louisiana, United States
	Hal Wasserman , Manuel Blum, Software reliability via run-time result-checking, Journal of the ACM (JACM), v.44 n.6, p.826-849, Nov. 1997
	Marc Fischlin, Cryptographic limitations on parallelizing membership and equivalence queries with applications to random-self-reductions, Theoretical Computer Science, v.268 n.2, p.199-219, 17 October 2001
	Yishay Mansour , Noam Nisan , Uzi Vishkin, Trade-offs between communication throughput and parallel time, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.372-381, May 23-25, 1994, Montreal, Quebec, Canada
	Dwight S. Wilson , Gregory F. Sullivan , Gerald M. Masson, Certification of Computational Results, IEEE Transactions on Computers, v.44 n.7, p.833-847, July 1995
	Giovanni Di Crescenzo, Sharing one secret vs. sharing many secrets, Theoretical Computer Science, v.295 n.1-3, p.123-140, 24 February 2003
	Christian Glaßer , Mitsunori Ogihara , A. Pavan , Alan L. Selman , Liyu Zhang, Autoreducibility, mitoticity, and immunity, Journal of Computer and System Sciences, v.73 n.5, p.735-754, August, 2007
	Alexander Golynski, Cell probe lower bounds for succinct data structures, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.625-634, January 04-06, 2009, New York, New York