The fine-grained complexity of multi-dimensional ordering properties
type: Item
instance of: scholarly article
title: The fine-grained complexity of multi-dimensional ordering properties
author: Haozhe An
author: Mohit Gurumukhani
author: Russell Impagliazzo
author: Michael Jaber
author: Marvin Künnemann
author: Maria Paula Parga Nina
published in: Algorithmica
publication date: 2022-10-27T00:00:00Z
Mathematics Subject Classification ID: 68Wxx
Mathematics Subject Classification ID: 05Cxx
zbMATH DE Number: 7608287
zbMATH Keywords: fine-grained complexity
zbMATH Keywords: first-order logic
zbMATH Keywords: orthogonal vectors
MaRDI profile type: Publication
full work available at URL: s00453-022-01014-x
OpenAlex ID: W4292608687
cites work: More consequences of falsifying SETH and the orthogonal vectors conjecture
cites work: Subcubic Equivalences Between Graph Centrality Problems, APSP and Diameter
cites work: More Applications of the Polynomial Method to Algorithm Design
cites work: Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
cites work: Consequences of Faster Alignment of Sequences
cites work: Q4864249
cites work: Fine-grained complexity for sparse graphs
cites work: Finding and counting given length cycles
cites work: Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)
cites work: Towards tight approximation bounds for graph diameter and eccentricities
cites work: A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties
cites work: Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility
cites work: Orthogonal range searching in moderate dimensions: k-d trees and range trees strike back
cites work: Orthogonal range searching on the RAM, revisited
cites work: All-pairs shortest paths in geometric intersection graphs
cites work: Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky
cites work: Multidimensional Range Selection
cites work: A Functional Approach to Data Structures and Its Use in Multidimensional Searching
cites work: An Equivalence Class for Orthogonal Vectors
cites work: A framework for ETH-tight algorithms and lower bounds in geometric intersection graphs
cites work: On a class of \(O(n^ 2)\) problems in computational geometry
cites work: Q5875548
cites work: Completeness for First-Order Properties on Sparse Structures with Algorithmic Applications
cites work: Q4227581
cites work: Space-Efficient and Fast Algorithms for Multidimensional Dominance Reporting and Counting
cites work: Finding small satisfying assignments faster than brute force: a fine-grained perspective into boolean constraint satisfaction
cites work: Q5111351
cites work: Q4607968
cites work: The limited blessing of low dimensionality
cites work: Subquadratic algorithms for succinct stable matching
cites work: Orthogonal range searching in linear and almost-linear space
cites work: Q5417690
cites work: A new algorithm for optimal 2-constraint satisfaction and its implications
cites work: Faster decision of first-order graph properties
cites work: Finding, minimizing, and counting weighted subgraphs
DOI: 10.1007/S00453-022-01014-X
Recommended article: Q4281648
Recommended article: On the complexity of partial order properties
Recommended article: On the Complexity of Some Ordering Problems
Recommended article: Q4429357
Recommended article: Q4918388
Recommended article: The order dimension of multinomial lattices
Recommended article: The complexity of random ordered structures
Recommended article: The Complexity of the Partial Order Dimension Problem: Closing the Gap
description: scientific article; zbMATH DE number 7608287