{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:20:57Z","timestamp":1750220457230,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":62,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,6,20]],"date-time":"2021-06-20T00:00:00Z","timestamp":1624147200000},"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":["725978"],"award-info":[{"award-number":["725978"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,20]]},"DOI":"10.1145\/3452021.3458814","type":"proceedings-article","created":{"date-parts":[[2021,6,18]],"date-time":"2021-06-18T14:21:58Z","timestamp":1624026118000},"page":"19-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Modern Lower Bound Techniques in Database Theory and Constraint Satisfaction"],"prefix":"10.1145","author":[{"given":"D\u00e1niel","family":"Marx","sequence":"first","affiliation":[{"name":"CISPA Helmholtz Center for Information Security, Saarbr\u00fccken, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,6,20]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.14"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1061771"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188938"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.53"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1050987"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.32"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523189"},{"volume-title":"Computational Complexity - A Modern Approach","author":"Arora Sanjeev","key":"e_1_3_2_1_8_1","unstructured":"Sanjeev Arora and Boaz Barak . 2009. Computational Complexity - A Modern Approach . Cambridge University Press . http:\/\/www.cambridge.org\/catalogue\/ catalogue.asp?isbn=9780521424264 Sanjeev Arora and Boaz Barak. 2009. Computational Complexity - A Modern Approach. Cambridge University Press. http:\/\/www.cambridge.org\/catalogue\/ catalogue.asp?isbn=9780521424264"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/110859440"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897542"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808746"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1053128"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3--540--74915--8_18"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.IPEC.2016.8"},{"key":"e_1_3_2_1_17_1","volume-title":"Why Walking the Dog Takes Time: Frechet Distance Has No Strongly Subquadratic Algorithms Unless SETH Fails. In 55th IEEE Annual Symposium on Foundations of Computer Science (FOCS 2014","author":"Bringmann Karl","year":"2014","unstructured":"Karl Bringmann . 2014 . Why Walking the Dog Takes Time: Frechet Distance Has No Strongly Subquadratic Algorithms Unless SETH Fails. In 55th IEEE Annual Symposium on Foundations of Computer Science (FOCS 2014 ), Philadelphia, PA, USA, October 18--21 , 2014. IEEE Computer Society, 661--670. https:\/\/doi.org\/10. 1109\/FOCS.2014.76 Karl Bringmann. 2014. Why Walking the Dog Takes Time: Frechet Distance Has No Strongly Subquadratic Algorithms Unless SETH Fails. In 55th IEEE Annual Symposium on Foundations of Computer Science (FOCS 2014), Philadelphia, PA, USA, October 18--21, 2014. IEEE Computer Society, 661--670. https:\/\/doi.org\/10. 1109\/FOCS.2014.76"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.77"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.15"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.79"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.37"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007391"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2001.1186"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(86)90019-1"},{"key":"e_1_3_2_1_25_1","unstructured":"Vincent Cohen-Addad \u00c9ric Colin de Verdi\u00e8re D\u00e1niel Marx and Arnaud de Mesmay. [n.d.]. Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs. To appear in Journal of the ACM.  Vincent Cohen-Addad \u00c9ric Colin de Verdi\u00e8re D\u00e1niel Marx and Arnaud de Mesmay. [n.d.]. Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs. To appear in Journal of the ACM."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/800157.805047"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch113"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2925416"},{"volume-title":"Parameterized Algorithms","author":"Cygan Marek","key":"e_1_3_2_1_29_1","unstructured":"Marek Cygan , Fedor V. Fomin , Lukasz Kowalik , Daniel Lokshtanov , D\u00e1niel Marx , Marcin Pilipczuk , Michal Pilipczuk , and Saket Saurabh . 2015. Parameterized Algorithms . Springer . Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, D\u00e1niel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. 2015. Parameterized Algorithms. Springer."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.23"},{"key":"e_1_3_2_1_31_1","volume-title":"Fellows","author":"Downey Rodney G.","year":"1999","unstructured":"Rodney G. Downey and Michael R . Fellows . 1999 . Parameterized Complexity. Springer , New York. xvi+533 pages. Rodney G. Downey and Michael R. Fellows. 1999. Parameterized Complexity. Springer, New York. xvi+533 pages."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--1--4471--5559--1"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.STACS.2018.27"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.05.009"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266766"},{"volume-title":"Parameterized Complexity Theory","author":"Flum J\u00f6rg","key":"e_1_3_2_1_36_1","unstructured":"J\u00f6rg Flum and Martin Grohe . 2006. Parameterized Complexity Theory . Springer , Berlin . xiv+493 pages. J\u00f6rg Flum and Martin Grohe. 2006. Parameterized Complexity Theory. Springer, Berlin. xiv+493 pages."},{"key":"e_1_3_2_1_37_1","volume-title":"Proc. of AAAI-90","author":"Freuder E. C.","year":"1990","unstructured":"E. C. Freuder . 1990 . Complexity of K-Tree Structured Constraint Satisfaction Problems . In Proc. of AAAI-90 . Boston, MA, 4--9. E. C. Freuder. 1990. Complexity of K-Tree Structured Constraint Satisfaction Problems. In Proc. of AAAI-90. Boston, MA, 4--9."},{"key":"e_1_3_2_1_38_1","volume-title":"Johnson","author":"Garey M. R.","year":"1979","unstructured":"M. R. Garey and David S . Johnson . 1979 . Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman . M. R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1206035.1206036"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380867"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01917434"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/120868177"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3--662--48350--3_63"},{"key":"e_1_3_2_1_46_1","volume-title":"Fine-Grained Parameterized Complexity Analysis of Graph Coloring Problems. In Proceedings of the 10th International Conference on Algorithms and Complexity (CIAC 2017)","volume":"10236","author":"Jaffke Lars","unstructured":"Lars Jaffke and Bart M. P. Jansen . 2017 . Fine-Grained Parameterized Complexity Analysis of Graph Coloring Problems. In Proceedings of the 10th International Conference on Algorithms and Complexity (CIAC 2017) (Lecture Notes in Computer Science) , Vol. 10236 . 345--356. Lars Jaffke and Bart M. P. Jansen. 2017. Fine-Grained Parameterized Complexity Analysis of Graph Coloring Problems. In Proceedings of the 10th International Conference on Algorithms and Complexity (CIAC 2017) (Lecture Notes in Computer Science), Vol. 10236. 345--356."},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--1-"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/321864.321877"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.2307\/2152702"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.80"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3170442"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2010.v006a005"},{"key":"e_1_3_2_1_53_1","first-page":"415","article-title":"On the complexity of the subgraph problem","volume":"26","author":"Poljak Svatopluk","year":"1985","unstructured":"Svatopluk Poljak . 1985 . On the complexity of the subgraph problem . Commentationes Mathematicae Universitatis Carolinae 26 , 2 (1985), 415 -- 419 . Svatopluk Poljak. 1985. On the complexity of the subgraph problem. Commentationes Mathematicae Universitatis Carolinae 26, 2 (1985), 415--419.","journal-title":"Commentationes Mathematicae Universitatis Carolinae"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/3180143"},{"volume-title":"Computational Complexity","author":"Papadimitriou C. H.","key":"e_1_3_2_1_55_1","unstructured":"C. H. Papadimitriou . 1994. Computational Complexity . Addison Wesley . C. H. Papadimitriou. 1994. Computational Complexity. Addison Wesley."},{"key":"e_1_3_2_1_56_1","volume-title":"Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA","author":"Patrascu Mihai","year":"2010","unstructured":"Mihai Patrascu and Ryan Williams . 2010 . On the Possibility of Faster SAT Algorithms . In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010). 1065--1075. Mihai Patrascu and Ryan Williams. 2010. On the Possibility of Faster SAT Algorithms. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010). 1065--1075."},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095--8956(84)"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488673"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804350"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.5441\/002"},{"key":"e_1_3_2_1_62_1","volume-title":"Proceedings of the 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)","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 . In Proceedings of the 10th International Symposium on Parameterized and Exact Computation (IPEC 2015) (LIPIcs), Vol. 43 . 17--29. Virginia Vassilevska Williams. 2015. Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis. In Proceedings of the 10th International Symposium on Parameterized and Exact Computation (IPEC 2015) (LIPIcs), Vol. 43. 17--29."},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.38"}],"event":{"name":"SIGMOD\/PODS '21: International Conference on Management of Data","sponsor":["SIGMOD ACM Special Interest Group on Management of Data"],"location":"Virtual Event China","acronym":"SIGMOD\/PODS '21"},"container-title":["Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3452021.3458814","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3452021.3458814","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:48:07Z","timestamp":1750193287000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3452021.3458814"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,20]]},"references-count":62,"alternative-id":["10.1145\/3452021.3458814","10.1145\/3452021"],"URL":"https:\/\/doi.org\/10.1145\/3452021.3458814","relation":{},"subject":[],"published":{"date-parts":[[2021,6,20]]},"assertion":[{"value":"2021-06-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}