2026-07-23T17:11:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15386 2024-03-06T10:55:37Z ddc:004 open_access

The Fine-Grained Complexity of Multi-Dimensional Ordering Properties An, Haozhe Gurumukhani, Mohit Impagliazzo, Russell Jaber, Michael Künnemann, Marvin Nina, Maria Paula Parga Fine-grained complexity First-order logic Orthogonal vectors 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Haozhe An and Mohit Gurumukhani and Russell Impagliazzo and Michael Jaber and Marvin Künnemann and Maria Paula Parga Nina 2021 Is Part Of LIPIcs, Volume 214, 16th International Symposium on Parameterized and Exact Computation (IPEC 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2021.3 urn:nbn:de:0030-drops-153869 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2021.3 eng https://creativecommons.org/licenses/by/4.0/legalcode