Adaptive versus nonadaptive attribute-efficient learning

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Adaptive versus nonadaptive attribute-efficient learning

Full text

Pdf (1.03 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirtieth annual ACM symposium on Theory of computing table of contents

Dallas, Texas, United States

Pages: 590 - 596

Year of Publication: 1998

ISBN:0-89791-962-9

Author

Peter Damaschke

FernUniversität, Theoretische Informatik II, 58084 Hagen, Germany

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

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

Additional Information:

references cited by index terms collaborative colleagues peer to peer

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/276698.276874 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	Hussein Almuallim , Thomas G. Dietterich, Learning Boolean concepts in the presence of many irrelevant features, Artificial Intelligence, v.69 n.1-2, p.279-305, Sept. 1994 [doi>10.1016/0004-3702(94)90084-1]
	2	N.Alon, J.Bruck, J.Naor, M.Naor, R.Roth: Construction of asymptotically good, low-rate error-correcting codes through pseudorandom graphs, iEEE Trans. Info. Theory
	3	N.Alon, O.Goldreich, J.Hastad, R.Peralta: Simple constructions of almost k-wise independent random variables, Ran. dorn Structures and Alger. 3, 289-304 and 4, 119-120
	4	Ingo Althöfer , Eberhard Triesch, Edge search in graphs and hypergraphs of bounded rank, Discrete Mathematics, v.115 n.1-3, p.1-9, May 15, 1993 [doi>10.1016/0012-365X(93)90473-7]
	5	Dana Angluin, Queries and Concept Learning, Machine Learning, v.2 n.4, p.319-342, April 1988 [doi>10.1023/A:1022821128753]
	6	D.J. Balding, D.C.Torney: A comparative surx'ey of nonadaptive pooling designs, in: Genetic Mapping and DNA Sequencing, IMA Volumes ir~ Mathematics and Its Application.% Springer 1995, 133-155
	7	David J. Balding , David C. Torney, Optimal pooling designs with error detection, Journal of Combinatorial Theory Series A, v.74 n.1, p.131-140, April 1996 [doi>10.1006/jcta.1996.0041]
	8	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]
	9	Avrim Blum , Lisa Hellerstein , Nick Littlestone, Learning in the presence of finitely or infinitely many irrelevant attributes, Journal of Computer and System Sciences, v.50 n.1, p.32-40, Feb. 1995 [doi>10.1006/jcss.1995.1004]
	10	N.H.Bshouty, R.Cleve: On the exact learning of formulas in parallel, 33th IEEE FOCS (1992), 513-522
	11	Nader H. Bshouty , Lisa Hellerstein, Attribute-efficient learning in query and mistake-bound models, Proceedings of the ninth annual conference on Computational learning theory, p.235-243, June 28-July 01, 1996, Desenzano del Garda, Italy [doi>10.1145/238061.238108]
	12	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]
	13	C.J.Colbourn, J.H.Dinitz: The CRC Handbook of Combina. torial Designs, CRC Press 1996
	14	Peter Damaschke, A tight upper bound for group testing in graphs, Discrete Applied Mathematics, v.48 n.2, p.101-109, Jan. 26, 1994 [doi>10.1016/0166-218X(92)00120-B]
	15	Peter Damaschke, The Algorithmic Complexity of Chemical Threshold Testing, Proceedings of the Third Italian Conference on Algorithms and Complexity, p.205-216, March 12-14, 1997
	16	A.Dhagat, L.I-Iellerstein: PAC learning with irrelevant attributes, 35th IEBE FOCS (1994), 64-74
	17	D.Z.Du, F.K.Hwang: Combinatorial Group Testing and Its Applications, World Scientific 1993
	18	M. Farach , S. Kannan , E. Knill , S. Muthukrishnan, Group Testing Problems with Sequences in Experimental Molecular Biology, Proceedings of the Compression and Complexity of Sequences 1997, p.357, June 11-13, 1997
	19	P. Fischer, N.Klasner, I.~Vegener: On the cut-off point for combinatorial group testing, Techn. Report eCOLT 9%002, Univ. Dortmund
	20	D.J.Kleitman, J.H.Spencer: Families of k. independent sets, Discrete ~lath. 6 (1973), 255-262
	21	E. Knill, Lower bounds for identifying subset members with subset queries, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.369-377, January 22-24, 1995, San Francisco, California, United States
	22	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]
	23	A.Macula, G.Reuter: Simplified searching for two defect:J, J. Statist. Planning and Inference, to appear
	24	Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
	25	Joseph Naor , Moni Naor, Small-bias probability spaces: efficient constructions and applications, SIAM Journal on Computing, v.22 n.4, p.838-856, Aug. 1993 [doi>10.1137/0222053]
	26	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
	27	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]
	28	G.Seroussi, N.H.Bshouty: Vector sets for exhaustive testing of logic circuits, IEEE Trans. Information Theory 3,t (1988), 513-522
	29	Eberhard Triesch, A group testing problem for hypergraphs of bounded rank, Discrete Applied Mathematics, v.66 n.2, p.185-188, April 30, 1996 [doi>10.1016/0166-218X(95)00120-G]
	30	Ryuhei Uehara , Kensei Tsuchida , Ingo Wegener, Optimal Attribute-Efficient Learning of Disjunction, Parity and Threshold Functions, Proceedings of the Third European Conference on Computational Learning Theory, p.171-184, March 17-19, 1997

CITED BY 5

	Peter Damaschke, Point placement on the line by distance data, Discrete Applied Mathematics, v.127 n.1, p.53-62, April 2003
	Krzysztof Majewski , Nicholas Pippenger, Attribute estimation and testing quasi-symmetry, Information Processing Letters, v.109 n.4, p.233-237, January, 2009
	Piotr Indyk, Interpolation of symmetric functions and a new type of combinatorial design, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.736-740, May 01-04, 1999, Atlanta, Georgia, United States
	Dana Angluin , Jiang Chen, Learning a Hidden Hypergraph, The Journal of Machine Learning Research, 7, p.2215-2236, 12/1/2006
	Nader H. Bshouty , Jeffrey C. Jackson , Christino Tamon, More efficient PAC-learning of DNF with membership queries under the uniform distribution, Proceedings of the twelfth annual conference on Computational learning theory, p.286-295, July 07-09, 1999, Santa Cruz, California, United States