The fine-grained complexity of multi-dimensional ordering properties

DOI10.4230/LIPICS.IPEC.2021.3MaRDI QIDQ6152159zbMATH OpenFDO

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

Publication date 12 February 2024

Full work available at URL https://doi.org/10.4230/LIPICS.IPEC.2021.3

zbMATH Keywords

fine-grained complexityfirst-order logicorthogonal vectors

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parameterized complexity, tractability and kernelization (68Q27) Algorithms in computer science (68Wxx)

Recommendations

• The fine-grained complexity of multi-dimensional ordering properties
• A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties
• Quantum complexity for vector domination problem
• The complexity of the partial order dimension problem: closing the gap
• K-Dominance in Multidimensional Data: Theory and Applications

Cited in

(1)

• The role of regularity in (hyper-)clique detection and implications for optimizing Boolean CSPs

This page was built for publication: The fine-grained complexity of multi-dimensional ordering properties

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6152159)