{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T09:50:33Z","timestamp":1773481833381,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":22,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,6,12]],"date-time":"2022-06-12T00:00:00Z","timestamp":1654992000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["850979"],"award-info":[{"award-number":["850979"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-19-P3IA-0001, ANR-19-CE48-0019"],"award-info":[{"award-number":["ANR-19-P3IA-0001, ANR-19-CE48-0019"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,6,12]]},"DOI":"10.1145\/3517804.3526234","type":"proceedings-article","created":{"date-parts":[[2022,6,13]],"date-time":"2022-06-13T13:29:54Z","timestamp":1655126994000},"page":"427-436","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Tight Fine-Grained Bounds for Direct Access on Join Queries"],"prefix":"10.1145","author":[{"given":"Karl","family":"Bringmann","sequence":"first","affiliation":[{"name":"Saarland University & Max Planck Institute for Informatics, Saarbr\u00fccken, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nofar","family":"Carmeli","sequence":"additional","affiliation":[{"name":"DI ENS, ENS, CNRS, PSL University & Inria, Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefan","family":"Mengel","sequence":"additional","affiliation":[{"name":"Univ. Artois, CNRS, Centre de Recherche en Informatique de Lens (CRIL), Lens, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,6,13]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188938"},{"key":"e_1_3_2_2_2_1","volume-title":"Virginia Vassilevska Williams, and Oren Weimann","author":"Abboud Amir","year":"2014","unstructured":"Amir Abboud , Virginia Vassilevska Williams, and Oren Weimann . 2014 . Con- sequences of Faster Alignment of Sequences. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8--11, 2014, Proceedings, Part I (Lecture Notes in Computer Science), Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias (Eds.), Vol. 8572 . Springer , 39--51. https:\/\/doi.org\/10.1007\/978--3--662--43948--7_4 10.1007\/978--3--662--43948--7_4 Amir Abboud, Virginia Vassilevska Williams, and Oren Weimann. 2014. Con- sequences of Faster Alignment of Sequences. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8--11, 2014, Proceedings, Part I (Lecture Notes in Computer Science), Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias (Eds.), Vol. 8572. Springer, 39--51. https:\/\/doi.org\/10.1007\/978--3--662--43948--7_4"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/110859440"},{"key":"e_1_3_2_2_4_1","volume-title":"43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016","author":"Backurs Arturs","year":"2016","unstructured":"Arturs Backurs , Nishanth Dikkala , and Christos Tzamos . 2016 . Tight Hardness Results for Maximum Weight Rectangles. In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016 , July 11 --15 , 2016, Rome, Italy (LIPIcs), Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi (Eds.), Vol. 55. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 81:1--81:13. https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2016.81 10.4230\/LIPIcs.ICALP.2016.81 Arturs Backurs, Nishanth Dikkala, and Christos Tzamos. 2016. Tight Hardness Results for Maximum Weight Rectangles. In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11--15, 2016, Rome, Italy (LIPIcs), Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi (Eds.), Vol. 55. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 81:1--81:13. https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2016.81"},{"key":"e_1_3_2_2_5_1","volume-title":"Proceedings of the 34th International Conference on Machine Learning, ICML 2017","volume":"70","author":"Backurs Arturs","year":"2017","unstructured":"Arturs Backurs and Christos Tzamos . 2017 . Improving Viterbi is Hard: Better Runtimes Imply Faster Clique Algorithms . In Proceedings of the 34th International Conference on Machine Learning, ICML 2017 , Sydney, NSW, Australia, 6- -11 August 2017 (Proceedings of Machine Learning Research), Doina Precup and Yee Whye Teh (Eds.), Vol. 70 . PMLR, 311--321. http:\/\/proceedings.mlr.press\/v70\/backurs17a.html Arturs Backurs and Christos Tzamos. 2017. Improving Viterbi is Hard: Better Runtimes Imply Faster Clique Algorithms. In Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6--11 August 2017 (Proceedings of Machine Learning Research), Doina Precup and Yee Whye Teh (Eds.), Vol. 70. PMLR, 311--321. http:\/\/proceedings.mlr.press\/v70\/backurs17a.html"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1051\/ita:2007046"},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3385634.3385636"},{"key":"e_1_3_2_2_10_1","volume-title":"Tight Fine-Grained Bounds for Direct Access on Join Queries. CoRR abs\/2201.02401","author":"Bringmann Karl","year":"2022","unstructured":"Karl Bringmann , Nofar Carmeli , and Stefan Mengel . 2022. Tight Fine-Grained Bounds for Direct Access on Join Queries. CoRR abs\/2201.02401 ( 2022 ). arXiv:2201.02401 https:\/\/arxiv.org\/abs\/2201.02401 Karl Bringmann, Nofar Carmeli, and Stefan Mengel. 2022. Tight Fine-Grained Bounds for Direct Access on Join Queries. CoRR abs\/2201.02401 (2022). arXiv:2201.02401 https:\/\/arxiv.org\/abs\/2201.02401"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3381878"},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3452021.3458331"},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3375395.3387662"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2636918"},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884524"},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.80"},{"key":"e_1_3_2_2_18_1","volume-title":"Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis","author":"Mitzenmacher Michael","unstructured":"Michael Mitzenmacher and Eli Upfal . 2017. Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis . Cambridge university press . Michael Mitzenmacher and Eli Upfal. 2017. Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis. Cambridge university press."},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213565"},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3180143"},{"key":"e_1_3_2_2_21_1","volume-title":"Proc. 17th International Conference on Database Theory (ICDT)","author":"Veldhuizen Todd L.","year":"2014","unstructured":"Todd L. Veldhuizen . 2014 . Triejoin: A Simple, Worst-Case Optimal Join Algorithm . In Proc. 17th International Conference on Database Theory (ICDT) , Athens, Greece, March 24--28 , 2014, Nicole Schweikardt, Vassilis Christophides, and Vincent Leroy (Eds.). OpenProceedings.org, 96--106. https:\/\/doi.org\/10.5441\/002\/icdt.2014.13 10.5441\/002 Todd L. Veldhuizen. 2014. Triejoin: A Simple, Worst-Case Optimal Join Algorithm. In Proc. 17th International Conference on Database Theory (ICDT), Athens, Greece, March 24--28, 2014, Nicole Schweikardt, Vassilis Christophides, and Vincent Leroy (Eds.). OpenProceedings.org, 96--106. https:\/\/doi.org\/10.5441\/002\/icdt.2014.13"},{"key":"e_1_3_2_2_22_1","volume-title":"Proceedings of the International Congress of Mathematicians: Rio de Janeiro","author":"Williams Virginia Vassilevska","year":"2018","unstructured":"Virginia Vassilevska Williams . 2018 . On some fine-grained questions in algorithms and complexity . In Proceedings of the International Congress of Mathematicians: Rio de Janeiro 2018. World Scientific, 3447--3487. Virginia Vassilevska Williams. 2018. On some fine-grained questions in algorithms and complexity. In Proceedings of the International Congress of Mathematicians: Rio de Janeiro 2018. World Scientific, 3447--3487."},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/09076619X"},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186893"},{"key":"e_1_3_2_2_25_1","volume-title":"Triangle Listing and APSP. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS, Sandy Irani (Ed.). IEEE, 786--797","author":"Williams Virginia Vassilevska","year":"2020","unstructured":"Virginia Vassilevska Williams and Yinzhan Xu . 2020 . Monochromatic Triangles , Triangle Listing and APSP. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS, Sandy Irani (Ed.). IEEE, 786--797 . https:\/\/doi.org\/10.1109\/FOCS46700.2020.00078 10.1109\/FOCS46700.2020.00078 Virginia Vassilevska Williams and Yinzhan Xu. 2020. Monochromatic Triangles, Triangle Listing and APSP. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS, Sandy Irani (Ed.). IEEE, 786--797. https:\/\/doi.org\/10.1109\/FOCS46700.2020.00078"}],"event":{"name":"SIGMOD\/PODS '22: International Conference on Management of Data","location":"Philadelphia PA USA","acronym":"SIGMOD\/PODS '22","sponsor":["SIGMOD ACM Special Interest Group on Management of Data"]},"container-title":["Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3517804.3526234","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3517804.3526234","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:49:05Z","timestamp":1750182545000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3517804.3526234"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,12]]},"references-count":22,"alternative-id":["10.1145\/3517804.3526234","10.1145\/3517804"],"URL":"https:\/\/doi.org\/10.1145\/3517804.3526234","relation":{},"subject":[],"published":{"date-parts":[[2022,6,12]]},"assertion":[{"value":"2022-06-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}