Abstract
We define a class of problems whose input is an nsized set of ddimensional vectors, and where the problem is firstorder definable using comparisons between coordinates. This class captures a wide variety of tasks, such as complex types of orthogonal range search, modelchecking firstorder 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 kquantifier, ddimensional such problem is solvable in O(n^{k1} log^{d1} n) time. Furthermore, this algorithm is conditionally tight up to subpolynomial factors: we show that assuming the 3uniform hyperclique hypothesis, there is a kquantifier, (3k3)dimensional problem in this class that requires time Ω(n^{k1o(1)}).
Towards identifying a single representative problem for this class, we study the existence of complete problems for the 3quantifier setting (since 2quantifier problems can already be solved in nearlinear time O(nlog^{d1} n), and kquantifier problems with k > 3 reduce to the 3quantifier case). We define a problem Vector Concatenated NonDomination 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 finegrained assumptions).
BibTeX  Entry
@InProceedings{an_et_al:LIPIcs.IPEC.2021.3,
author = {An, Haozhe and Gurumukhani, Mohit and Impagliazzo, Russell and Jaber, Michael and K\"{u}nnemann, Marvin and Nina, Maria Paula Parga},
title = {{The FineGrained Complexity of MultiDimensional Ordering Properties}},
booktitle = {16th International Symposium on Parameterized and Exact Computation (IPEC 2021)},
pages = {3:13:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772167},
ISSN = {18688969},
year = {2021},
volume = {214},
editor = {Golovach, Petr A. and Zehavi, Meirav},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/15386},
URN = {urn:nbn:de:0030drops153869},
doi = {10.4230/LIPIcs.IPEC.2021.3},
annote = {Keywords: Finegrained complexity, Firstorder logic, Orthogonal vectors}
}
Keywords: 

Finegrained complexity, Firstorder logic, Orthogonal vectors 
Collection: 

16th International Symposium on Parameterized and Exact Computation (IPEC 2021) 
Issue Date: 

2021 
Date of publication: 

22.11.2021 