{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,10,29]],"date-time":"2024-10-29T17:12:41Z","timestamp":1730221961168,"version":"3.28.0"},"reference-count":51,"publisher":"IEEE","license":[{"start":{"date-parts":[[2023,11,6]],"date-time":"2023-11-06T00:00:00Z","timestamp":1699228800000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2023,11,6]],"date-time":"2023-11-06T00:00:00Z","timestamp":1699228800000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023,11,6]]},"DOI":"10.1109\/focs57990.2023.00146","type":"proceedings-article","created":{"date-parts":[[2023,12,22]],"date-time":"2023-12-22T19:20:35Z","timestamp":1703272835000},"page":"2383-2407","source":"Crossref","is-referenced-by-count":1,"title":["Properly learning decision trees with queries is NP-hard"],"prefix":"10.1109","author":[{"given":"Caleb","family":"Koch","sequence":"first","affiliation":[{"name":"Stanford University,Stanford,USA"}]},{"given":"Carmen","family":"Strassle","sequence":"additional","affiliation":[{"name":"Stanford University,Stanford,USA"}]},{"given":"Li-Yang","family":"Tan","sequence":"additional","affiliation":[{"name":"Stanford University,Stanford,USA"}]}],"member":"263","reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1214\/ss\/1009213726"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1214\/21-ss133"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1145\/1968.1972"},{"key":"ref4","first-page":"24","article-title":"Extracting tree-structured representations of trained networks","volume-title":"Proceedings of the 8th Conference on Advances in Neural Information Processing Systems (NeurIPS)","volume":"8","author":"Craven"},{"volume-title":"Born again trees","year":"1996","author":"Breiman","key":"ref5"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74958-5_39"},{"volume-title":"Interpreting models via single tree approximation","year":"2016","author":"Zhou","key":"ref7"},{"article-title":"Interpretability via model extraction","volume-title":"Proceedings of the 4th Workshop on Fairness, Accountability, and Transparency in Machine Learning (FAT\/ML)","author":"Bastani","key":"ref8"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-67274-8_10"},{"key":"ref10","article-title":"Distilling a neural network into a soft decision tree","author":"Frosst","year":"2017","journal-title":"arXiv preprint arXiv:1711.09784"},{"key":"ref11","first-page":"9743","article-title":"Born-again tree ensembles","volume-title":"Proceedings of the 37th International Conference on Machine Learning (ICML)","author":"Vidal"},{"journal-title":"unpublished Manuscript","article-title":"Remarks on the difficulty of finding a minimal disjunctive normal form for boolean functions","author":"Angluin","key":"ref12"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1145\/48014.63140"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1993.366857"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(99)00063-0"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00011-1"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4939-2864-4_177"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1996.0040"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.04.011"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch75"},{"key":"ref21","article-title":"Superpolynomial lower bounds for learning monotone classes","volume-title":"Electron. Colloquium Comput. Complex","volume":"TR23-006","author":"Bshouty","year":"2023"},{"key":"ref22","first-page":"265","article-title":"Universal sorting problem","volume":"9","author":"Levin","year":"1973","journal-title":"Problemy Predaci Informacii"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(88)90002-1"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1145\/76359.76371"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(89)90001-1"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1007\/BF00116828"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1137\/0222080"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1145\/168304.168307"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1145\/3561047"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195147"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132569"},{"first-page":"560","article-title":"Learning disjunction of conjunctions.\u201d in Proceedings of the 9th International Joint Conference on Artificial Intelligence (IJCAI)","author":"Valiant","key":"ref32"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(76)90095-8"},{"volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman","year":"1979","author":"Garey","key":"ref34"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48447-7_17"},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054100000193"},{"key":"ref37","first-page":"157","article-title":"On the proper learning of axis-parallel concepts","volume":"4","author":"Bshouty","year":"2003","journal-title":"The Journal of Machine Learning Research"},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2004.06.002"},{"key":"ref39","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265538"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2006.08.012"},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.06.014"},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-011-9510-9"},{"key":"ref43","article-title":"Truth table minimization of computational models","volume":"abs\/1306.3766","author":"Raviv","year":"2013","journal-title":"CoRR"},{"key":"ref44","first-page":"45:1","article-title":"Decision tree heuristics can fail, even in the smoothed setting","volume-title":"Proceedings of the 25th International Conference on Randomization and Computation (RANDOM)","volume":"207","author":"Blanc"},{"key":"ref45","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285060"},{"key":"ref46","doi-asserted-by":"publisher","DOI":"10.1145\/1236457.1236459"},{"key":"ref47","doi-asserted-by":"publisher","DOI":"10.1137\/050646445"},{"key":"ref48","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90023-X"},{"key":"ref49","doi-asserted-by":"publisher","DOI":"10.1145\/273865.273901"},{"key":"ref50","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"ref51","doi-asserted-by":"publisher","DOI":"10.1002\/9781119005353.ch13"}],"event":{"name":"2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)","start":{"date-parts":[[2023,11,6]]},"location":"Santa Cruz, CA, USA","end":{"date-parts":[[2023,11,9]]}},"container-title":["2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)"],"original-title":[],"link":[{"URL":"http:\/\/xplorestaging.ieee.org\/ielx7\/10353068\/10353072\/10353131.pdf?arnumber=10353131","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,12]],"date-time":"2024-01-12T20:16:55Z","timestamp":1705090615000},"score":1,"resource":{"primary":{"URL":"https:\/\/ieeexplore.ieee.org\/document\/10353131\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,6]]},"references-count":51,"URL":"https:\/\/doi.org\/10.1109\/focs57990.2023.00146","relation":{},"subject":[],"published":{"date-parts":[[2023,11,6]]}}}