{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,11,30]],"date-time":"2024-11-30T06:10:41Z","timestamp":1732947041453,"version":"3.30.0"},"reference-count":64,"publisher":"IEEE","license":[{"start":{"date-parts":[[2024,10,27]],"date-time":"2024-10-27T00:00:00Z","timestamp":1729987200000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2024,10,27]],"date-time":"2024-10-27T00:00:00Z","timestamp":1729987200000},"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":[[2024,10,27]]},"DOI":"10.1109\/focs61266.2024.00114","type":"proceedings-article","created":{"date-parts":[[2024,11,29]],"date-time":"2024-11-29T18:48:52Z","timestamp":1732906132000},"page":"1893-1910","source":"Crossref","is-referenced-by-count":0,"title":["Fast Decision Tree Learning Solves Hard Coding-Theoretic Problems"],"prefix":"10.1109","author":[{"given":"Caleb","family":"Koch","sequence":"first","affiliation":[{"name":"Stanford University,Department of Computer Science,Stanford,United States"}]},{"given":"Carmen","family":"Strassle","sequence":"additional","affiliation":[{"name":"Stanford University,Department of Computer Science,Stanford,United States"}]},{"given":"Li-Yang","family":"Tan","sequence":"additional","affiliation":[{"name":"Stanford University,Department of Computer Science,Stanford,United States"}]}],"member":"263","reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.04.011"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1472"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-011-0031-3"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-011-0029-x"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44777-2_1"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03685-9_26"},{"key":"ref7","article-title":"Towards a theory of model distillation","author":"Boix-Adsera","year":"2024","journal-title":"arXiv preprint"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1145\/3444942"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585214"},{"key":"ref10","article-title":"Fixed-parameter approximability of boolean MinC-S Ps","author":"Bonnet","year":"2016","journal-title":"arXiv preprint"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48329-2_24"},{"key":"ref12","first-page":"17:1","article-title":"Parameterized intractability of even set and shortest vector problem from Gap- Eth","volume-title":"Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP)","volume":"107","author":"Bhattacharyya","year":"2018"},{"key":"ref13","first-page":"496","article-title":"The complexity of linear dependence problems in vector spaces","author":"Bhattacharyya","year":"2011","journal-title":"ICS"},{"key":"ref14","first-page":"514","article-title":"Approximating minimum unsatisfiability of linear equations","volume-title":"Proceedings of the 13th annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Berman","year":"2002"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1145\/792538.792543"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(97)00063-5"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1145\/3561047"},{"key":"ref18","first-page":"1","article-title":"Top-down induction of decision trees: rigorous guarantees and inherent limitations","volume-title":"Proceedings of the 11th Innovations in Theoretical Computer Science Conference (ITCS)","volume":"151","author":"Blanc","year":"2020"},{"key":"ref19","first-page":"1","article-title":"Relevant examples and relevant features: Thoughts from computational learning theory","volume-title":"AAAI Fall Symposium on Relevance","volume":"5","author":"Blum","year":"1994"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1978.1055873"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1109\/18.52484"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1993.366857"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939785"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1137\/s0097539797323571"},{"key":"ref27","article-title":"Mildly exponential reduction from gap-3sat to polynomial-gap label-cover","author":"Dinur","year":"2016","journal-title":"Electronic colloquium on computational complexity ECCC; research reports, surveys and books in computational complexity"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-003-0019-y"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1998.743433"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2002.806118"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(89)90001-1"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.3390\/a13060146"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.01.002"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374451"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649771"},{"key":"ref36","first-page":"507","article-title":"Why do tree-based models still outperform deep learning on typical tabular data?","volume":"35","author":"Grinsztajn","year":"2022","journal-title":"Advances in Neural Information Processing Systems (NeurIPS)"},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.850102"},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1996.0040"},{"key":"ref39","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704444555"},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.1137\/0222080"},{"issue":"3","key":"ref43","doi-asserted-by":"crossref","first-page":"1184","DOI":"10.1137\/130919623","article-title":"Almost polynomial factor hardness for closest vector problem with preprocessing","volume":"43","author":"Subhash","year":"2014","journal-title":"SIAM Journal on Computing"},{"key":"ref44","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.60"},{"key":"ref45","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00146"},{"key":"ref46","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch75"},{"journal-title":"Improved lower bounds for approximating parameterized nearest codeword and related problems under ETH","year":"2024","author":"Li","key":"ref47"},{"key":"ref48","doi-asserted-by":"publisher","DOI":"10.1109\/18.53763"},{"key":"ref49","article-title":"On lower bounds of approximating parameterized k-clique","volume-title":"Proceedings of the 49th International Colloquium on Automata, Languages, and Programming (ICALP)","author":"Lin","year":"2022"},{"key":"ref50","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.5"},{"volume-title":"Project: Complexity of coding problems","author":"Micciancio","key":"ref51"},{"key":"ref52","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.04.002"},{"key":"ref53","first-page":"78:1","article-title":"A Birthday Repetition Theorem and Complexity of Approximating Dense CSPs","volume-title":"Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP)","volume":"80","author":"Manurangsi","year":"2017"},{"key":"ref54","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139814782"},{"key":"ref55","doi-asserted-by":"publisher","DOI":"10.1137\/060669309"},{"key":"ref56","doi-asserted-by":"publisher","DOI":"10.1145\/48014.63140"},{"key":"ref57","doi-asserted-by":"publisher","DOI":"10.1214\/21-SS133"},{"key":"ref58","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2003.1214435"},{"key":"ref59","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00027"},{"key":"ref60","doi-asserted-by":"publisher","DOI":"10.1145\/168304.168307"},{"key":"ref61","doi-asserted-by":"publisher","DOI":"10.1016\/j.inffus.2021.11.011"},{"key":"ref62","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(84)90081-7"},{"key":"ref63","doi-asserted-by":"publisher","DOI":"10.1145\/1968.1972"},{"key":"ref64","doi-asserted-by":"publisher","DOI":"10.1145\/2728167"}],"event":{"name":"2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)","start":{"date-parts":[[2024,10,27]]},"location":"Chicago, IL, USA","end":{"date-parts":[[2024,10,30]]}},"container-title":["2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)"],"original-title":[],"link":[{"URL":"http:\/\/xplorestaging.ieee.org\/ielx8\/10755992\/10756014\/10756046.pdf?arnumber=10756046","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,30]],"date-time":"2024-11-30T05:51:27Z","timestamp":1732945887000},"score":1,"resource":{"primary":{"URL":"https:\/\/ieeexplore.ieee.org\/document\/10756046\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,27]]},"references-count":64,"URL":"https:\/\/doi.org\/10.1109\/focs61266.2024.00114","relation":{},"subject":[],"published":{"date-parts":[[2024,10,27]]}}}