The query complexity of finding local minima in the lattice

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The query complexity of finding local minima in the lattice

Full text

Pdf (1.25 MB)

Source

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

Madison, Wisconsin, United States

Pages: 294 - 302

Year of Publication: 1998

ISBN:1-58113-057-0

Authors

Amos Beimel	Division of Engineering & Applied Sciences, Harvard University, 40 Oxford St., Cambridge, MA
Felix Geller	Computer Science Department, Technion, Haifa 32000, Israel
Eyal Kushilevitz	Computer Science Department, Technion, Haifa 32000, Israel

Sponsors

University of Wisconsin : University of Wisconsin
UC @ Santa Cruz : UC @ Santa Cruz
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGART: ACM Special Interest Group on Artificial Intelligence

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 13, Citation Count: 1

Additional Information:

references cited by 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/279943.280000 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.

	AFP92	Dana Angluin , Michael Frazier , Leonard Pitt, Learning Conjunctions of Horn Clauses, Machine Learning, v.9 n.2-3, p.147-164, July 1992 [doi>10.1007/BF00992675]
	AHK93	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 [doi>10.1145/138027.138061]
	AKST97	Dana Angluin , Mārtiņš Kriķis , Robert H. Sloan , György Turán, Malicious Omissions and Errors in Answers to Membership Queries, Machine Learning, v.28 n.2-3, p.211-255, Aug./Sept. 1997 [doi>10.1023/A:1007311411259]
	Ang87a	D. Angluin. Learning k-term DNF formulas using queries and counterexamples. Technical Report YALEU/DCS/RR-559, Department of Computer Science, Yale University, 1987.
	Ang87b	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]
	Ang88	Dana Angluin, Queries and Concept Learning, Machine Learning, v.2 n.4, p.319-342, April 1988 [doi>10.1023/A:1022821128753]
	Ang90	Dana Angluin, Negative Results for Equivalence Queries, Machine Learning, v.5 n.2, p.121-150, Jun. 1990 [doi>10.1023/A:1022692615781]
	AS94	Dana Angluin , Donna K. Slonim, Randomly Fallible Teachers: Learning Monotone DNF with an Incomplete Membership Oracle, Machine Learning, v.14 n.1, p.7-26, Jan. 1994 [doi>10.1023/A:1022642604085]
	BBB+96	A. Beimel, On the applications of multiplicity automata in learning, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.349, October 14-16, 1996
	BC92	N.H. Bshouty and R. Cleve. On the exact learning of formulas in parallel. In 33rd Annu. IEEE Syrup. on Foundations of Computer Science, pages 513-522, 1992.
	BCGS95	Avrim Blum , Prasad Chalasani , Sally A. Goldman , Donna K. Slonim, Learning with unreliable boundary queries, Proceedings of the eighth annual conference on Computational learning theory, p.98-107, July 05-08, 1995, Santa Cruz, California, United States [doi>10.1145/225298.225310]
	BCV96	F. Bergadano , D. Catalano , S. Varricchio, Learning Sat-k-DNF formulas from membership queries, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.126-130, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237845]
	BGHM96	Nader H. Bshouty , Sally A. Goldman , Thomas R. Hancock , Sleiman Matar, Asking questions to minimize errors, Journal of Computer and System Sciences, v.52 n.2, p.268-286, April 1996 [doi>10.1006/jcss.1996.0021]
	BR95	Avrim Blum , Steven Rudich, Fast learning of k-term DNF formulas with queries, Journal of Computer and System Sciences, v.51 n.3, p.367-373, Dec. 1995 [doi>10.1006/jcss.1995.1075]
	Bsh93	Nader H. Bshouty, Exact learning Boolean functions via the monotone theory, Information and Computation, v.123 n.1, p.146-153, Nov. 15, 1995 [doi>10.1006/inco.1995.1164]
	Bsh97	Nader H. Bshouty, Simple learning algorithms using divide and conquer, Computational Complexity, v.6 n.2, p.174-194, 1996/1997 [doi>10.1007/BF01262930]
	CDGK91	Michael Clausen , Andreas Dress , Johannes Grabmeier , Marek Karpinski, On zero-testing and interpolation of k -sparse multivariate polynomials over finite fields, Theoretical Computer Science, v.84 n.2, p.151-164, July 29, 1991 [doi>10.1016/0304-3975(91)90157-W]
	GM92	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 [doi>10.1145/130385.130394]
	Heg95	Tibor Hegedűs, Generalized teaching dimensions and the query complexity of learning, Proceedings of the eighth annual conference on Computational learning theory, p.108-117, July 05-08, 1995, Santa Cruz, California, United States [doi>10.1145/225298.225311]
	HPRW96	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 [doi>10.1145/234752.234755]
	Kus97	Eyal Kushilevitz, A simple algorithm for learning O (log n)-term DNF, Information Processing Letters, v.61 n.6, p.289-292, March 28, 1997 [doi>10.1016/S0020-0190(97)00026-4]
	MT89	W. Maass and G. Turin. On the complexity of learning from counterexamples. In Proc. of 3Oth Annu. IEEE Syrup. on Foundations of Computer Science, pages 262-273, 1989.
	MT90	W. Maass and G. Turin. On the complexity of learning from counterexamples and membership queries. In Proc. of 3 I st Annu. IEEE Syrup. on Foundations of Computer Science, volume I, pages 203-210, 1990.
	MT92	Wolfgang Maass , György Turán, Lower Bound Methods and Separation Results for On-Line Learning Models, Machine Learning, v.9 n.2-3, p.107-145, July 1992 [doi>10.1007/BF00992674]
	NSS95	M. Naor , L. J. Schulman , A. Srinivasan, Splitters and near-optimal derandomization, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.182, October 23-25, 1995
	RB91	Ron M. Roth , Gyora M. Benedek, Interpolation and approximation of sparse multivariate polynomials over GF(2), SIAM Journal on Computing, v.20 n.2, p.291-314, April 1990 [doi>10.1137/0220019]
	RS93	Ronald L. Rivest , Robert E. Schapire, Inference of finite automata using homing sequences, Information and Computation, v.103 n.2, p.299-347, April 1993 [doi>10.1006/inco.1993.1021]
	SS96	Robert E. Schapire , Linda M. Sellie, Learning sparse multivariate polynomials over a field with queries and counterexamples, Journal of Computer and System Sciences, v.52 n.2, p.201-213, April 1996 [doi>10.1006/jcss.1996.0017]
	Yao83	A.C. Yao. Lower bounds by probabilistic arguments. In Proc. of the 24th Annu. IEEE Syrup. on Foundations of Computer Science, pages 420- 428, 1983.