Completeness for first-order properties on sparse structures with algorithmic applications
From MaRDI portal
Logic in computer science (03B70) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) General topics in the theory of algorithms (68W01)
Recommendations
- Completeness for first-order properties on sparse structures with algorithmic applications
- Faster decision of first-order graph properties
- Testing first-order properties for subclasses of sparse graphs
- Sparsity. Graphs, structures, and algorithms
- The Exact Complexity of the First-Order Logic Definability Problem
Cited in
(11)- The fine-grained complexity of multi-dimensional ordering properties
- Completeness for first-order properties on sparse structures with algorithmic applications
- Faster decision of first-order graph properties
- Fine-grained derandomization: from problem-centric to resource-centric complexity
- Polyline simplification has cubic complexity
- The Orthogonal Vectors Conjecture for Branching Programs and Formulas
- Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems
- Counting Answers to Existential Questions
- A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties
- scientific article; zbMATH DE number 7250154 (Why is no real title available?)
- Towards permissionless consensus in the standard model via fine-grained complexity
This page was built for publication: Completeness for first-order properties on sparse structures with algorithmic applications
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575889)
