When won't membership queries help?

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

When won't membership queries help?

Full text

Pdf (1.21 MB)

Source

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

New Orleans, Louisiana, United States

Pages: 444 - 454

Year of Publication: 1991

ISBN:0-89791-397-3

Authors

Dana Angluin	Yale Univ., New Haven, CT
Michael Kharitonov	Stanford Univ., Stanford, CA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 32, Citation Count: 26

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/103418.103420 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	Dana Angluin, Learning regular sets from queries and counterexamples, Information and Computation, v.75 n.2, p.87-106, November 1, 1987 [doi>10.1016/0890-5401(87)90052-6]
	2	D. Angluin, M. Frazier, and L. Pitt. Learning conjunctions of horn clauses. In Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science, pages 186-192. IEEE, 1990.
	3	Dana Angluin , Lisa Hellerstein , Marek Karpinski, Learning Read-Once Formulas with Queries, University of California at Berkeley, Berkeley, CA, 1989
	4	Mihir Bellare , Silvio Micali, How to sign given any trapdoor function, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.32-42, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62216]
	5	M. Blum, A. DeSantis, S. Micali, and G. Persiano. Non-interactive zero knowledge. Technical report, MIT/LCS/TM-430, 1990.
	6	Manuel Blum , Paul Feldman , Silvio Micali, Non-interactive zero-knowledge and its applications, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.103-112, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62222]
	7	Danny Dolev , Cynthia Dwork , Moni Naor, Non-malleable cryptography, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.542-552, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103474]
	8	U. Feige, D. Lapidot, and A. Shamir. Multiple noninteractive zero knowledge proofs based on a single random string. In Proceedzngs of the 31st Annual Symposium on Foundations of Computer Science, pages 308-317, 1990.
	9	Oded Goldreich, Two remarks concerning the Goldwasser-Micali-Rivest signature scheme, Proceedings on Advances in cryptology---CRYPTO '86, p.104-110, January 1987, Santa Barbara, California, United States
	10	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]
	11	Shafi Goldwasser , Silvio Micali , Ronald L. Rivest, A digital signature scheme secure against adaptive chosen-message attacks, SIAM Journal on Computing, v.17 n.2, p.281-308, April 1988 [doi>10.1137/0217017]
	12	T. Hancock. Learning 2#dnf formulas and k# decision trees. Extended Abstract, Harvard University, 1990.
	13	David Haussler , Michael Kearns , Nick Littlestone , Manfred K. Warmuth, Equivalence of models for polynomial learnability, Proceedings of the first annual workshop on Computational learning theory, p.42-55, August 03-05, 1988, MIT, Cambridge, Massachusetts, United States
	14	D. Haussler, N. Littlestone, and M. Warmuth. Predicting {0, 1}-functions on randomly drawn points. In Proc. 291h Symposium on Foundations of Computer Science, pages 100-109. IEEE, 1988.
	15	M. Kearns , M. Li , L. Pitt , L. Valiant, On the learnability of Boolean formulae, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.285-295, January 1987, New York, New York, United States [doi>10.1145/28395.28426]
	16	M. Kearns , L. G. Valiant, Crytographic limitations on learning Boolean formulae and finite automata, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.433-444, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73049]
	17	Nick Littlestone, Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm, Machine Learning, v.2 n.4, p.285-318, April 1988 [doi>10.1023/A:1022869011914]
	18	M. Naor , M. Yung, Universal one-way hash functions and their cryptographic applications, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.33-43, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73011]
	19	M. Naor , M. Yung, Public-key cryptosystems provably secure against chosen ciphertext attacks, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.427-437, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100273]
	20	L. Pitt and M. Warmuth. Reductions among prediction problems" On the difficulty of predicting automata. In Proceedings of the Third Annual Structure in Complexity Theory Conference, pages 60-69. IEEE Computer Society Press, 1988.
	21	J. Rompel, One-way functions are necessary and sufficient for secure signatures, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.387-394, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100269]
	22	R. E. Schapire. The strength of weak learnability. In Proceedings of the 30lh Annual Symposium on Foundations of Computer Science, pages 28-33. IEEE, 1989.
	23	L. G. Valiant, A theory of the learnable, Communications of the ACM, v.27 n.11, p.1134-1142, Nov. 1984 [doi>10.1145/1968.1972]

