{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,18]],"date-time":"2025-05-18T04:04:10Z","timestamp":1747541050438,"version":"3.40.5"},"publisher-location":"Cham","reference-count":19,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031929311","type":"print"},{"value":"9783031929328","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-3-031-92932-8_3","type":"book-chapter","created":{"date-parts":[[2025,5,17]],"date-time":"2025-05-17T07:47:15Z","timestamp":1747468035000},"page":"34-50","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On Exact Learning of\u00a0d-Monotone Functions"],"prefix":"10.1007","author":[{"given":"Nader H.","family":"Bshouty","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,5,18]]},"reference":[{"key":"3_CR1","doi-asserted-by":"publisher","unstructured":"Amano, K., Maruoka, A.: On learning monotone Boolean functions under the uniform distribution. Theor. Comput. Sci. 350(1), 3\u201312 (2006). https:\/\/doi.org\/10.1016\/J.TCS.2005.10.012","DOI":"10.1016\/J.TCS.2005.10.012"},{"issue":"4","key":"3_CR2","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/BF00116828","volume":"2","author":"D Angluin","year":"1987","unstructured":"Angluin, D.: Queries and concept learning. Mach. Learn. 2(4), 319\u2013342 (1987). https:\/\/doi.org\/10.1007\/BF00116828","journal-title":"Mach. Learn."},{"key":"3_CR3","doi-asserted-by":"publisher","unstructured":"Black, H.: Nearly optimal bounds for sample-based testing and learning of \\$k\\$-monotone functions. CoRR abs\/2310.12375 (2023). https:\/\/doi.org\/10.48550\/ARXIV.2310.12375","DOI":"10.48550\/ARXIV.2310.12375"},{"key":"3_CR4","doi-asserted-by":"publisher","unstructured":"Blais, E., Canonne, C.L., Oliveira, I.C., Servedio, R.A., Tan, L.: Learning circuits with few negations. In: Garg, N., Jansen, K., Rao, A., Rolim, J.D.P. (eds.) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM 2015, Princeton, NJ, USA, 24\u201326 August 2015. LIPIcs, vol.\u00a040, pp. 512\u2013527. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2015). https:\/\/doi.org\/10.4230\/LIPICS.APPROX-RANDOM.2015.512","DOI":"10.4230\/LIPICS.APPROX-RANDOM.2015.512"},{"key":"3_CR5","doi-asserted-by":"publisher","unstructured":"Blum, A., Burch, C., Langford, J.: On learning monotone Boolean functions. In: 39th Annual Symposium on Foundations of Computer Science, FOCS 1998, Palo Alto, California, USA, 8\u201311 November 1998, pp. 408\u2013415. IEEE Computer Society (1998). https:\/\/doi.org\/10.1109\/SFCS.1998.743491","DOI":"10.1109\/SFCS.1998.743491"},{"issue":"1","key":"3_CR6","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1006\/INCO.1995.1164","volume":"123","author":"NH Bshouty","year":"1995","unstructured":"Bshouty, N.H.: Exact learning Boolean function via the monotone theory. Inf. Comput. 123(1), 146\u2013153 (1995). https:\/\/doi.org\/10.1006\/INCO.1995.1164","journal-title":"Inf. Comput."},{"issue":"2","key":"3_CR7","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1007\/BF01262930","volume":"6","author":"NH Bshouty","year":"1997","unstructured":"Bshouty, N.H.: Simple learning algorithms using divide and conquer. Comput. Complex. 6(2), 174\u2013194 (1997). https:\/\/doi.org\/10.1007\/BF01262930","journal-title":"Comput. Complex."},{"key":"3_CR8","unstructured":"Bshouty, N.H.: On exact learning of $$d$$-monotone functions (2025). https:\/\/arxiv.org\/abs\/2502.01265"},{"issue":"4","key":"3_CR9","doi-asserted-by":"publisher","first-page":"747","DOI":"10.1145\/234533.234564","volume":"43","author":"NH Bshouty","year":"1996","unstructured":"Bshouty, N.H., Tamon, C.: On the Fourier spectrum of monotone functions. J. ACM 43(4), 747\u2013770 (1996). https:\/\/doi.org\/10.1145\/234533.234564","journal-title":"J. ACM"},{"issue":"3","key":"3_CR10","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/S004930070011","volume":"20","author":"O Goldreich","year":"2000","unstructured":"Goldreich, O., Goldwasser, S., Lehman, E., Ron, D., Samorodnitsky, A.: Testing monotonicity. Combinatorica 20(3), 301\u2013337 (2000). https:\/\/doi.org\/10.1007\/S004930070011","journal-title":"Combinatorica"},{"issue":"1\u20132","key":"3_CR11","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1016\/S0304-3975(00)00043-8","volume":"259","author":"D Guijarro","year":"2001","unstructured":"Guijarro, D., Lav\u00edn, V., Raghavan, V.: Monotone term decision lists. Theor. Comput. Sci. 259(1\u20132), 549\u2013575 (2001). https:\/\/doi.org\/10.1016\/S0304-3975(00)00043-8","journal-title":"Theor. Comput. Sci."},{"key":"3_CR12","doi-asserted-by":"publisher","unstructured":"Harms, N., Yoshida, Y.: Downsampling for testing and learning in product distributions. In: Bojanczyk, M., Merelli, E., Woodruff, D.P. (eds.) 49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, Paris, France, 4\u20138 July 2022. LIPIcs, vol.\u00a0229, pp. 71:1\u201371:19. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2022). https:\/\/doi.org\/10.4230\/LIPICS.ICALP.2022.71","DOI":"10.4230\/LIPICS.ICALP.2022.71"},{"key":"3_CR13","doi-asserted-by":"publisher","unstructured":"Lange, J., Rubinfeld, R., Vasilyan, A.: Properly learning monotone functions via local correction. In: 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, 31 October\u20133 November 2022, pp. 75\u201386. IEEE (2022). https:\/\/doi.org\/10.1109\/FOCS54457.2022.00015","DOI":"10.1109\/FOCS54457.2022.00015"},{"key":"3_CR14","doi-asserted-by":"publisher","unstructured":"Lange, J., Vasilyan, A.: Agnostic proper learning of monotone functions: beyond the black-box correction barrier. In: 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, 6\u20139 November 2023, pp. 1149\u20131170. IEEE (2023). https:\/\/doi.org\/10.1109\/FOCS57990.2023.00068","DOI":"10.1109\/FOCS57990.2023.00068"},{"issue":"4","key":"3_CR15","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1145\/320941.320945","volume":"5","author":"AA Markov","year":"1958","unstructured":"Markov, A.A.: On the inversion complexity of a system of functions. J. ACM 5(4), 331\u2013334 (1958). https:\/\/doi.org\/10.1145\/320941.320945","journal-title":"J. ACM"},{"issue":"3","key":"3_CR16","doi-asserted-by":"publisher","first-page":"827","DOI":"10.1137\/060669309","volume":"37","author":"R O\u2019Donnell","year":"2007","unstructured":"O\u2019Donnell, R., Servedio, R.A.: Learning monotone decision trees in polynomial time. SIAM J. Comput. 37(3), 827\u2013844 (2007). https:\/\/doi.org\/10.1137\/060669309","journal-title":"SIAM J. Comput."},{"key":"3_CR17","doi-asserted-by":"publisher","unstructured":"O\u2019Donnell, R., Wimmer, K.: KKL, Kruskal-Katona, and monotone nets. In: 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, Atlanta, Georgia, USA, 25\u201327 October 2009, pp. 725\u2013734. IEEE Computer Society (2009). https:\/\/doi.org\/10.1109\/FOCS.2009.78","DOI":"10.1109\/FOCS.2009.78"},{"issue":"1","key":"3_CR18","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/J.IC.2004.04.003","volume":"193","author":"RA Servedio","year":"2004","unstructured":"Servedio, R.A.: On learning monotone DNF under product distributions. Inf. Comput. 193(1), 57\u201374 (2004). https:\/\/doi.org\/10.1016\/J.IC.2004.04.003","journal-title":"Inf. Comput."},{"issue":"1\u20132","key":"3_CR19","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/S0304-3975(99)00265-0","volume":"241","author":"E Takimoto","year":"2000","unstructured":"Takimoto, E., Sakai, Y., Maruoka, A.: The learnability of exclusive-or expansions based on monotone DNF formulas. Theor. Comput. Sci. 241(1\u20132), 37\u201350 (2000). https:\/\/doi.org\/10.1016\/S0304-3975(99)00265-0","journal-title":"Theor. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-92932-8_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,17]],"date-time":"2025-05-17T07:47:17Z","timestamp":1747468037000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-92932-8_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031929311","9783031929328"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-92932-8_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"18 May 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CIAC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Algorithms and Complexity","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Rome","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10 June 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12 June 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ciac2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/easyconferences.eu\/ciac2025\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}