Document Open Access Logo

The Fine-Grained Complexity of Multi-Dimensional Ordering Properties

Authors Haozhe An, Mohit Gurumukhani, Russell Impagliazzo, Michael Jaber, Marvin Künnemann, Maria Paula Parga Nina

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2021.3.pdf
  • Filesize: 0.72 MB
  • 15 pages

Document Identifiers

Author Details

Haozhe An
  • University of Maryland, College Park, MD, USA
Mohit Gurumukhani
  • University of California at San Diego, CA, USA
Russell Impagliazzo
  • University of California at San Diego, CA, USA
Michael Jaber
  • University of California at San Diego, CA, USA
Marvin Künnemann
  • Institute for Theoretical Studies, ETH Zürich, Switzerland
Maria Paula Parga Nina
  • University of California at San Diego, CA, USA

Funding

  • Impagliazzo, Russell: Work supported by the Simons Foundation and NSF grant CCF-1909634.
  • Künnemann, Marvin: Research supported by Dr. Max Rössler, by the Walter Haefner Foundation, and by the ETH Zürich Foundation. Part of this research was performed while the author was employed at MPI Informatics.

Acknowledgements

We would like to thank Rex Lei, Jiawei Gao, and Victor Vianu for helpful comments and discussion.

Cite As Get BibTex

Haozhe An, Mohit Gurumukhani, Russell Impagliazzo, Michael Jaber, Marvin Künnemann, and Maria Paula Parga Nina. The Fine-Grained Complexity of Multi-Dimensional Ordering Properties. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 3:1-3:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.IPEC.2021.3

Abstract

We define a class of problems whose input is an n-sized set of d-dimensional vectors, and where the problem is first-order definable using comparisons between coordinates. This class captures a wide variety of tasks, such as complex types of orthogonal range search, model-checking first-order properties on geometric intersection graphs, and elementary questions on multidimensional data like verifying Pareto optimality of a choice of data points.
Focusing on constant dimension d, we show that any k-quantifier, d-dimensional such problem is solvable in O(n^{k-1} log^{d-1} n) time. Furthermore, this algorithm is conditionally tight up to subpolynomial factors: we show that assuming the 3-uniform hyperclique hypothesis, there is a k-quantifier, (3k-3)-dimensional problem in this class that requires time Ω(n^{k-1-o(1)}).
Towards identifying a single representative problem for this class, we study the existence of complete problems for the 3-quantifier setting (since 2-quantifier problems can already be solved in near-linear time O(nlog^{d-1} n), and k-quantifier problems with k > 3 reduce to the 3-quantifier case). We define a problem Vector Concatenated Non-Domination VCND_d (Given three sets of vectors X,Y and Z of dimension d,d and 2d, respectively, is there an x ∈ X and a y ∈ Y so that their concatenation x∘y is not dominated by any z ∈ Z, where vector u is dominated by vector v if u_i ≤ v_i for each coordinate 1 ≤ i ≤ d), and determine it as the "unique" candidate to be complete for this class (under fine-grained assumptions).

Subject Classification

ACM Subject Classification
  • Theory of computation → Complexity theory and logic
  • Theory of computation → Problems, reductions and completeness
  • Theory of computation → Verification by model checking
