Learning DNF over the uniform distribution using a quantum example oracle

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Learning DNF over the uniform distribution using a quantum example oracle

Full text

Pdf (1.03 MB)

Source

Annual Workshop on Computational Learning Theory archive
Proceedings of the eighth annual conference on Computational learning theory table of contents

Santa Cruz, California, United States

Pages: 118 - 127

Year of Publication: 1995

ISBN:0-89791-723-5

Authors

Nader H. Bshouty	University of Calgary
Jeffrey C. Jackson	Carnegie Mellon University

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGART: ACM Special Interest Group on Artificial Intelligence
University of California : University of California

Publisher

ACM New York, NY, USA

Bibliometrics

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

Additional Information:

references index terms collaborative colleagues

Tools and Actions:	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/225298.225312 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.

	AFP90	DanaAngluin, Michael Frazier, and Leonard PitL Learning conjunctions of Horn clauses. In Proceedings of the 30th Annual Symposium on Foundations of Computer Science, pages 186-192, 1990.
	AHP92	Howard Aizenstein, Lisa Hellerstein, and Leonard Pitt. Read-thrice DNF is hard to learn with membership and equivalence queries. In Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, pages 523- 532, 1992.
	AP91	Howard Aizenstein , Leonard Pitt, Exact learning of read-twice DNF formulas (extended abstract), Proceedings of the 32nd annual symposium on Foundations of computer science, p.170-179, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185366]
	AP92	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 [doi>10.1145/130385.130393]
	BB92a	Andr6 Berthiaume and Gilles Brassard. Oracle quantum computing. In Proceedings of the Workshop on the Physics of Computation, pages 195- 199. IEEE Press, 1992.
	BB92b	Andr~ Berthiaume and Gilles Brassard. The quantum challenge to structural complexity theory. In Proceedings of 7th IEEE Conference on Structure in Complexity Theory, pages 132-137, 1992.
	BFJ+94	Avrim Blum , Merrick Furst , Jeffrey Jackson , Michael Kearns , Yishay Mansour , Steven Rudich, Weakly learning DNF and characterizing statistical query learning using Fourier analysis, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.253-262, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195147]
	BR92	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 [doi>10.1145/129712.129748]
	Bru90	Jehoshua Bruck. Harmonic analysis of polynomial threshold functions. SIAM Journal of Discrete Mathematics, 3(2): 168-177, May 1990.
	Bsh93	Nader I-I. It~houty. Exact learning via the monotone theory. In Proceedings of the 34th Annual Symposium on Foundations of Computer Science, pages 302-311, 1993.
	BV93	Ethan Bernstein , Umesh Vazirani, Quantum complexity theory, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.11-20, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167097]
	Deu85	D. Deutsch. Quantum theory, the Church-Turing principle and the universal quantum computer. Proceesings of the Royal Society of London, A400:97-117, 1985.
	DJ92	D. Deutsch and R. Jozsa. Rapid solution of problems by quantum computation. Proceesings of the Royal Society of London, A439:553-558, 1992.
	Fre90	Yoav Freund, Boosting a weak learning algorithm by majority, Proceedings of the third annual workshop on Computational learning theory, p.202-216, August 06-08, 1990, Rochester, New York, United States
	Fre92	Yoav Freund, An improved boosting algorithm and its implications on learning complexity, Proceedings of the fifth annual workshop on Computational learning theory, p.391-398, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130429]
	FS95	Yoav Freund , Robert E. Schapire, A decision-theoretic generalization of on-line learning and an application to boosting, Proceedings of the Second European Conference on Computational Learning Theory, p.23-37, March 13-15, 1995
	GL89	O. Goldreich , L. A. Levin, A hard-core predicate for all one-way functions, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.25-32, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73010]
	Han91	Thomas R. Hancock, Learning 2u DNF formulas and ku decision trees, Proceedings of the fourth annual workshop on Computational learning theory, p.199-212, August 05-07, 1991, Santa Cruz, California, United States
	Jac94	Jeffrey Jackson. An efficient membership-query algorithm for learning DNF with respect to the uniform distribution. In Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994. 42-53.
	Kea93	Michael Kearns, Efficient noise-tolerant learning from statistical queries, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.392-401, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167200]
	KLPV87	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]
	KR93	Eyal Kushilevitz , Dan Roth, On learning visual concepts and DNF formulae, Proceedings of the sixth annual conference on Computational learning theory, p.317-326, July 26-28, 1993, Santa Cruz, California, United States [doi>10.1145/168304.168362]
	Sch90	Robert E. Schapire, The Strength of Weak Learnability, Machine Learning, v.5 n.2, p.197-227, Jun. 1990 [doi>10.1023/A:1022648800760]
	Sho94	Peter W. Shor. Algorithms for quantum computation: Discrete logarithms and factoring. In Proceedings of the 35th Annual Symposium on Foundations of Computer Science, pages 124- 134, 1994.
	Sim94	Daniel R. Simon. On the power of quantum computation. In Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994. To appear.
	Val84	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]
	Yao93	Andrew Chi-Chih Yao. Quantum circuit complexity. In Proceedings of the 34th Annual Symposium on Foundations of Computer Science, pages 352-361, 1993.