Completeness for First-Order Properties on Sparse Structures with Algorithmic Applications

DOI10.1137/1.9781611974782.141zbMath1407.68220OpenAlexW4244133084MaRDI QIDQ4575889

Russell Impagliazzo, Jiawei Gao, Antonina Kolokolova, R. 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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Logic in computer science (03B70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) General topics in the theory of algorithms (68W01)

Related Items (8)

Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Counting Answers to Existential Questions ⋮ Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems ⋮ A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties ⋮ The Orthogonal Vectors Conjecture for Branching Programs and Formulas ⋮ The fine-grained complexity of multi-dimensional ordering properties

This page was built for publication: Completeness for First-Order Properties on Sparse Structures with Algorithmic Applications