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

DOI10.1137/1.9781611974782.141zbMATH Open1407.68220OpenAlexW4244133084MaRDI QIDQ4575889FDOQ4575889

Russell Impagliazzo, Jiawei Gao, Ryan Williams, Antonina Kolokolova

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

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)

Cited In (9)

• 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
• Title not available (Why is that?)
• A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties
• Title not available (Why is that?)
• Towards permissionless consensus in the standard model via fine-grained 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)