Learning sparse multivariate polynomials over a field with queries and counterexamples

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Learning sparse multivariate polynomials over a field with queries and counterexamples

Full text

Pdf (1.13 MB)

Source

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

Santa Cruz, California, United States

Pages: 17 - 26

Year of Publication: 1993

ISBN:0-89791-611-5

Authors

Robert E. Schapire
Linda M. Sellie

Sponsors

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): 15, Downloads (12 Months): 26, Citation Count: 9

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/168304.168307 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	Sigal Ar, Richard J. Lipton, Ronitt Rubinfeld, and Madhu Sudan. Reconstructing algebraic functions from mixed data. In 33rd Annual Symposium on Foundations of Computer Science, pages 503-512, October 1992.
	3	Michael Ben-Or, A deterministic algorithm for sparse multivariate polynomial interpolation, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.301-309, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62241]
	4	Avrim Blum, Learning Boolean Functions in an Infinite Attribute Space, Machine Learning, v.9 n.4, p.373-386, Oct. 1992 [doi>10.1023/A:1022653502461]
	5	Avrim Blum , Mona Singh, Learning functions of k terms, Proceedings of the third annual workshop on Computational learning theory, p.144-153, August 06-08, 1990, Rochester, New York, United States
	6	Anselm Blumer , A. Ehrenfeucht , David Haussler , Manfred K. Warmuth, Learnability and the Vapnik-Chervonenkis dimension, Journal of the ACM (JACM), v.36 n.4, p.929-965, Oct. 1989 [doi>10.1145/76359.76371]
	7	Nader H. Bshouty. Exact learning. Unpublished manuscript, 1993.
	8	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]
	9	Paul Fischer , Hans Ulrich Simon, On learning ring-sum-expansions, SIAM Journal on Computing, v.21 n.1, p.181-192, Feb. 1992 [doi>10.1137/0221014]
	10	Peter Gemmell , Madhu Sudan, Highly resilient correctors for polynomials, Information Processing Letters, v.43 n.4, p.169-174, Sept. 28, 1992 [doi>10.1016/0020-0190(92)90195-2]
	11	Dima Yu Grigoriev , Marek Karpinski , Michael F. Singer, Fast parallel algorithms for sparse multivariate polynomial interpolation over finite fields, SIAM Journal on Computing, v.19 n.6, p.1059-1063, Dec. 1990 [doi>10.1137/0219073]
	12	David Haussler, Decision theoretic generalizations of the PAC model for neural net and other learning applications, Information and Computation, v.100 n.1, p.78-150, Sept. 1992 [doi>10.1016/0890-5401(92)90010-D]
	13	Lisa Hellerstein and Manfred Warmuth. Interpolating
	14	I.N. Herstein. Topics in Algebra. Wiley, second edition, 1975.
	15	Eyal Kushilevitz , Yishay Mansour, Learning decision trees using the Fourier spectrum, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.455-464, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103466]
	16	Yishay Mansour, Randomized Interpolation and Approximation of Sparse Polynomials, Proceedings of the 19th International Colloquium on Automata, Languages and Programming, p.261-272, July 13-17, 1992
	17	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]
	18	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]
	19	Richard Zippel, Probabilistic algorithms for sparse polynomials, Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, p.216-226, June 01, 1979
	20	Richard Zippel, Interpolating polynomials from their values, Journal of Symbolic Computation, v.9 n.3, p.375-403, March 1990 [doi>10.1016/S0747-7171(08)80018-1]

CITED BY 9

	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
	Eyal Kushilevitz, A simple algorithm for learning O(log n)-term DNF, Proceedings of the ninth annual conference on Computational learning theory, p.266-269, June 28-July 01, 1996, Desenzano del Garda, Italy
	Nader H. Bshouty , Zhixiang Chen , Scott E. Decatur , Steven Homer, On the learnability of Zn-DNF formulas (extended abstract), Proceedings of the eighth annual conference on Computational learning theory, p.198-205, July 05-08, 1995, Santa Cruz, California, United States
	Nader H. Bshouty , Lynn Burroughs, On the proper learning of axis-parallel concepts, The Journal of Machine Learning Research, 4, p.157-176, 12/1/2003
	Daoud Bshouty , Nader H. Bshouty, On learning arithmetic read-once formulas with exponentiation (extended abstract), Proceedings of the seventh annual conference on Computational learning theory, p.311-317, July 12-15, 1994, New Brunswick, New Jersey, United States
	Nader H. Bshouty, A note on learning multivariate polynomials under the uniform distribution (extended abstract), Proceedings of the eighth annual conference on Computational learning theory, p.79-82, July 05-08, 1995, Santa Cruz, California, United States
	Amos Beimel , Felix Geller , Eyal Kushilevitz, The query complexity of finding local minima in the lattice, Information and Computation, v.171 n.1, p.69-83, November 25, 2001
	Sebastien M. Lahaie , David C. Parkes, Applying learning algorithms to preference elicitation, Proceedings of the 5th ACM conference on Electronic commerce, May 17-20, 2004, New York, NY, USA
	Zeljko Zilic , Zvonko G. Vranesic, A Deterministic Multivariate Interpolation Algorithm for Small Finite Fields, IEEE Transactions on Computers, v.51 n.9, p.1100-1105, September 2002