{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:42:24Z","timestamp":1781077344945,"version":"3.54.1"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2019,4,12]],"date-time":"2019-04-12T00:00:00Z","timestamp":1555027200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"CCF","award":["1614023"],"award-info":[{"award-number":["1614023"]}]},{"name":"NSF CAREER","award":["1553288 and 1350481"],"award-info":[{"award-number":["1553288 and 1350481"]}]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-1412958"],"award-info":[{"award-number":["CCF-1412958"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Sloan fellowship"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2019,6,30]]},"abstract":"<jats:p>\n            We construct near-optimal linear decision trees for a variety of decision problems in combinatorics and discrete geometry. For example, for any constant\n            <jats:italic>k<\/jats:italic>\n            , we construct linear decision trees that solve the\n            <jats:italic>k<\/jats:italic>\n            -SUM problem on\n            <jats:italic>n<\/jats:italic>\n            elements using\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            log\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ) linear queries. Moreover, the queries we use are comparison queries, which compare the sums of two\n            <jats:italic>k<\/jats:italic>\n            -subsets; when viewed as linear queries, comparison queries are 2\n            <jats:italic>k<\/jats:italic>\n            -sparse and have only { \u22121,0,1} coefficients. We give similar constructions for sorting sumsets A+B and for solving the SUBSET-SUM problem, both with optimal number of queries, up to poly-logarithmic terms.\n          <\/jats:p>\n          <jats:p>Our constructions are based on the notion of \u201cinference dimension,\u201d recently introduced by the authors in the context of active classification with comparison queries. This can be viewed as another contribution to the fruitful link between machine learning and discrete geometry, which goes back to the discovery of the VC dimension.<\/jats:p>","DOI":"10.1145\/3285953","type":"journal-article","created":{"date-parts":[[2019,4,15]],"date-time":"2019-04-15T12:07:04Z","timestamp":1555330024000},"page":"1-18","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["Near-optimal Linear Decision Trees for k-SUM and Related Problems"],"prefix":"10.1145","volume":"66","author":[{"given":"Daniel M.","family":"Kane","sequence":"first","affiliation":[{"name":"University of California, San Diego, La Jolla, CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4552-1443","authenticated-orcid":false,"given":"Shachar","family":"Lovett","sequence":"additional","affiliation":[{"name":"University of California, San Diego, La Jolla, CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shay","family":"Moran","sequence":"additional","affiliation":[{"name":"Princeton University, Princeton, NJ, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,4,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1059513.1059515"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2840728.2840746"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 24th Annual European Symposium on Algorithms (ESA\u201916)","author":"Cardinal Jean","year":"2016","unstructured":"Jean Cardinal , John Iacono , and Aur\u00e9lien Ooms . 2016 . Solving k-SUM using few linear queries . In Proceedings of the 24th Annual European Symposium on Algorithms (ESA\u201916) . 25:1--25:17. Jean Cardinal, John Iacono, and Aur\u00e9lien Ooms. 2016. Solving k-SUM using few linear queries. In Proceedings of the 24th Annual European Symposium on Algorithms (ESA\u201916). 25:1--25:17."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746568"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884522"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/800119.803909"},{"key":"e_1_2_1_7_1","volume-title":"Bounds for linear satisfiability problems. Chi. J. Theor. Comput. Sci. 8","author":"Erickson Jeff","year":"1999","unstructured":"Jeff Erickson . 1999. Bounds for linear satisfiability problems. Chi. J. Theor. Comput. Sci. 8 ( 1999 ). Jeff Erickson. 1999. Bounds for linear satisfiability problems. Chi. J. Theor. Comput. Sci. 8 (1999)."},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 33rd International Symposium on Computational Geometry (SoCG\u201917)","author":"Ezra Esther","year":"2017","unstructured":"Esther Ezra and Micha Sharir . 2017 . A nearly quadratic bound for the decision tree complexity of k-SUM . In Proceedings of the 33rd International Symposium on Computational Geometry (SoCG\u201917) . 41:1--41:15. Esther Ezra and Micha Sharir. 2017. A nearly quadratic bound for the decision tree complexity of k-SUM. In Proceedings of the 33rd International Symposium on Computational Geometry (SoCG\u201917). 41:1--41:15."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90078-5"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/0205006"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(95)00022-2"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.72"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 25th Annual European Symposium on Algorithms (ESA\u201917)","author":"Gold Omer","year":"2017","unstructured":"Omer Gold and Micha Sharir . 2017 . Improved bounds for 3SUM, k-SUM, and linear degeneracy . In Proceedings of the 25th Annual European Symposium on Algorithms (ESA\u201917) . 42:1--42:13. Omer Gold and Micha Sharir. 2017. Improved bounds for 3SUM, k-SUM, and linear degeneracy. In Proceedings of the 25th Annual European Symposium on Algorithms (ESA\u201917). 42:1--42:13."},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the IFIP Congress. 747--752","author":"Goto Eiichi","year":"1962","unstructured":"Eiichi Goto and Hidetosi Takahasi . 1962 . Some theorems useful in threshold logic for enumerating Boolean functions . In Proceedings of the IFIP Congress. 747--752 . Eiichi Goto and Hidetosi Takahasi. 1962. Some theorems useful in threshold logic for enumerating Boolean functions. In Proceedings of the IFIP Congress. 747--752."},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP\u201918)","author":"Kane Daniel","year":"2018","unstructured":"Daniel Kane , Shachar Lovett , and Shay Moran . 2018 . Generalized comparison trees for point-location problems . In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP\u201918) . Daniel Kane, Shachar Lovett, and Shay Moran. 2018. Generalized comparison trees for point-location problems. In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP\u201918)."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.40"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884524"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/828.322450"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1993.1057"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806772"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/646345.689915"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/1116025"},{"key":"e_1_2_1_23_1","volume-title":"Measures of Complexity","author":"Vapnik Vladimir N.","unstructured":"Vladimir N. Vapnik and A. Ya Chervonenkis . 2015. On the uniform convergence of relative frequencies of events to their probabilities . In Measures of Complexity . Springer , 11--30. Vladimir N. Vapnik and A. Ya Chervonenkis. 2015. On the uniform convergence of relative frequencies of events to their probabilities. In Measures of Complexity. Springer, 11--30."},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the LIPIcs-Leibniz International Proceedings in Informatics","volume":"43","author":"Williams Virginia Vassilevska","year":"2015","unstructured":"Virginia Vassilevska Williams . 2015 . Hardness of easy problems: Basing hardness on popular conjectures such as the strong exponential time hypothesis (invited talk) . In Proceedings of the LIPIcs-Leibniz International Proceedings in Informatics , vol. 43 . Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Virginia Vassilevska Williams. 2015. Hardness of easy problems: Basing hardness on popular conjectures such as the strong exponential time hypothesis (invited talk). In Proceedings of the LIPIcs-Leibniz International Proceedings in Informatics, vol. 43. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591811"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/800076.802465"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3285953","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3285953","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3285953","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:44:14Z","timestamp":1750207454000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3285953"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,4,12]]},"references-count":26,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,6,30]]}},"alternative-id":["10.1145\/3285953"],"URL":"https:\/\/doi.org\/10.1145\/3285953","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,4,12]]},"assertion":[{"value":"2018-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-04-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}