{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T23:05:19Z","timestamp":1725750319441},"publisher-location":"Berlin, Heidelberg","reference-count":100,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642409349"},{"type":"electronic","value":"9783642409356"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40935-6_4","type":"book-chapter","created":{"date-parts":[[2013,9,27]],"date-time":"2013-09-27T05:14:50Z","timestamp":1380258890000},"page":"33-52","source":"Crossref","is-referenced-by-count":5,"title":["Exact Learning from Membership Queries: Some Techniques, Results and New Directions"],"prefix":"10.1007","author":[{"given":"Nader H.","family":"Bshouty","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"4_CR1","series-title":"Wiley Teubner Series on Applicable Theory in Computer Science","volume-title":"Combinatorial Search","author":"M. Aigner","year":"1988","unstructured":"Aigner, M.: Combinatorial Search. Wiley Teubner Series on Applicable Theory in Computer Science. Teubner, Stuttgart (1988)"},{"issue":"4","key":"4_CR2","first-page":"319","volume":"2","author":"D. Angluin","year":"1987","unstructured":"Angluin, D.: Queries and Concept Learning. Machine Learning\u00a02(4), 319\u2013342 (1987)","journal-title":"Machine Learning"},{"key":"4_CR3","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/0890-5401(87)90052-6","volume":"75","author":"D. Angluin","year":"1987","unstructured":"Angluin, D.: Learning Regaular Sets from Queries and Counterexamples. Information and Computation\u00a075, 87\u2013106 (1987)","journal-title":"Information and Computation"},{"doi-asserted-by":"crossref","unstructured":"Abboud, E., Agha, N., Bshouty, N.H., Radwan, N., Saleh, F.: Learning Threshold Functions with Small Weights Using Membership Queries. In: COLT 1999, pp. 318\u2013322 (1999)","key":"4_CR4","DOI":"10.1145\/307400.307483"},{"unstructured":"Abasi, H., Bshouty, N.H.: On Exact Learning DNF from Membership Queries (in preperation)","key":"4_CR5"},{"issue":"1","key":"4_CR6","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1016\/j.jcss.2007.04.011","volume":"74","author":"M. Alekhnovich","year":"2008","unstructured":"Alekhnovich, M., Braverman, M., Feldman, V., Klivans, A.R., Pitassi, T.: The Complexity of Properly Learning Simple Concept classes. J. Comput. Syst. Sci.\u00a074(1), 16\u201334 (2008)","journal-title":"J. Comput. Syst. Sci."},{"key":"4_CR7","first-page":"147","volume":"9","author":"D. Angluin","year":"1992","unstructured":"Angluin, D., Frazier, M., Pitt, L.: Learning Conjunctions of Horn Clauses. Machine Learning\u00a09, 147\u2013164 (1992)","journal-title":"Machine Learning"},{"doi-asserted-by":"crossref","unstructured":"Aizenstein, H., Hellerstein, L., Pitt, L.: Read-Thrice DNF Is Hard to Learn With Membership and Equivalence Queries. In: FOCS 1992, pp. 523\u2013532 (1992)","key":"4_CR8","DOI":"10.1109\/SFCS.1992.267799"},{"issue":"2-3","key":"4_CR9","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1023\/A:1007311411259","volume":"28","author":"D. Angluin","year":"1997","unstructured":"Angluin, D., Krikis, M., Sloan, R.H., Tur\u00e1n, G.: Malicious Omissions and Errors in Answers to Membership Queries. Machine Learning\u00a028(2-3), 211\u2013255 (1997)","journal-title":"Machine Learning"},{"issue":"2","key":"4_CR10","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/1150334.1150336","volume":"2","author":"N. Alon","year":"2006","unstructured":"Alon, N., Moshkovitz, D., Safra, S.: Algorithmic construction of sets for k-restrictions. ACM Transactions on Algorithms\u00a02(2), 153\u2013177 (2006)","journal-title":"ACM Transactions on Algorithms"},{"doi-asserted-by":"crossref","unstructured":"Anderson, M., van Melkebeek, D., Volkovich, I.: Derandomizing Polynomial Identity Testing for Multilinear Constant-Read Formulae. In: CCC 2011, pp. 273\u2013282 (2011)","key":"4_CR11","DOI":"10.1109\/CCC.2011.18"},{"unstructured":"Aizenstein, H., Pitt, L.: Exact Learning of Read-Twice DNF Formulas. In: FOCS 1991, pp. 170\u2013179 (1991)","key":"4_CR12"},{"issue":"1","key":"4_CR13","first-page":"7","volume":"14","author":"D. Angluin","year":"1994","unstructured":"Angluin, D., Slonim, D.K.: Randomly Fallible Teachers: Learning Monotone DNF with an Incomplete Membership Oracle. Machine Learning\u00a014(1), 7\u201326 (1994)","journal-title":"Machine Learning"},{"unstructured":"Agrawal, M., Saptharishi, R.: Classifying polynomials and identity testing. Current Trends in Science (2009), http:\/\/www.cse.iitk.ac.in\/users\/manindra\/survey\/Identity.pdf.3","key":"4_CR14"},{"doi-asserted-by":"crossref","unstructured":"Agrawal, M., Saha, C., Saxena, N.: Quasi-polynomial Hitting-set for Set-depth-\u0394 Formulas. In: STOC 2013, pp. 321\u2013330 (2013)","key":"4_CR15","DOI":"10.1145\/2488608.2488649"},{"doi-asserted-by":"crossref","unstructured":"Agrawal, M., Vinay, V.: Arithmetic Circuits: A Chasm at Depth Four. In: FOCS 2008, pp. 67\u201375 (2008)","key":"4_CR16","DOI":"10.1109\/FOCS.2008.32"},{"doi-asserted-by":"crossref","unstructured":"Bogdanov, A.: Pseudorandom Generators for Low Degree Polynomials. In: STOC 2005, pp. 21\u201330 (2005)","key":"4_CR17","DOI":"10.1145\/1060590.1060594"},{"issue":"1","key":"4_CR18","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1006\/inco.1995.1164","volume":"123","author":"N.H. Bshouty","year":"1995","unstructured":"Bshouty, N.H.: Exact Learning Boolean Function via the Monotone Theory. Inf. Comput.\u00a0123(1), 146\u2013153 (1995)","journal-title":"Inf. Comput."},{"issue":"2","key":"4_CR19","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1007\/BF01262930","volume":"6","author":"N.H. Bshouty","year":"1997","unstructured":"Bshouty, N.H.: Simple Learning Algorithms Using Divide and Conquer. Computational Complexity\u00a06(2), 174\u2013194 (1997)","journal-title":"Computational Complexity"},{"issue":"1","key":"4_CR20","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1023\/A:1007320031970","volume":"26","author":"N.H. Bshouty","year":"1997","unstructured":"Bshouty, N.H.: Exact Learning of Formulas in Parallel. Machine Learning\u00a026(1), 25\u201341 (1997)","journal-title":"Machine Learning"},{"doi-asserted-by":"crossref","unstructured":"Bshouty, N.H.: On the Coin Weighing Problem with the Presence of Noise. In: APPROX-RANDOM 2012, pp. 471\u2013482 (2012)","key":"4_CR21","DOI":"10.1007\/978-3-642-32512-0_40"},{"key":"4_CR22","first-page":"11","volume":"19","author":"N.H. Bshouty","year":"2012","unstructured":"Bshouty, N.H.: Testers and their Applications. Electronic Collouium on Computational Complexity (ECCC)\u00a019, 11 (2012)","journal-title":"Electronic Collouium on Computational Complexity (ECCC)"},{"key":"4_CR23","first-page":"11","volume":"20","author":"N.H. Bshouty","year":"2013","unstructured":"Bshouty, N.H.: Multilinear Complexity is Equivalent to Optimal Tester Size. Electronic Collouium on Computational Complexity (ECCC)\u00a020, 11 (2013)","journal-title":"Electronic Collouium on Computational Complexity (ECCC)"},{"unstructured":"Bshouty, N.H.: Dense Testers and Their Applications (in preperation)","key":"4_CR24"},{"unstructured":"Bshouty, N.H.: Non-adaptive Deterministic Learning XOR of Terms and Decision Tree from Membership Queries (in preperation)","key":"4_CR25"},{"issue":"1","key":"4_CR26","doi-asserted-by":"publisher","first-page":"112","DOI":"10.1006\/jcss.1997.1550","volume":"56","author":"D. Bshouty","year":"1998","unstructured":"Bshouty, D., Bshouty, N.H.: On Interpolating Arithmetic Read-Once Formulas with Exponentiation. J. Comput. Syst. Sci.\u00a056(1), 112\u2013124 (1998)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"4_CR27","doi-asserted-by":"publisher","first-page":"506","DOI":"10.1145\/337244.337257","volume":"47","author":"A. Beimel","year":"2000","unstructured":"Beimel, A., Bergadano, F., Bshouty, N.H., Kushilevitz, E., Varricchio, S.: Learning Functions Represented as Multiplicity Automata. J. ACM\u00a047(3), 506\u2013530 (2000)","journal-title":"J. ACM"},{"issue":"1","key":"4_CR28","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.jcss.2007.04.010","volume":"74","author":"L. Bisht","year":"2008","unstructured":"Bisht, L., Bshouty, N.H., Khoury, L.: Learning with Errors in Answering to Memebership Queries. J. Comput. Syst. Sci.\u00a074(1), 2\u201315 (2008)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"4_CR29","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1137\/S009753979528812X","volume":"27","author":"N.H. Bshouty","year":"1998","unstructured":"Bshouty, N.H., Cleve, R.: Interpolating Arithmetic Read-Once Formulas in Parallel. SIAM J. Comput.\u00a027(2), 401\u2013413 (1998)","journal-title":"SIAM J. Comput."},{"key":"4_CR30","first-page":"49","volume":"3","author":"N.H. Bshouty","year":"2002","unstructured":"Bshouty, N.H., Eiron, N.: Learning Monotone DNF from a Teacher that Almost Does Not Answer Membership Queries. JMLR\u00a03, 49\u201357 (2002)","journal-title":"JMLR"},{"issue":"2","key":"4_CR31","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/S0304-3975(01)00403-0","volume":"288","author":"N.H. Bshouty","year":"2002","unstructured":"Bshouty, N.H., Eiron, N., Kushilevitz, E.: PAC Learning with Nasty Noise. Theor. Comput. Sci.\u00a0288(2), 255\u2013275 (2002)","journal-title":"Theor. Comput. Sci."},{"unstructured":"Biglieri, E., Gyorfi, L.: Multiple Access Channels: Theory and Practice. IOS Press (2007)","key":"4_CR32"},{"issue":"2","key":"4_CR33","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1006\/jcss.1996.0021","volume":"52","author":"N.H. Bshouty","year":"1996","unstructured":"Bshouty, N.H., Goldman, S.A., Hancock, T.R., Matar, S.: Asking Questions to Minimize Errors. J. Comput. Syst. Sci.\u00a052(2), 268\u2013286 (1996)","journal-title":"J. Comput. Syst. Sci."},{"doi-asserted-by":"crossref","unstructured":"Bshouty, N.H., Hellerstein, L.: Attribute-Efficient Learning in Query and Mistakebound Models. In: COLT 1996, pp. 235\u2013243 (1996)","key":"4_CR34","DOI":"10.1145\/238061.238108"},{"issue":"3","key":"4_CR35","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1006\/jcss.1995.1042","volume":"50","author":"N.H. Bshouty","year":"1995","unstructured":"Bshouty, N.H., Hancock, T.R., Hellerstein, L.: Learning Boolean Read-Once Formulas over Generalized Bases. J. Comput. Syst. Sci.\u00a050(3), 521\u2013542 (1995)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"4_CR36","doi-asserted-by":"publisher","first-page":"706","DOI":"10.1137\/S009753979223664X","volume":"24","author":"N.H. Bshouty","year":"1995","unstructured":"Bshouty, N.H., Hancock, T.R., Hellerstein, L.: Learning Arithmetic Read-Once Formulas. SIAM J. Comput.\u00a024(4), 706\u2013735 (1995)","journal-title":"SIAM J. Comput."},{"key":"4_CR37","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/BF01205054","volume":"4","author":"N.H. Bshouty","year":"1994","unstructured":"Bshouty, N.H., Hancock, T.R., Hellerstein, L., Karpinski, M.: An Algorithm to Learn Read-Once Threshold Formulas, and Transformations Between Learning Models. Computational Complexity\u00a04, 37\u201361 (1994)","journal-title":"Computational Complexity"},{"issue":"3","key":"4_CR38","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/j.ipl.2008.09.029","volume":"109","author":"M. Bl\u00e4ser","year":"2009","unstructured":"Bl\u00e4ser, M., Hardt, M., Lipton, R.J., Vishnoi, N.K.: Deterministically Testing Sparse Polynomial Identities of Unbounded Degree. Inf. Process. Lett.\u00a0109(3), 187\u2013192 (2009)","journal-title":"Inf. Process. Lett."},{"doi-asserted-by":"crossref","unstructured":"Bl\u00e4ser, M., Hardt, M., Steurer, D.: Asymptotically Optimal Hitting Sets Against Polynomials. In: ICALP (1), pp. 345\u2013356 (2008)","key":"4_CR39","DOI":"10.1007\/978-3-540-70575-8_29"},{"issue":"6","key":"4_CR40","doi-asserted-by":"publisher","first-page":"1909","DOI":"10.1137\/S009753979732058X","volume":"31","author":"N.H. Bshouty","year":"2002","unstructured":"Bshouty, N.H., Mansour, Y.: Simple Learning Algorithms for Decision Trees and Multivariate Polynomials. SIAM J. Comput.\u00a031(6), 1909\u20131925 (2002)","journal-title":"SIAM J. Comput."},{"unstructured":"Bshouty, N.H., Mossel, E., O\u2019Donnell, R., Servedio, R.A.: Learning DNF from Random Walks. In: FOCS 2003, pp. 189\u2013198 (2003)","key":"4_CR41"},{"issue":"3","key":"4_CR42","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.1995.1075","volume":"51","author":"A. Blum","year":"1995","unstructured":"Blum, A., Rudich, S.: Fast Learning of k-Term DNF Formulas with Queries. J. Comput. Syst. Sci.\u00a051(3), 367\u2013373 (1995)","journal-title":"J. Comput. Syst. Sci."},{"doi-asserted-by":"crossref","unstructured":"Ben-Or, M., Tiwari, P.: A Deterministic Algorithm for Sparse Multivariate Polynomial Interpolation. In: STOC 1988, pp. 301\u2013309 (1988)","key":"4_CR43","DOI":"10.1145\/62212.62241"},{"issue":"2","key":"4_CR44","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1016\/0304-3975(91)90157-W","volume":"84","author":"M. Clausen","year":"1991","unstructured":"Clausen, M., Dress, A.W.M., Grabmeier, J., Karpinski, M.: On Zero-Testing and Interpolation of k-Sparse Multivariate Polynomials Over Finite Fields. Theor. Comput. Sci.\u00a084(2), 151\u2013164 (1991)","journal-title":"Theor. Comput. Sci."},{"key":"4_CR45","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/978-3-642-20712-9_3","volume-title":"Computer Science \u2013 Theory and Applications","author":"A. Chattopadhyay","year":"2011","unstructured":"Chattopadhyay, A., Gavald\u00e0, R., Hansen, K.A., Th\u00e9rien, D.: Learning Read-Constant Polynomials of Constant Degree Modulo Composites. In: Kulikov, A., Vereshchagin, N. (eds.) CSR 2011. LNCS, vol.\u00a06651, pp. 29\u201342. Springer, Heidelberg (2011)"},{"doi-asserted-by":"crossref","unstructured":"Cheng, J., Kamoi, K., Watanabe, Y.: User Identification by Signature Code for Noisy Multiple-Access Adder Channel. In: IEEE International Symposium on In- formation Theory, pp. 1974\u20131977 (2006)","key":"4_CR46","DOI":"10.1109\/ISIT.2006.261894"},{"key":"4_CR47","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"516","DOI":"10.1007\/BFb0045121","volume-title":"Computing and Combinatorics","author":"C. Domingo","year":"1997","unstructured":"Domingo, C.: Exact Learning of Subclasses of CDNF Formulars with Membership Queries. In: Jiang, T., Lee, D.T. (eds.) COCOON 1997. LNCS, vol.\u00a01276, pp. 516\u2013520. Springer, Heidelberg (1997)"},{"issue":"2","key":"4_CR48","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1023\/A:1007616604496","volume":"41","author":"P. Damaschke","year":"2000","unstructured":"Damaschke, P.: Adaptive Versus Nonadaptive Attribute-Efficient Learning. Machine Learning\u00a041(2), 197\u2013215 (2000)","journal-title":"Machine Learning"},{"issue":"1","key":"4_CR49","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1016\/S0022-0000(03)00047-3","volume":"67","author":"P. Damaschke","year":"2003","unstructured":"Damaschke, P.: On Parallel Attribute-Efficient Learning. J. Comput. Syst. Sci.\u00a067(1), 46\u201362 (2003)","journal-title":"J. Comput. Syst. Sci."},{"doi-asserted-by":"crossref","unstructured":"Du, D., Hwang, F.K.: Combinatorial Group Testing and Its Applications. World Scientific Pub. Co. Inc. (2000)","key":"4_CR50","DOI":"10.1142\/4252"},{"doi-asserted-by":"crossref","unstructured":"Du, D., Hwang, F.K.: Pooling Design and Nonadaptive Group Testing: Important Tools for DNA Sequencing. World Scientific Publishing Company (2006)","key":"4_CR51","DOI":"10.1142\/9789812773463"},{"issue":"1","key":"4_CR52","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1023\/A:1007627028578","volume":"37","author":"C. Domingo","year":"1999","unstructured":"Domingo, C., Mishra, N., Pitt, L.: Efficient Read-Restricted Monotone CNF\/DNF Dualization by Learning with Membership Queries. Machine Learning\u00a037(1), 89\u2013110 (1999)","journal-title":"Machine Learning"},{"key":"4_CR53","first-page":"1431","volume":"8","author":"V. Feldman","year":"2007","unstructured":"Feldman, V.: Attribute-Efficient and Non-adaptive Learning of Parities and DNF Expressions. JMLR\u00a08, 1431\u20131460 (2007)","journal-title":"JMLR"},{"issue":"3","key":"4_CR54","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1006\/jcss.1996.0035","volume":"52","author":"M. Frazier","year":"1996","unstructured":"Frazier, M., Goldman, S.A., Mishra, N., Pitt, L.: Learning from a Consistently Ignorant Teacher. J. Comput. Syst. Sci.\u00a052(3), 471\u2013492 (1996)","journal-title":"J. Comput. Syst. Sci."},{"key":"4_CR55","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1007\/11776420_27","volume-title":"Learning Theory","author":"L. Fortnow","year":"2006","unstructured":"Fortnow, L., Klivans, A.R.: Efficient Learning Algorithms Yield Circuit Lower Bounds. In: Lugosi, G., Simon, H.U. (eds.) COLT 2006. LNCS (LNAI), vol.\u00a04005, pp. 350\u2013363. Springer, Heidelberg (2006)"},{"doi-asserted-by":"crossref","unstructured":"Grigoriev, D., Karpinski, M.: Algorithms for Sparse Rational Interpolation. In: ISSAC 1991, pp. 7\u201313 (1991)","key":"4_CR56","DOI":"10.1145\/120694.120696"},{"issue":"6","key":"4_CR57","doi-asserted-by":"publisher","first-page":"1059","DOI":"10.1137\/0219073","volume":"19","author":"D. Grigoriev","year":"1990","unstructured":"Grigoriev, D., Karpinski, M., Singer, M.F.: Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields. SIAM J. Comput.\u00a019(6), 1059\u20131063 (1990)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"4_CR58","doi-asserted-by":"publisher","first-page":"705","DOI":"10.1137\/0222047","volume":"22","author":"S.A. Goldman","year":"1993","unstructured":"Goldman, S.A., Kearns, M.J., Schapire, R.E.: Exact Identification of Read-Once Formulas Using Fixed Points of Amplification Functions. SIAM J. Comput.\u00a022(4), 705\u2013726 (1993)","journal-title":"SIAM J. Comput."},{"unstructured":"Grigoriev, D., Karpinski, M., Singer, M.F.: Interpolation of Sparse Rational Functions Without Knowing Bounds on Exponents. In: FOCS 1990, pp. 840\u2013846 (1990)","key":"4_CR59"},{"issue":"6","key":"4_CR60","doi-asserted-by":"publisher","first-page":"1059","DOI":"10.1137\/0219073","volume":"19","author":"D. Grigoriev","year":"1990","unstructured":"Grigoriev, D., Karpinski, M., Singer, M.F.: Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields. SIAM J. Comput.\u00a019(6), 1059\u20131063 (1990)","journal-title":"SIAM J. Comput."},{"doi-asserted-by":"crossref","unstructured":"Goldreich, O., Levin, L.A.: A Hard-core Predicate for all One-way Functions. In: STOC\u00a01989, pp. 25\u201332 (1989)","key":"4_CR61","DOI":"10.1145\/73007.73010"},{"issue":"3","key":"4_CR62","doi-asserted-by":"publisher","first-page":"649","DOI":"10.1145\/146637.146670","volume":"39","author":"W.I. Gasarch","year":"1992","unstructured":"Gasarch, W.I., Smith, C.H.: Learning via Queries. J. ACM\u00a039(3), 649\u2013674 (1992)","journal-title":"J. ACM"},{"key":"4_CR63","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/978-3-642-04414-4_19","volume-title":"Algorithmic Learning Theory","author":"R. Gavald\u00e0","year":"2009","unstructured":"Gavald\u00e0, R., Th\u00e9rien, D.: An algebraic perspective on boolean function learning. In: Gavald\u00e0, R., Lugosi, G., Zeugmann, T., Zilles, S. (eds.) ALT 2009. LNCS, vol.\u00a05809, pp. 201\u2013215. Springer, Heidelberg (2009)"},{"doi-asserted-by":"crossref","unstructured":"Hellerstein, L., Karpinski, M.: Learning Read-Once Formulas Using Membership Queries. In: COLT 1989, pp. 146\u2013161 (1989)","key":"4_CR64","DOI":"10.1016\/B978-0-08-094829-4.50013-1"},{"issue":"3","key":"4_CR65","doi-asserted-by":"publisher","first-page":"414","DOI":"10.1006\/jcss.1997.1533","volume":"55","author":"J.C. Jackson","year":"1997","unstructured":"Jackson, J.C.: An Efficient Membership-Query Algorithm for Learning DNF with Respect to the Uniform Distribution. J. Comput. Syst. Sci.\u00a055(3), 414\u2013440 (1997)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2-3","key":"4_CR66","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/S0166-218X(99)00045-1","volume":"92","author":"J. Jacksona","year":"1999","unstructured":"Jacksona, J., Shamir, E., Shwartzmanb, C.: Learning with Queries Corrupted by Classification Noise. Discrete Applied Mathematics\u00a092(2-3), 157\u2013175 (1999)","journal-title":"Discrete Applied Mathematics"},{"issue":"6","key":"4_CR67","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1016\/S0020-0190(97)00026-4","volume":"61","author":"E. Kushilevitz","year":"1997","unstructured":"Kushilevitz, E.: A Simple Algorithm for Learning O (logn)-Term DNF. Inf. Process. Lett.\u00a061(6), 289\u2013292 (1997)","journal-title":"Inf. Process. Lett."},{"issue":"6","key":"4_CR68","doi-asserted-by":"publisher","first-page":"983","DOI":"10.1145\/293347.293351","volume":"45","author":"M.J. Kearns","year":"1998","unstructured":"Kearns, M.J.: Efficient Noise-Tolerant Learning from Statistical Queries. J. ACM\u00a045(6), 983\u20131006 (1998)","journal-title":"J. ACM"},{"unstructured":"Kutyniok, G.: Compressed Sensing: Theory and Applications. CoRR abs\/1203.3815 (2012)","key":"4_CR69"},{"doi-asserted-by":"crossref","unstructured":"Kabanets, V., Impagliazzo, R.: Derandomizing Polynomial Identity Tests means Proving Circuit Lower Bounds. In: STOC 2003, pp. 355\u2013364 (2003)","key":"4_CR70","DOI":"10.1145\/780591.780595"},{"key":"4_CR71","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1007\/3-540-51084-2_44","volume-title":"Symbolic and Algebraic Computation","author":"E. Kaltofen","year":"1989","unstructured":"Kaltofen, E., Lakshman, Y.N.: Improved Sparse Multivariate Polynomial Interpolation Algorithms. In: Gianni, P. (ed.) ISSAC 1988. LNCS, vol.\u00a0358, pp. 467\u2013474. Springer, Heidelberg (1989)"},{"issue":"4","key":"4_CR72","doi-asserted-by":"publisher","first-page":"807","DOI":"10.1137\/0222052","volume":"22","author":"M.J. Kearns","year":"1993","unstructured":"Kearns, M.J., Li, M.: Learning in the Presence of Malicious Errors. SIAM J. Comput.\u00a022(4), 807\u2013837 (1993)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"4_CR73","doi-asserted-by":"publisher","first-page":"1331","DOI":"10.1137\/0222080","volume":"22","author":"E. Kushilevitz","year":"1993","unstructured":"Kushilevitz, E., Mansour, Y.: Learning Decision Trees Using the Fourier Spectrum. SIAM J. Comput.\u00a022(6), 1331\u20131348 (1993)","journal-title":"SIAM J. Comput."},{"doi-asserted-by":"crossref","unstructured":"Karnin, Z.S., Mukhopadhyay, P., Shpilka, A., Volkovich, I.: Deterministic Identity Testing of Depth-4 Multilinear Circuits with Bounded top Fan-in. In: STOC 2010, pp. 649\u2013658 (2010)","key":"4_CR74","DOI":"10.1145\/1806689.1806779"},{"issue":"4","key":"4_CR75","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1109\/TIT.1964.1053689","volume":"10","author":"W.H. Kautz","year":"1964","unstructured":"Kautz, W.H., Singleton, R.C.: Nonrandom binary superimposed codes. IEEE Trans. Inform. Theory\u00a010(4), 363\u2013377 (1964)","journal-title":"IEEE Trans. Inform. Theory"},{"issue":"3","key":"4_CR76","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/0012-365X(73)90098-8","volume":"6","author":"D.J. Kleitman","year":"1972","unstructured":"Kleitman, D.J., Spencer, J.: Families of k-independent sets. Discrete Mathematics\u00a06(3), 255\u2013262 (1972)","journal-title":"Discrete Mathematics"},{"doi-asserted-by":"crossref","unstructured":"Klivans, A., Spielman, D.A.: Randomness Efficient Identity Testing of Multivariate Polynomials. In: STOC 2001, pp. 216\u2013223 (2001)","key":"4_CR77","DOI":"10.1145\/380752.380801"},{"key":"4_CR78","first-page":"32","volume":"16","author":"N. Kayal","year":"2009","unstructured":"Kayal, N., Saraf, S.: Blackbox Polynomial Identity Testing for Depth 3 Circuits. Electronic Colloquium on Computational Complexity (ECCC)\u00a016, 32 (2009)","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"doi-asserted-by":"crossref","unstructured":"Karnin, Z.S., Shpilka, A.: Black Box Polynomial Identity Testing of Generalized Depth-3 Arithmetic Circuits with Bounded Top Fan-In. In: CCC 2008, pp. 280\u2013291 (2008)","key":"4_CR79","DOI":"10.1109\/CCC.2008.15"},{"unstructured":"Naor, M., Schulman, L.J., Srinivasan, A.: Splitters and Near-optimal Derandomization. In: FOCS 1995, pp. 182\u2013191 (1995)","key":"4_CR80"},{"unstructured":"Introduction to Coding Theory. Cambridge University Press (2007)","key":"4_CR81"},{"issue":"1","key":"4_CR82","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00037-005-0188-8","volume":"14","author":"R. Raz","year":"2005","unstructured":"Raz, R., Shpilka, A.: Deterministic Polynomial Identity Testing in Non-commutative Models. Computational Complexity\u00a014(1), 1\u201319 (2005)","journal-title":"Computational Complexity"},{"key":"4_CR83","first-page":"49","volume":"99","author":"N. Saxena","year":"2009","unstructured":"Saxena, N.: Progress on Polynomial Identity Testing. Bulletin of the EATCS\u00a099, 49\u201379 (2009)","journal-title":"Bulletin of the EATCS"},{"unstructured":"Settles, B.: Active Learning Literature Survey. Computer Sciences Technical Report 1648, University of Wisconsin\u2013Madison (2010)","key":"4_CR84"},{"issue":"5","key":"4_CR85","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1016\/0020-0190(91)90220-C","volume":"37","author":"Y. Sakakibara","year":"1991","unstructured":"Sakakibara, Y.: On Learning from Queries and Counterexamples in the Presence of Noise. Inf. Process. Lett.\u00a037(5), 279\u2013284 (1991)","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"4_CR86","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1145\/322217.322225","volume":"27","author":"J.T. Schwartz","year":"1980","unstructured":"Schwartz, J.T.: Fast Probabilistic Algorithms for Verification of Polynomial Identities. Journal of the ACM\u00a027(4), 701\u2013717 (1980)","journal-title":"Journal of the ACM"},{"doi-asserted-by":"crossref","unstructured":"Schapire, R.E., Sellie, L.M.: Learning Sparse Multivariate Polynomials over a Field with Queries and Counterexamples. In: COLT, pp. 17\u201326 (1996)","key":"4_CR87","DOI":"10.1006\/jcss.1996.0017"},{"doi-asserted-by":"crossref","unstructured":"Saxena, N., Seshadhr, C.: Blackbox Identity Testing for Bounded top Fanin Depth-3 Circuits: the Field doesn\u2019t matter. In: STOC 2011, pp. 431\u2013440 (2011)","key":"4_CR88","DOI":"10.1145\/1993636.1993694"},{"issue":"3-4","key":"4_CR89","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1561\/0400000039","volume":"5","author":"A. Shpilka","year":"2010","unstructured":"Shpilka, A., Yehudayoff, A.: Arithmetic Circuits: A Survey of Recent Results and Open Questions. Foundations and Trends in Theoretical Computer Science\u00a05(3-4), 207\u2013388 (2010)","journal-title":"Foundations and Trends in Theoretical Computer Science"},{"key":"4_CR90","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"700","DOI":"10.1007\/978-3-642-03685-9_52","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"A. Shpilka","year":"2009","unstructured":"Shpilka, A., Volkovich, I.: Improved Polynomial Identity Testing for Read-once Formulas. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) APPROX 2009. LNCS, vol.\u00a05687, pp. 700\u2013713. Springer, Heidelberg (2009)"},{"key":"4_CR91","first-page":"11","volume":"17","author":"A. Shpilka","year":"2010","unstructured":"Shpilka, A., Volkovich, I.: Read-Once Polynomial Identity Testing. Electronic Colloquium on Computational Complexity (ECCC)\u00a017, 11 (2010)","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"doi-asserted-by":"crossref","unstructured":"Saraf, S., Volkovich, I.: Black-box Identity Testing of Depth-4 Multilinear Circuits. In: STOC 2011, pp. 421\u2013430 (2011)","key":"4_CR92","DOI":"10.1145\/1993636.1993693"},{"issue":"1","key":"4_CR93","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1006\/jcta.1999.3036","volume":"90","author":"D.R. Stinson","year":"2000","unstructured":"Stinson, D.R., Wei, R., Zhu, L.: Some New Bounds for Cover-free Families. Journal of Combinatorial Theory, Series A\u00a090(1), 224\u2013234 (2000)","journal-title":"Journal of Combinatorial Theory, Series A"},{"key":"4_CR94","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/3-540-49730-7_5","volume-title":"Algorithmic Learning Theory","author":"V.N. Shevchenko","year":"1998","unstructured":"Shevchenko, V.N., Zolotykh, N.Y.: Lower Bounds for the Complexity of Learning Half-Spaces with Membership Queries. In: Richter, M.M., Smith, C.H., Wiehagen, R., Zeugmann, T. (eds.) ALT 1998. LNCS (LNAI), vol.\u00a01501, pp. 61\u201371. Springer, Heidelberg (1998)"},{"key":"4_CR95","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/3-540-62685-9_15","volume-title":"Computational Learning Theory","author":"R. Uehara","year":"1997","unstructured":"Uehara, R., Tsuchida, K., Wegener, I.: Optimal Attribute-Efficient Learning of Disjunction, Parity and Threshold Functions. In: Ben-David, S. (ed.) EuroCOLT 1997. LNCS, vol.\u00a01208, pp. 171\u2013184. Springer, Heidelberg (1997)"},{"doi-asserted-by":"crossref","unstructured":"Valiant, L.G.: Completeness Classes in Algebra. In: Proc. of 11th ACM STOC, pp. 249\u2013261 (1979)","key":"4_CR96","DOI":"10.1145\/800135.804419"},{"unstructured":"Valiant, L.G.: Learning Disjunction of Conjunctions. In: IJCAI 1985, pp. 560\u2013566 (1985)","key":"4_CR97"},{"key":"4_CR98","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/BF01438278","volume":"5","author":"K. Werther","year":"1994","unstructured":"Werther, K.: The Complexity of Sparse Polynomial Interpolation over Finite Fields. Appl. Algebra Eng. Commun. Comput.\u00a05, 91\u2013103 (1994)","journal-title":"Appl. Algebra Eng. Commun. Comput."},{"unstructured":"Wikipedia, http:\/\/en.wikipedia.org\/wiki\/Guessing_game","key":"4_CR99"},{"key":"4_CR100","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1007\/3-540-09519-5_73","volume-title":"Symbolic and Algebraic Computation","author":"R. Zippel","year":"1979","unstructured":"Zippel, R.: Probabilistic Algorithms for Sparse Polynomials. In: Ng, K.W. (ed.) EUROSAM 1979 and ISSAC 1979. LNCS, vol.\u00a072, pp. 216\u2013226. Springer, Heidelberg (1979)"}],"container-title":["Lecture Notes in Computer Science","Algorithmic Learning Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40935-6_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,6]],"date-time":"2022-03-06T23:48:21Z","timestamp":1646610501000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40935-6_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642409349","9783642409356"],"references-count":100,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40935-6_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}