Completeness for first-order properties on sparse structures with algorithmic applications

DOI10.1137/1.9781611974782.141MaRDI QIDQ4575889zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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)

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)

• Counting Answers to Existential Questions
• scientific article; zbMATH DE number 7559218 (Why is no real title available?)
• 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
• scientific article; zbMATH DE number 7250154 (Why is no real title available?)
• 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

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)