{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T07:26:13Z","timestamp":1758266773828,"version":"3.41.0"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2018,12,18]],"date-time":"2018-12-18T00:00:00Z","timestamp":1545091200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-1213151, CCF-1552651 (CAREER)"],"award-info":[{"award-number":["CCF-1213151, CCF-1552651 (CAREER)"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"NSERC Discovery"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2019,4,30]]},"abstract":"<jats:p>\n            Properties definable in first-order logic are algorithmically interesting for both theoretical and pragmatic reasons. Many of the most studied algorithmic problems, such as Hitting Set and Orthogonal Vectors, are first-order, and the first-order properties naturally arise as relational database queries. A relatively straightforward algorithm for evaluating a property with\n            <jats:italic>k<\/jats:italic>\n            +1 quantifiers takes time\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>m<\/jats:italic>\n            <jats:sup>\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sup>\n            ) and, assuming the Strong Exponential Time Hypothesis (SETH), some such properties require\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>m<\/jats:italic>\n            <jats:sup>\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sup>\n            \u2212\u03f5) time for any \u03f5 &gt; 0. (Here, &gt;\n            <jats:italic>m<\/jats:italic>\n            represents the size of the input structure, i.e.,\u00a0the number of tuples in all relations.)\n          <\/jats:p>\n          <jats:p>\n            We give algorithms for every first-order property that improves this upper bound to\n            <jats:italic>m<\/jats:italic>\n            <jats:sup>\n              <jats:italic>k<\/jats:italic>\n              \/2\n            <\/jats:sup>\n            <jats:sup>\n              \u0398 (\u221a log\n              <jats:italic>n<\/jats:italic>\n              )\n            <\/jats:sup>\n            , i.e., an improvement by a factor more than any poly-log, but less than the polynomial required to refute SETH. Moreover, we show that further improvement is\n            <jats:italic>equivalent<\/jats:italic>\n            to improving algorithms for sparse instances of the well-studied Orthogonal Vectors problem. Surprisingly, both results are obtained by showing completeness of the Sparse Orthogonal Vectors problem for the class of first-order properties under fine-grained reductions. To obtain improved algorithms, we apply the fast Orthogonal Vectors algorithm of References [3, 16].\n          <\/jats:p>\n          <jats:p>While fine-grained reductions (reductions that closely preserve the conjectured complexities of problems) have been used to relate the hardness of disparate specific problems both within P and beyond, this is the first such completeness result for a standard complexity class.<\/jats:p>","DOI":"10.1145\/3196275","type":"journal-article","created":{"date-parts":[[2018,12,19]],"date-time":"2018-12-19T13:07:08Z","timestamp":1545224828000},"page":"1-35","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Completeness for First-order Properties on Sparse Structures with Algorithmic Applications"],"prefix":"10.1145","volume":"15","author":[{"given":"Jiawei","family":"Gao","sequence":"first","affiliation":[{"name":"University of California, San Diego, La Jolla, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Russell","family":"Impagliazzo","sequence":"additional","affiliation":[{"name":"University of California, San Diego, La Jolla, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Antonina","family":"Kolokolova","sequence":"additional","affiliation":[{"name":"Memorial University of Newfoundland, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ryan","family":"Williams","sequence":"additional","affiliation":[{"name":"MIT, Cambridge, MA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,12,18]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Quadratic-time hardness of LCS and other sequence similarity measures. CoRR abs\/1501.07053","author":"Abboud Amir","year":"2015","unstructured":"Amir Abboud , Arturs Backurs , and Virginia Vassilevska Williams . 2015. Quadratic-time hardness of LCS and other sequence similarity measures. CoRR abs\/1501.07053 ( 2015 ). Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. 2015. Quadratic-time hardness of LCS and other sequence similarity measures. CoRR abs\/1501.07053 (2015)."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897653"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/2722129.2722146"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884463"},{"key":"e_1_2_1_5_1","volume-title":"Virginia Vassilevska Williams, and Oren Weimann","author":"Abboud Amir","year":"2014","unstructured":"Amir Abboud , Virginia Vassilevska Williams, and Oren Weimann . 2014 . Consequences of faster alignment of sequences. In Automata, Languages, and Programming. Springer , 39--51. Amir Abboud, Virginia Vassilevska Williams, and Oren Weimann. 2014. Consequences of faster alignment of sequences. In Automata, Languages, and Programming. Springer, 39--51."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1985.19"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/210332.210337"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01275486"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746612"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(90)90022-D"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2016.03.005"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.76"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.15"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2840728.2840746"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/2982445.2982455"},{"key":"e_1_2_1_16_1","volume-title":"Chan and Ryan Williams","author":"Timothy","year":"2016","unstructured":"Timothy M. Chan and Ryan Williams . 2016 . Deterministic APSP, orthogonal vectors, and more: Quickly derandomizing Razborov-Smolensky. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM , 1246--1255. Timothy M. Chan and Ryan Williams. 2016. Deterministic APSP, orthogonal vectors, and more: Quickly derandomizing Razborov-Smolensky. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 1246--1255."},{"volume-title":"Automata, Languages and Programming","author":"Charikar Moses","key":"e_1_2_1_17_1","unstructured":"Moses Charikar , Piotr Indyk , and Rina Panigrahy . 2002. New algorithms for subset query, partial match, orthogonal range searching, and related problems . In Automata, Languages and Programming . Springer , 451--462. Moses Charikar, Piotr Indyk, and Rina Panigrahy. 2002. New algorithms for subset query, partial match, orthogonal range searching, and related problems. In Automata, Languages and Programming. Springer, 451--462."},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 7th Annual Structure in Complexity Theory Conference","author":"Rodney","year":"1992","unstructured":"Rodney G. Downey and Michael R. Fellows. 1992. Fixed-parameter intractability . In Proceedings of the 7th Annual Structure in Complexity Theory Conference 1992 . IEEE, 36--49. Rodney G. Downey and Michael R. Fellows. 1992. Fixed-parameter intractability. In Proceedings of the 7th Annual Structure in Complexity Theory Conference 1992. IEEE, 36--49."},{"key":"e_1_2_1_19_1","series-title":"Texts in Theoretical Computer Science","volume-title":"Parameterized Complexity Theory","author":"Flum J\u00f6rg","unstructured":"J\u00f6rg Flum and Martin Grohe . 2006. Parameterized Complexity Theory , volume XIV of Texts in Theoretical Computer Science . J\u00f6rg Flum and Martin Grohe. 2006. Parameterized Complexity Theory, volume XIV of Texts in Theoretical Computer Science."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(02)00024-7"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/792764.793393"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/795664.796440"},{"key":"e_1_2_1_24_1","volume-title":"Johnson and Mario Szegedy","author":"David","year":"1999","unstructured":"David S. Johnson and Mario Szegedy . 1999 . What are the least tractable instances of max independent set? In Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 927--928. David S. Johnson and Mario Szegedy. 1999. What are the least tractable instances of max independent set? In Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 927--928."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-004-0182-6"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/174130.174138"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-34171-2_21"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80043-1"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02090776"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/800070.802186"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.023"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/10080703X"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2603088.2603121"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2559903"},{"key":"e_1_2_1_35_1","unstructured":"Virginia Vassilevska Williams. 2016. CS267 Lecture 1 Algorithms for Fixed Subgraph Isomorphism. http:\/\/theory.stanford.edu\/ virgi\/cs267\/lecture1.pdf.  Virginia Vassilevska Williams. 2016. CS267 Lecture 1 Algorithms for Fixed Subgraph Isomorphism. http:\/\/theory.stanford.edu\/ virgi\/cs267\/lecture1.pdf."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.67"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1982.45"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3196275","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3196275","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3196275","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:07:40Z","timestamp":1750212460000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3196275"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,12,18]]},"references-count":36,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,4,30]]}},"alternative-id":["10.1145\/3196275"],"URL":"https:\/\/doi.org\/10.1145\/3196275","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2018,12,18]]},"assertion":[{"value":"2017-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-12-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}