{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2020,9,8]],"date-time":"2020-09-08T14:44:24Z","timestamp":1599576264216},"publisher-location":"New York, New York, USA","reference-count":22,"publisher":"ACM Press","isbn-type":[{"value":"9781450355599","type":"print"}],"license":[{"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background","start":{"date-parts":[[2018,6,20]],"date-time":"2018-06-20T00:00:00Z","timestamp":1529452800000},"delay-in-days":170,"content-version":"vor"}],"funder":[{"name":"NSF","award":["1553288,1350481,1614023"]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1145\/3188745.3188770","type":"proceedings-article","created":{"date-parts":[[2018,6,20]],"date-time":"2018-06-20T20:15:46Z","timestamp":1529525746000},"source":"Crossref","is-referenced-by-count":3,"title":["Near-optimal linear decision trees for k-SUM and related problems"],"prefix":"10.1145","author":[{"given":"Daniel M.","family":"Kane","sequence":"first","affiliation":[{"name":"University of California at San Diego, USA"}]},{"given":"Shachar","family":"Lovett","sequence":"additional","affiliation":[{"name":"University of California at San Diego, USA"}]},{"given":"Shay","family":"Moran","sequence":"additional","affiliation":[{"name":"Institute for Advanced Study at Princeton, USA"}]}],"member":"320","reference":[{"key":"key-10.1145\/3188745.3188770-1","unstructured":"[AC05] Nir Ailon and Bernard Chazelle. Lower bounds for linear degeneracy testing. Journal of the ACM (JACM), 52(2):157–171, 2005.","DOI":"10.1145\/1059513.1059515","doi-asserted-by":"crossref"},{"key":"key-10.1145\/3188745.3188770-2","unstructured":"[CGI + 16] Marco L Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mihajlin, Ramamohan Paturi, and Stefan Schneider. Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, pages 261–270. ACM, 2016.","DOI":"10.1145\/2840728.2840746","doi-asserted-by":"crossref"},{"key":"key-10.1145\/3188745.3188770-3","unstructured":"[CIO16] Jean Cardinal, John Iacono, and Aurélien Ooms. Solving k-SUM using few linear queries. In 24th Annual European Symposium on Algorithms, ESA 2016, pages 25:1–25:17, 2016."},{"key":"key-10.1145\/3188745.3188770-4","unstructured":"[CL15] Timothy M Chan and Moshe Lewenstein. Clustered integer 3SUM via additive combinatorics. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, pages 31–40. ACM, 2015."},{"key":"key-10.1145\/3188745.3188770-5","unstructured":"[DL74] David Dobkin and Richard J Lipton. On some generalizations of binary search. In Proceedings of the sixth annual ACM symposium on Theory of computing, pages 310–316. ACM, 1974.","DOI":"10.1145\/800119.803909","doi-asserted-by":"crossref"},{"key":"key-10.1145\/3188745.3188770-6","unstructured":"[Eri99] Jeff Erickson. Bounds for linear satisfiability problems. Chicago Journal of Theoretical Computer Science, page 8, 1999."},{"key":"key-10.1145\/3188745.3188770-7","unstructured":"[ES17] Esther Ezra and Micha Sharir. A nearly quadratic bound for the decision tree complexity of k-SUM. In 33rd International Symposium on Computational Geometry, SoCG 2017, pages 41:1–41:15, 2017."},{"key":"key-10.1145\/3188745.3188770-8","unstructured":"[Fre76a] Michael L Fredman. How good is the information theory bound in sorting? Theoretical Computer Science, 1(4):355–361, 1976.","DOI":"10.1016\/0304-3975(76)90078-5","doi-asserted-by":"crossref"},{"key":"key-10.1145\/3188745.3188770-9","unstructured":"[Fre76b] Michael L Fredman. New bounds on the complexity of the shortest path problem. SIAM Journal on Computing, 5(1):83–89, 1976.","DOI":"10.1137\/0205006","doi-asserted-by":"crossref"},{"key":"key-10.1145\/3188745.3188770-10","unstructured":"[GO95] Anka Gajentaan and Mark H Overmars. On a class of o(n 2 ) problems in computational geometry. Computational geometry, 5(3):165–185, 1995.","DOI":"10.1016\/0925-7721(95)00022-2","doi-asserted-by":"crossref"},{"key":"key-10.1145\/3188745.3188770-11","unstructured":"[GP14] Allan Grønlund and Seth Pettie. Threesomes, degenerates, and love triangles. In Foundations of Computer Science (FOCS), 2014 IEEE 55th Annual Symposium on, pages 621–630. IEEE, 2014."},{"key":"key-10.1145\/3188745.3188770-12","unstructured":"[GS17] Omer Gold and Micha Sharir. Improved bounds for 3sum, k-sum, and linear degeneracy. In 25th Annual European Symposium on Algorithms, ESA 2017, pages 42:1–42:13, 2017."},{"key":"key-10.1145\/3188745.3188770-13","unstructured":"[GT62] Eiichi Goto and Hidetosi Takahasi. Some theorems useful in threshold logic for enumerating boolean functions. In IFIP Congress, pages 747–752, 1962."},{"key":"key-10.1145\/3188745.3188770-14","unstructured":"[KLMZ17] Daniel M Kane, Shachar Lovett, Shay Moran, and Jiapeng Zhang. Active classification with comparison queries. arXiv preprint arXiv:1704.03564, 2017."},{"key":"key-10.1145\/3188745.3188770-15","unstructured":"[MadH84] Friedhelm Meyer auf der Heide. A polynomial linear search algorithm for the n-dimensional knapsack problem. Journal of the ACM (JACM), 31(3):668–676, 1984.","DOI":"10.1145\/828.322450","doi-asserted-by":"crossref"},{"key":"key-10.1145\/3188745.3188770-16","unstructured":"STOC’18, June 25–29, 2018, Los Angeles, CA, USA Daniel M. Kane, Shachar Lovett, and Shay Moran [Mei93] Stefan Meiser. Point location in arrangements of hyperplanes. Information and Computation, 106(2):286–303, 1993.","DOI":"10.1006\/inco.1993.1057","doi-asserted-by":"crossref"},{"key":"key-10.1145\/3188745.3188770-17","unstructured":"[Pet02] Seth Pettie. On the comparison-addition complexity of all-pairs shortest paths. In Algorithms and Computation, 13th International Symposium, ISAAC 2002 Vancouver, BC, Canada, November 21-23, 2002, Proceedings, pages 32–43, 2002.","DOI":"10.1007\/3-540-36136-7_4","doi-asserted-by":"crossref"},{"key":"key-10.1145\/3188745.3188770-18","unstructured":"[VC71] VN Vapnik and A Ya Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability & Its Applications, 16(2):264–280, 1971.","DOI":"10.1137\/1116025","doi-asserted-by":"crossref"},{"key":"key-10.1145\/3188745.3188770-19","unstructured":"[VC15] Vladimir N Vapnik and A Ya Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. In Measures of Complexity, pages 11–30. Springer, 2015.","DOI":"10.1007\/978-3-319-21852-6_3","doi-asserted-by":"crossref"},{"key":"key-10.1145\/3188745.3188770-20","unstructured":"[VW15] Virginia Vassilevska Williams. Hardness of easy problems: Basing hardness on popular conjectures such as the strong exponential time hypothesis (invited talk). In LIPIcs-Leibniz International Proceedings in Informatics, volume 43. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2015."},{"key":"key-10.1145\/3188745.3188770-21","unstructured":"[Wil14] Ryan Williams. Faster all-pairs shortest paths via circuit complexity. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 664–673. ACM, 2014.","DOI":"10.1145\/2591796.2591811","doi-asserted-by":"crossref"},{"key":"key-10.1145\/3188745.3188770-22","unstructured":"[Yao81] Andrew Chi-Chih Yao. On the parallel computation for the knapsack problem. In Proceedings of the thirteenth annual ACM symposium on Theory of computing, pages 123–127. ACM, 1981.","DOI":"10.1145\/800076.802465","doi-asserted-by":"crossref"}],"event":{"name":"the 50th Annual ACM SIGACT Symposium","location":"Los Angeles, CA, USA","sponsor":["SIGACT, ACM Special Interest Group on Algorithms and Computation Theory"],"acronym":"STOC 2018","number":"2018","start":{"date-parts":[[2018,6,25]]},"end":{"date-parts":[[2018,6,29]]}},"container-title":["Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing - STOC 2018"],"original-title":[],"link":[{"URL":"http:\/\/dl.acm.org\/ft_gateway.cfm?id=3188770&ftid=1981429&dwn=1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,19]],"date-time":"2019-10-19T19:45:02Z","timestamp":1571514302000},"score":1.0,"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9781450355599"],"references-count":22,"URL":"http:\/\/dx.doi.org\/10.1145\/3188745.3188770","relation":{"cites":[]}}}