{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:58:08Z","timestamp":1781078288735,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":81,"publisher":"ACM","license":[{"start":{"date-parts":[[2018,6,20]],"date-time":"2018-06-20T00:00:00Z","timestamp":1529452800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["639.021.438"],"award-info":[{"award-number":["639.021.438"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2018,6,20]]},"DOI":"10.1145\/3188745.3188938","type":"proceedings-article","created":{"date-parts":[[2018,6,20]],"date-time":"2018-06-20T20:15:46Z","timestamp":1529525746000},"page":"253-266","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":19,"title":["More consequences of falsifying SETH and the orthogonal vectors conjecture"],"prefix":"10.1145","author":[{"given":"Amir","family":"Abboud","sequence":"first","affiliation":[{"name":"IBM Research, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Karl","family":"Bringmann","sequence":"additional","affiliation":[{"name":"Max Planck Institute for Informatics, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Holger","family":"Dell","sequence":"additional","affiliation":[{"name":"Saarland University, Germany \/ M2CI, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jesper","family":"Nederlof","sequence":"additional","affiliation":[{"name":"Eindhoven University of Technology, Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,6,20]]},"reference":[{"key":"e_1_3_2_2_1_1","unstructured":"Amir Abboud Arturs Backurs Karl Bringmann and Marvin K\u00fcnnemann. 2017.  Amir Abboud Arturs Backurs Karl Bringmann and Marvin K\u00fcnnemann. 2017."},{"key":"e_1_3_2_2_2_1","volume-title":"58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017","author":"Analyzing Compressed Data Fine-Grained","year":"2017"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.14"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/2722129.2722241"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188938"},{"key":"e_1_3_2_2_6_1","volume-title":"Distributed PCP Theorems for Hardness of Approximation in P. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017","author":"Abboud Amir","year":"2017"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.53"},{"key":"e_1_3_2_2_8_1","volume-title":"Virginia Vassilevska Williams, and Oren Weimann","author":"Abboud Amir","year":"2014"},{"key":"e_1_3_2_2_9_1","unstructured":"Springer 39\u201351. 3- 662- 43948- 7_4  Springer 39\u201351. 3- 662- 43948- 7_4"},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746594"},{"key":"e_1_3_2_2_11_1","volume-title":"43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016","volume":"55","author":"Backurs Arturs","year":"2016"},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746612"},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.56"},{"key":"e_1_3_2_2_14_1","volume-title":"Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems","author":"Backurs Arturs","year":"2017"},{"key":"e_1_3_2_2_15_1","volume-title":"Proceedings of the 34th International Conference on Machine Learning, ICML 2017","volume":"70","author":"Backurs Arturs","year":"2017"},{"key":"e_1_3_2_2_16_1","unstructured":"Marshall Ball Alon Rosen Manuel Sabin and Prashant Nalini Vasudevan. 2017.  Marshall Ball Alon Rosen Manuel Sabin and Prashant Nalini Vasudevan. 2017."},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055466"},{"key":"e_1_3_2_2_18_1","unstructured":"Armin Biere Marijn Heule Hans van Maaren and Toby Walsh (Eds.). 2009.  Armin Biere Marijn Heule Hans van Maaren and Toby Walsh (Eds.). 2009."},{"key":"e_1_3_2_2_19_1","volume-title":"Frontiers in Artificial Intelligence and Applications","author":"Satisfiability Handbook"},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.76"},{"key":"e_1_3_2_2_21_1","unstructured":"Karl Bringmann Pawel Gawrychowski Shay Mozes and Oren Weimann. 2018.  Karl Bringmann Pawel Gawrychowski Shay Mozes and Oren Weimann. 2018."},{"key":"e_1_3_2_2_22_1","volume-title":"Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018","author":"Distance Tree Edit","year":"2018"},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.36"},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.15"},{"key":"e_1_3_2_2_25_1","unstructured":"Chris Calabro Russell Impagliazzo and Ramamohan Paturi. 2006.  Chris Calabro Russell Impagliazzo and Ramamohan Paturi. 2006."},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2006.6"},{"key":"e_1_3_2_2_27_1","volume-title":"Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016","author":"Timothy","year":"2016"},{"key":"e_1_3_2_2_28_1","unstructured":"Ruiwen Chen and Rahul Santhanam. 2015.  Ruiwen Chen and Rahul Santhanam. 2015."},{"key":"e_1_3_2_2_29_1","volume-title":"USA","author":"Improved Algorithms","year":"2015"},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2925416"},{"key":"e_1_3_2_2_31_1","unstructured":"Marek Cygan Fedor V. Fomin Lukasz Kowalik Daniel Lokshtanov D\u00e1niel Marx Marcin Pilipczuk Michal Pilipczuk and Saket Saurabh. 2015.  Marek Cygan Fedor V. Fomin Lukasz Kowalik Daniel Lokshtanov D\u00e1niel Marx Marcin Pilipczuk Michal Pilipczuk and Saket Saurabh. 2015."},{"key":"e_1_3_2_2_32_1","unstructured":"Parameterized Algorithms. Springer.  Parameterized Algorithms. Springer."},{"key":"e_1_3_2_2_33_1","unstructured":"3- 319- 21275- 3  3- 319- 21275- 3"},{"key":"e_1_3_2_2_34_1","unstructured":"Marek Cygan Stefan Kratsch and Jesper Nederlof. 2013.  Marek Cygan Stefan Kratsch and Jesper Nederlof. 2013."},{"key":"e_1_3_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488646"},{"key":"e_1_3_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.23"},{"key":"e_1_3_2_2_37_1","volume-title":"On the Hardness of Partially Dynamic Graph Problems and Connections to Diameter. 55","author":"Dahlgaard S\u00f8ren","year":"2016"},{"key":"e_1_3_2_2_38_1","volume-title":"8th International Conference, CIAC 2013, Barcelona, Spain, May 22-24, 2013. Proceedings (Lecture Notes in Computer Science), Paul G. Spirakis and Maria J. Serna (Eds.)","volume":"7878","author":"Dantsin Evgeny","year":"2013"},{"key":"e_1_3_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.05.009"},{"key":"e_1_3_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(95)00022-2"},{"key":"e_1_3_2_2_41_1","volume-title":"Faster Algorithms for Rectangular Matrix Multiplication. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012","author":"Gall Fran\u00e7ois Le","year":"2012"},{"key":"e_1_3_2_2_42_1","unstructured":"Jiawei Gao Russell Impagliazzo Antonina Kolokolova and Ryan Williams. 2017.  Jiawei Gao Russell Impagliazzo Antonina Kolokolova and Ryan Williams. 2017."},{"key":"e_1_3_2_2_43_1","volume-title":"First-Order Properties on Sparse Structures with Algorithmic Applications. In Proc. of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 2162\u20132181","author":"Completeness"},{"key":"e_1_3_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095193"},{"key":"e_1_3_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"e_1_3_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.58"},{"key":"e_1_3_2_2_47_1","unstructured":"Hamid Jahanjou Eric Miles and Emanuele Viola. 2015.  Hamid Jahanjou Eric Miles and Emanuele Viola. 2015."},{"key":"e_1_3_2_2_48_1","volume-title":"Automata, Languages, and Programming - 42nd International Colloquium, ICALP","author":"Reductions Local","year":"2015"},{"key":"e_1_3_2_2_49_1","unstructured":"Stasys Jukna. 2012.  Stasys Jukna. 2012."},{"key":"e_1_3_2_2_50_1","volume-title":"Advances and Frontiers","author":"Complexity Boolean Function"},{"key":"e_1_3_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884524"},{"key":"e_1_3_2_2_52_1","unstructured":"9781611974331.ch89  9781611974331.ch89"},{"key":"e_1_3_2_2_53_1","volume-title":"44th International Colloquium on Automata, Languages, and Programming, ICALP 2017","volume":"80","author":"Krauthgamer Robert","year":"2017"},{"key":"e_1_3_2_2_54_1","unstructured":"Marvin K\u00fcnnemann Ramamohan Paturi and Stefan Schneider. 2017.  Marvin K\u00fcnnemann Ramamohan Paturi and Stefan Schneider. 2017."},{"key":"e_1_3_2_2_55_1","volume-title":"44th International Colloquium on Automata, Languages, and Programming, ICALP 2017","volume":"80","author":"Fine-Grained On","year":"2017"},{"key":"e_1_3_2_2_56_1","unstructured":"21  21"},{"key":"e_1_3_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133097"},{"key":"e_1_3_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-34171-2_21"},{"key":"e_1_3_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32589-2_62"},{"key":"e_1_3_2_2_60_1","first-page":"415","article-title":"On the complexity of the subgraph problem","volume":"26","author":"Ne\u0161et\u0159il Jaroslav","year":"1985","journal-title":"Commentationes Mathematicae Universitatis Carolinae"},{"key":"e_1_3_2_2_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806772"},{"key":"e_1_3_2_2_62_1","unstructured":"Mihai P \u02c7 atra\u015fcu and Ryan Williams. 2010.  Mihai P \u02c7 atra\u015fcu and Ryan Williams. 2010."},{"key":"e_1_3_2_2_63_1","volume-title":"Possibility of Faster SAT Algorithms. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010","author":"On","year":"2010"},{"key":"e_1_3_2_2_64_1","unstructured":"Liam Roditty and Virginia Vassilevska Williams. 2013.  Liam Roditty and Virginia Vassilevska Williams. 2013."},{"key":"e_1_3_2_2_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488673"},{"key":"e_1_3_2_2_66_1","unstructured":"Liam Roditty and Uri Zwick. 2004.  Liam Roditty and Uri Zwick. 2004."},{"key":"e_1_3_2_2_67_1","volume-title":"ESA 2004, 12th Annual European Symposium, Bergen, Norway, September 14-17, 2004, Proceedings (Lecture Notes in Computer Science), Susanne Albers and Tomasz Radzik (Eds.)","volume":"3221","author":"Shortest Paths Problems On Dynamic"},{"key":"e_1_3_2_2_68_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.17"},{"key":"e_1_3_2_2_69_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31594-7_65"},{"key":"e_1_3_2_2_70_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(82)90113-X"},{"key":"e_1_3_2_2_71_1","volume-title":"6th Symposium, Tatranska Lomnica","volume":"53","author":"Valiant Leslie G.","year":"1977"},{"key":"e_1_3_2_2_72_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000033"},{"key":"e_1_3_2_2_73_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.023"},{"key":"e_1_3_2_2_74_1","unstructured":"Ryan Williams. 2013.  Ryan Williams. 2013."},{"key":"e_1_3_2_2_75_1","volume-title":"1218\u20131244","author":"Search Implies Superpolynomial Lower Improving Exhaustive","year":"2013"},{"key":"e_1_3_2_2_76_1","unstructured":"10080703X  10080703X"},{"key":"e_1_3_2_2_77_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591811"},{"key":"e_1_3_2_2_78_1","unstructured":"Ryan Williams. 2014.  Ryan Williams. 2014."},{"key":"e_1_3_2_2_79_1","doi-asserted-by":"publisher","DOI":"10.1145\/2559903"},{"key":"e_1_3_2_2_80_1","volume-title":"10th International Symposium on Parameterized and Exact Computation, IPEC 2015","volume":"43","author":"Williams Virginia Vassilevska","year":"2015"},{"key":"e_1_3_2_2_81_1","volume-title":"Matrix and Triangle Problems. In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010","author":"Williams Virginia Vassilevska","year":"2010"}],"event":{"name":"STOC '18: Symposium on Theory of Computing","location":"Los Angeles CA USA","acronym":"STOC '18","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3188745.3188938","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3188745.3188938","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:08:07Z","timestamp":1750208887000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3188745.3188938"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,20]]},"references-count":81,"alternative-id":["10.1145\/3188745.3188938","10.1145\/3188745"],"URL":"https:\/\/doi.org\/10.1145\/3188745.3188938","relation":{},"subject":[],"published":{"date-parts":[[2018,6,20]]},"assertion":[{"value":"2018-06-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}