Keywords
  • Fine-grained complexity
  • First-order logic
  • Orthogonal vectors

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. Tight hardness results for LCS and other sequence similarity measures. In Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on, pages 59-78. IEEE, 2015. Google Scholar
  2. Amir Abboud, Karl Bringmann, Holger Dell, and Jesper Nederlof. More consequences of falsifying SETH and the orthogonal vectors conjecture. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 253-266. ACM, 2018. Google Scholar
  3. Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, apsp and diameter. In Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms, pages 1681-1697. SIAM, 2014. Google Scholar
  4. Amir Abboud, Ryan Williams, and Huacheng Yu. More applications of the polynomial method to algorithm design. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 218-230. SIAM, 2015. Google Scholar
  5. Amir Abboud, Virginia Vassilevska Williams, and Joshua R. Wang. Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs. In Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 377-391. SIAM, 2016. URL: https://doi.org/10.1137/1.9781611974331.ch28.
  6. Amir Abboud, Virginia Vassilevska Williams, and Oren Weimann. Consequences of faster alignment of sequences. In International Colloquium on Automata, Languages, and Programming, pages 39-51. Springer, 2014. Google Scholar
  7. Serge Abiteboul, Richard Hull, and Victor Vianu. Foundations of databases: the logical level. Addison-Wesley Longman Publishing Co., Inc., 1995. Google Scholar
  8. Pankaj K. Agarwal. Range searching. In Jacob E. Goodman, Joseph O'Rourke, and Csaba D. Tóth, editors, Handbook of Discrete and Computational Geometry, chapter 40. CRC Press LLC, 3rd edition, 2017. Google Scholar
  9. Udit Agarwal and Vijaya Ramachandran. Fine-grained complexity for sparse graphs. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pages 239-252, 2018. Google Scholar
  10. Noga Alon, Raphael Yuster, and Uri Zwick. Finding and counting given length cycles. Algorithmica, 17(3):209-223, 1997. URL: https://doi.org/10.1007/BF02523189.
  11. Stephen Alstrup, Gerth Stølting Brodal, and Theis Rauhe. New data structures for orthogonal range searching. In 41st Annual Symposium on Foundations of Computer Science, FOCS 2000, 12-14 November 2000, Redondo Beach, California, USA, pages 198-207. IEEE Computer Society, 2000. URL: https://doi.org/10.1109/SFCS.2000.892088.
  12. Arturs Backurs and Piotr Indyk. Edit distance cannot be computed in strongly subquadratic time (unless SETH is false). In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pages 51-58. ACM, 2015. Google Scholar
  13. Arturs Backurs, Liam Roditty, Gilad Segal, Virginia Vassilevska Williams, and Nicole Wein. Towards tight approximation bounds for graph diameter and eccentricities. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 267-280. ACM, 2018. Google Scholar
  14. Karl Bringmann. Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless seth fails. In Foundations of Computer Science (FOCS), 2014 IEEE 55th Annual Symposium on, pages 661-670. IEEE, 2014. Google Scholar
  15. Karl Bringmann, Nick Fischer, and Marvin Künnemann. A fine-grained analogue of schaefer’s theorem in P: dichotomy of exists^k-forall-quantified first-order graph properties. In Amir Shpilka, editor, 34th Computational Complexity Conference, CCC 2019, July 18-20, 2019, New Brunswick, NJ, USA, volume 137 of LIPIcs, pages 31:1-31:27. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.CCC.2019.31.
  16. Karl Bringmann and Marvin Künnemann. Quadratic conditional lower bounds for string problems and dynamic time warping. In Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on, pages 79-97. IEEE, 2015. Google Scholar
  17. Marco L. Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mihajlin, Ramamohan Paturi, and Stefan Schneider. Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility. In Madhu Sudan, editor, Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, Cambridge, MA, USA, January 14-16, 2016, pages 261-270. ACM, 2016. URL: https://doi.org/10.1145/2840728.2840746.
  18. Timothy M. Chan. Orthogonal range searching in moderate dimensions: k-d trees and range trees strike back. Discret. Comput. Geom., 61(4):899-922, 2019. Google Scholar
  19. Timothy M. Chan, Kasper Green Larsen, and Mihai Patrascu. Orthogonal range searching on the ram, revisited. In Ferran Hurtado and Marc J. van Kreveld, editors, Proceedings of the 27th ACM Symposium on Computational Geometry, Paris, France, June 13-15, 2011, pages 1-10. ACM, 2011. URL: https://doi.org/10.1145/1998196.1998198.
  20. Timothy M. Chan and Dimitrios Skrepetos. All-pairs shortest paths in geometric intersection graphs. JoCG, 10(1):27-41, 2019. URL: https://doi.org/10.20382/jocg.v10i1a2.
  21. Timothy M Chan and Ryan Williams. Deterministic APSP, Orthogonal Vectors, and More: Quickly derandomizing Razborov-Smolensky. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1246-1255. SIAM, 2016. Google Scholar
  22. Bernard Chazelle. A functional approach to data structures and its use in multidimensional searching. SIAM J. Comput., 17(3):427-462, 1988. URL: https://doi.org/10.1137/0217026.
  23. Lijie Chen and Ryan Williams. An equivalence class for orthogonal vectors. In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 21-40. SIAM, 2019. URL: https://doi.org/10.1137/1.9781611975482.2.
  24. Mark de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak, Dániel Marx, and Tom C. van der Zanden. A framework for eth-tight algorithms and lower bounds in geometric intersection graphs. In Ilias Diakonikolas, David Kempe, and Monika Henzinger, editors, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 574-586. ACM, 2018. URL: https://doi.org/10.1145/3188745.3188854.
  25. Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Cheong Schwarzkopf. Orthogonal Range Searching, pages 95-120. Springer Berlin Heidelberg, Berlin, Heidelberg, 2000. URL: https://doi.org/10.1007/978-3-662-04245-8_5.
  26. Anka Gajentaan and Mark H Overmars. On a class of o(n²) problems in computational geometry. Computational geometry, 5(3):165-185, 1995. Google Scholar
  27. Jiawei Gao. On the fine-grained complexity of least weight subsequence in multitrees and bounded treewidth dags. In Bart M. P. Jansen and Jan Arne Telle, editors, 14th International Symposium on Parameterized and Exact Computation, IPEC 2019, September 11-13, 2019, Munich, Germany, volume 148 of LIPIcs, pages 16:1-16:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.IPEC.2019.16.
  28. Jiawei Gao and Russell Impagliazzo. The fine-grained complexity of strengthenings of first-order logic. Electronic Colloquium on Computational Complexity (ECCC), 26:9, 2019. URL: https://eccc.weizmann.ac.il/report/2019/009.
  29. Jiawei Gao, Russell Impagliazzo, Antonina Kolokolova, and Ryan Williams. Completeness for first-order properties on sparse structures with algorithmic applications. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '17, pages 2162-2181, 2017. Google Scholar
  30. Neil Immerman. Descriptive complexity. Graduate texts in computer science. Springer, 1999. URL: https://doi.org/10.1007/978-1-4612-0539-5.
  31. Russell Impagliazzo, Shachar Lovett, Ramamohan Paturi, and Stefan Schneider. 0-1 integer linear programming with a linear number of constraints. CoRR, abs/1401.5512, 2014. URL: http://arxiv.org/abs/1401.5512.
  32. Russell Impagliazzo, Ramamohan Paturi, and Stefan Schneider. A satisfiability algorithm for sparse depth-2 threshold circuits. CoRR, abs/1212.4548, 2012. URL: http://arxiv.org/abs/1212.4548.
  33. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? In Foundations of Computer Science, 1998. Proceedings. 39th Annual Symposium on, pages 653-662. IEEE, 1998. Google Scholar
  34. Marvin Künnemann and Dániel Marx. Finding small satisfying assignments faster than brute force: A fine-grained perspective into boolean constraint satisfaction. In Proc. 35th Computational Complexity Conference (CCC 2020), 2020. To appear. Google Scholar
  35. Marvin Künnemann, Ramamohan Paturi, and Stefan Schneider. On the Fine-Grained Complexity of One-Dimensional Dynamic Programming. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), volume 80 of Leibniz International Proceedings in Informatics (LIPIcs), pages 21:1-21:15, 2017. Google Scholar
  36. Andrea Lincoln, Virginia Vassilevska Williams, and Ryan Williams. Tight hardness for shortest cycles and paths in sparse graphs. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1236-1252. Society for Industrial and Applied Mathematics, 2018. Google Scholar
  37. George S. Lueker. A data structure for orthogonal range queries. In 19th Annual Symposium on Foundations of Computer Science, Ann Arbor, Michigan, USA, 16-18 October 1978, pages 28-34. IEEE Computer Society, 1978. URL: https://doi.org/10.1109/SFCS.1978.1.
  38. Dániel Marx and Anastasios Sidiropoulos. The limited blessing of low dimensionality: when 1-1/d is the best possible exponent for d-dimensional geometric problems. In Siu-Wing Cheng and Olivier Devillers, editors, 30th Annual Symposium on Computational Geometry, SOCG'14, Kyoto, Japan, June 08 - 11, 2014, page 67. ACM, 2014. URL: https://doi.org/10.1145/2582112.2582124.
  39. Daniel Moeller, Ramamohan Paturi, and Stefan Schneider. Subquadratic algorithms for succinct stable matching. In International Computer Science Symposium in Russia, pages 294-308. Springer, 2016. Google Scholar
  40. Yakov Nekrich. Orthogonal range searching in linear and almost-linear space. Comput. Geom., 42(4):342-351, 2009. URL: https://doi.org/10.1016/j.comgeo.2008.09.001.
  41. Mihai Patrascu and Ryan Williams. On the possibility of faster SAT algorithms. In SODA, volume 10, pages 1065-1075. SIAM, 2010. Google Scholar
  42. D.E. Willard. Predicate-oriented Database Search Algorithms. Center for Research in Computing Technology: Center for Research in Computing Technology. Garland Pub., 1979. URL: https://books.google.de/books?id=iLQmAAAAMAAJ.
  43. Ryan Williams. Faster decision of first-order graph properties. In Proceedings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), page 80. ACM, 2014. Google Scholar
  44. Virginia Vassilevska Williams and Ryan Williams. Subcubic equivalences between path, matrix and triangle problems. In Foundations of Computer Science (FOCS), 2010 51st Annual IEEE Symposium on, pages 645-654. IEEE, 2010. Google Scholar
  45. Virginia Vassilevska Williams and Ryan Williams. Finding, minimizing, and counting weighted subgraphs. SIAM J. Comput., 42(3):831-854, 2013. URL: https://doi.org/10.1137/09076619X.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact