{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:23:51Z","timestamp":1750281831642,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":56,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T00:00:00Z","timestamp":1592784000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Narodowe Centrum Nauki","award":["2017\/27\/N\/ST6\/02719"],"award-info":[{"award-number":["2017\/27\/N\/ST6\/02719"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,6,22]]},"DOI":"10.1145\/3357713.3384275","type":"proceedings-article","created":{"date-parts":[[2020,6,7]],"date-time":"2020-06-07T01:45:25Z","timestamp":1591494325000},"page":"974-981","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["All non-trivial variants of 3-LDT are equivalent"],"prefix":"10.1145","author":[{"given":"Bart\u0142omiej","family":"Dudek","sequence":"first","affiliation":[{"name":"University of Wroc\u0142aw, Poland"}]},{"given":"Pawe\u0142","family":"Gawrychowski","sequence":"additional","affiliation":[{"name":"University of Wroc\u0142aw, Poland"}]},{"given":"Tatiana","family":"Starikovskaya","sequence":"additional","affiliation":[{"name":"PSL University, France"}]}],"member":"320","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3088511"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.3"},{"key":"e_1_3_2_1_3_1","volume-title":"Scheduling lower bounds via AND subset sum. CoRR, abs\/","author":"Abboud Amir","year":"2003","unstructured":"Amir Abboud , Karl Bringmann , Danny Hermelin , and Dvir Shabtay . Scheduling lower bounds via AND subset sum. CoRR, abs\/ 2003 .07113, 2020. Amir Abboud, Karl Bringmann, Danny Hermelin, and Dvir Shabtay. Scheduling lower bounds via AND subset sum. CoRR, abs\/ 2003.07113, 2020."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39206-1_1"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44777-2_1"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.53"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43948-7_4"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44676-1_23"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1059513.1059515"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930070001"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/210332.210337"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43948-7_10"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195905001841"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009204"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/060669474"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9036-3"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-018-0040-y"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195901000596"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.32.12.331"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0010-4485(97)00075-4"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.57"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746568"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808737"},{"key":"e_1_3_2_1_24_1","first-page":"1098","volume-title":"15th SODA","author":"Cheong Otfried","year":"2004","unstructured":"Otfried Cheong , Alon Efrat , and Sariel Har-Peled . On finding a guard that sees most and a shop that sells most . In 15th SODA , pages 1098 - 1107 , 2004 . doi: 10.5555\/982792.982954. 10.5555\/982792.982954 Otfried Cheong, Alon Efrat, and Sariel Har-Peled. On finding a guard that sees most and a shop that sells most. In 15th SODA, pages 1098-1107, 2004. doi: 10.5555\/982792.982954."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(08)80013-2"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(95)00045-3"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629620"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973075.72"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-11.4.261"},{"key":"e_1_3_2_1_30_1","first-page":"388","volume-title":"6th SODA","author":"Erickson Jef","year":"1995","unstructured":"Jef Erickson . Lower bounds for linear satisfiability problems . In 6th SODA , pages 388 - 395 , 1995 . doi: 10.5555\/313651.313772. 10.5555\/313651.313772 Jef Erickson. Lower bounds for linear satisfiability problems. In 6th SODA, pages 388-395, 1995. doi: 10.5555\/313651.313772."},{"key":"e_1_3_2_1_31_1","volume-title":"Manuscript","author":"Erickson Jef","year":"1999","unstructured":"Jef Erickson . Finding longest arithmetic progressions . Manuscript , 1999 . Jef Erickson. Finding longest arithmetic progressions. Manuscript, 1999."},{"key":"e_1_3_2_1_32_1","volume":"199","author":"Erickson Jef","unstructured":"Jef Erickson . Lower bounds for linear satisfiability problems. Chicago J. Theor. Comput. Sci. , 199 9. Jef Erickson. Lower bounds for linear satisfiability problems. Chicago J. Theor. Comput. Sci., 1999.","journal-title":"Chicago J. Theor. Comput. Sci."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797315410"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-006-1267-6"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/130910932"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-015-0079-6"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2011.11.006"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA.2017.42"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA.2016.45"},{"key":"e_1_3_2_1_40_1","volume-title":"3SUM with preprocessing: Algorithms, lower bounds and cryptographic applications. CoRR, abs\/","author":"Golovnev Alexander","year":"1907","unstructured":"Alexander Golovnev , Siyao Guo , Thibaut Horel , Sunoo Park , and Vinod Vaikuntanathan . 3SUM with preprocessing: Algorithms, lower bounds and cryptographic applications. CoRR, abs\/ 1907 .08355, 2019. Alexander Golovnev, Siyao Guo, Thibaut Horel, Sunoo Park, and Vinod Vaikuntanathan. 3SUM with preprocessing: Algorithms, lower bounds and cryptographic applications. CoRR, abs\/ 1907.08355, 2019."},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3185378"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10068"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9946-9"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2012.04.004"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3285953"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch89"},{"key":"e_1_3_2_1_47_1","volume-title":"The strong 3SUM-indexing conjecture is false. CoRR, abs\/","author":"Kopelowitz Tsvi","year":"1907","unstructured":"Tsvi Kopelowitz and Ely Porat . The strong 3SUM-indexing conjecture is false. CoRR, abs\/ 1907 .11206, 2019. Tsvi Kopelowitz and Ely Porat. The strong 3SUM-indexing conjecture is false. CoRR, abs\/ 1907.11206, 2019."},{"key":"e_1_3_2_1_48_1","volume-title":"An annotated bibliography on 3SUM-hard problems. https: \/\/sarielhp.org\/research\/CG\/collection\/04\/3sumhard.pdf","author":"Lafeber Martijn","year":"2004","unstructured":"Martijn Lafeber . An annotated bibliography on 3SUM-hard problems. https: \/\/sarielhp.org\/research\/CG\/collection\/04\/3sumhard.pdf , 2004 . Martijn Lafeber. An annotated bibliography on 3SUM-hard problems. https: \/\/sarielhp.org\/research\/CG\/collection\/04\/3sumhard.pdf, 2004."},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806772"},{"key":"e_1_3_2_1_50_1","volume-title":"Solving a linear equation in a set of integers I. Acta Arithmetica LXV.3","author":"Ruzsa Imre Z.","year":"1993","unstructured":"Imre Z. Ruzsa . Solving a linear equation in a set of integers I. Acta Arithmetica LXV.3 , 1993 . Imre Z. Ruzsa. Solving a linear equation in a set of integers I. Acta Arithmetica LXV.3, 1993."},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.28.12.561"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1137\/0219054"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(02)00156-6"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.IPEC.2015.17"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186893"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1137\/09076619X"}],"event":{"name":"STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Chicago IL USA","acronym":"STOC '20"},"container-title":["Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384275","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384275","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:12Z","timestamp":1750200072000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384275"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":56,"alternative-id":["10.1145\/3357713.3384275","10.1145\/3357713"],"URL":"https:\/\/doi.org\/10.1145\/3357713.3384275","relation":{},"subject":[],"published":{"date-parts":[[2020,6,22]]},"assertion":[{"value":"2020-06-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}