CITED BY 26

	Avrim Blum , Steven Rudich, Fast learning of k-term DNF formulas with queries, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.382-389, May 04-06, 1992, Victoria, British Columbia, Canada
	Dana Angluin, Computational learning theory: survey and selected bibliography, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.351-369, May 04-06, 1992, Victoria, British Columbia, Canada
	Ronald L. Rivest , Yiqun Lisa Yin, Being taught can be faster than asking questions, Proceedings of the eighth annual conference on Computational learning theory, p.144-151, July 05-08, 1995, Santa Cruz, California, United States
	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
	Howard Aizenstein , Leonard Pitt, Exact learning of read-k disjoint DNF and not-so-disjoint DNF, Proceedings of the fifth annual workshop on Computational learning theory, p.71-76, July 27-29, 1992, Pittsburgh, Pennsylvania, United States
	Nader H. Bshouty , Thomas R. Hancock , Lisa Hellerstein, Learning Boolean read-once formulas with arbitrary symmetric and constant fan-in gates, Proceedings of the fifth annual workshop on Computational learning theory, p.1-15, July 27-29, 1992, Pittsburgh, Pennsylvania, United States
	Moni Naor, Evaluation may be easier than generation (extended abstract), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.74-83, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	Rodney G. Downey , Patricia A. Evans , Michael R. Fellows, Parameterized learning complexity, Proceedings of the sixth annual conference on Computational learning theory, p.51-57, July 26-28, 1993, Santa Cruz, California, United States
	Yishay Mansour, An O(nlog log n) learning algorithm for DNF under the uniform distribution, Proceedings of the fifth annual workshop on Computational learning theory, p.53-61, July 27-29, 1992, Pittsburgh, Pennsylvania, United States
	Scott Decatur , Oded Goldreich , Dana Ron, Computational sample complexity, Proceedings of the tenth annual conference on Computational learning theory, p.130-142, July 06-09, 1997, Nashville, Tennessee, United States
	Lisa Hellerstein , Vijay Raghavan , Krishnan Pillaipakkamnatt , Dawn Wilkins, How many queries are needed to learn?, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.190-199, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Michael Kharitonov, Cryptographic hardness of distribution-specific learning, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.372-381, May 16-18, 1993, San Diego, California, United States
	Michael Kharitonov, Cryptographic lower bounds for learnability of Boolean functions on the uniform distribution, Proceedings of the fifth annual workshop on Computational learning theory, p.29-36, July 27-29, 1992, Pittsburgh, Pennsylvania, United States
	Dana Angluin , Lisa Hellerstein , Marek Karpinski, Learning read-once formulas with queries, Journal of the ACM (JACM), v.40 n.1, p.185-210, Jan. 1993
	Sally A. Goldman , H. David Mathias, Learning k-term DNF formulas with an incomplete membership oracle, Proceedings of the fifth annual workshop on Computational learning theory, p.77-84, July 27-29, 1992, Pittsburgh, Pennsylvania, United States
	Yishay Mansour , Mariano Schain, Learning with maximum-entropy distributions, Proceedings of the tenth annual conference on Computational learning theory, p.201-210, July 06-09, 1997, Nashville, Tennessee, United States
	Peter Auer , Philip M. Long, Simulating access to hidden information while learning, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.263-272, May 23-25, 1994, Montreal, Quebec, Canada
	Lisa Hellerstein , Krishnan Pillaipakkamnatt , Vijay Raghavan , Dawn Wilkins, How many queries are needed to learn?, Journal of the ACM (JACM), v.43 n.5, p.840-862, Sept. 1996
	Avrim Blum , Roni Khardon , Eyal Kushilevitz , Leonard Pitt , Dan Roth, On learning Read-k-Satisfy-j DNF, Proceedings of the seventh annual conference on Computational learning theory, p.110-117, July 12-15, 1994, New Brunswick, New Jersey, United States
	Nader H. Bshouty , Christino Tamon , David K. Wilson, On learning width two branching programs (extended abstract), Proceedings of the ninth annual conference on Computational learning theory, p.224-227, June 28-July 01, 1996, Desenzano del Garda, Italy
	Michael Kearns , Leslie Valiant, Cryptographic limitations on learning Boolean formulae and finite automata, Journal of the ACM (JACM), v.41 n.1, p.67-95, Jan. 1994
	Henning Fernau, Even linear simple matrix languages: formal language properties and grammatical inference, Theoretical Computer Science, v.289 n.1, p.425-456, 23 October 2002
	Nader H. Bshouty , Vitaly Feldman, On using extended statistical queries to avoid membership queries, The Journal of Machine Learning Research, 2, p.359-395, 3/1/2002
	Yishay Mansour , Mariano Schain, Learning with Maximum-Entropy Distributions, Machine Learning, v.45 n.2, p.123-145, November 2001
	Michael Frazier , Sally Goldman , Nina Mishra , Leonard Pitt, Learning from a consistently ignorant teacher, Proceedings of the seventh annual conference on Computational learning theory, p.328-339, July 12-15, 1994, New Brunswick, New Jersey, United States
	György Turán, Lower bounds for PAC learning with queries, Proceedings of the sixth annual conference on Computational learning theory, p.384-391, July 26-28, 1993, Santa Cruz, California, United States