Completeness for first-order properties on sparse structures with algorithmic applications
DOI10.1137/1.9781611974782.141zbMATH Open1407.68220OpenAlexW4244133084MaRDI QIDQ4575889FDOQ4575889
Authors: Jiawei Gao, Russell Impagliazzo, Antonina Kolokolova, Ryan Williams 
Publication date: 16 July 2018
Published in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/1.9781611974782.141
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
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Logic in computer science (03B70) General topics in the theory of algorithms (68W01)
Cited In (11)
- Title not available (Why is that?)
- The Orthogonal Vectors Conjecture for Branching Programs and Formulas
- Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems
- Faster decision of first-order graph properties
- A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties
- Completeness for first-order properties on sparse structures with algorithmic applications
- Title not available (Why is that?)
- Towards permissionless consensus in the standard model via fine-grained complexity
- Fine-grained derandomization: from problem-centric to resource-centric complexity
- The fine-grained complexity of multi-dimensional ordering properties
- Counting Answers to Existential Questions
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)
