The fine-grained complexity of multi-dimensional ordering properties
From MaRDI portal
Publication:2093566
Recommendations
- scientific article; zbMATH DE number 512933
- On the complexity of partial order properties
- On the Complexity of Some Ordering Problems
- scientific article; zbMATH DE number 1985659
- scientific article; zbMATH DE number 6157241
- The order dimension of multinomial lattices
- The complexity of random ordered structures
- The complexity of the partial order dimension problem: closing the gap
Cites work
- A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties
- A framework for ETH-tight algorithms and lower bounds in geometric intersection graphs
- A Functional Approach to Data Structures and Its Use in Multidimensional Searching
- A new algorithm for optimal 2-constraint satisfaction and its implications
- All-pairs shortest paths in geometric intersection graphs
- An equivalence class for orthogonal vectors
- Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
- Completeness for first-order properties on sparse structures with algorithmic applications
- Consequences of Faster Alignment of Sequences
- Deterministic APSP, orthogonal vectors, and more: quickly derandomizing Razborov-Smolensky
- Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
- Faster decision of first-order graph properties
- Finding and counting given length cycles
- Finding small satisfying assignments faster than brute force: a fine-grained perspective into boolean constraint satisfaction
- Finding, minimizing, and counting weighted subgraphs
- Fine-grained complexity for sparse graphs
- scientific article; zbMATH DE number 1254648 (Why is no real title available?)
- scientific article; zbMATH DE number 839556 (Why is no real title available?)
- scientific article; zbMATH DE number 7204473 (Why is no real title available?)
- scientific article; zbMATH DE number 7650224 (Why is no real title available?)
- More applications of the polynomial method to algorithm design
- More consequences of falsifying SETH and the orthogonal vectors conjecture
- Multidimensional range selection
- Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility
- On a class of \(O(n^ 2)\) problems in computational geometry
- On the possibility of faster \textsc{SAT} algorithms
- Orthogonal range searching in linear and almost-linear space
- Orthogonal range searching in moderate dimensions: k-d trees and range trees strike back
- Orthogonal range searching on the RAM, revisited
- Space-Efficient and Fast Algorithms for Multidimensional Dominance Reporting and Counting
- Subcubic equivalences between graph centrality problems, APSP and diameter
- The limited blessing of low dimensionality: when \(1-1/d\) is the best possible exponent for \(d\)-dimensional geometric problems (extended abstract)
- Tight hardness for shortest cycles and paths in sparse graphs
- Towards tight approximation bounds for graph diameter and eccentricities
Cited in
(4)
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 Q2093566)
