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

DOI10.1145/3196275zbMath1454.68054OpenAlexW4235156957WikidataQ128708728 ScholiaQ128708728MaRDI QIDQ4629991

Russell Impagliazzo, Jiawei Gao, Antonina Kolokolova, R. Ryan Williams

Publication date: 28 March 2019

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3196275

zbMATH Keywords

orthogonal vectorsfine-grained complexityfirst-order model checking

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Logic in computer science (03B70) Specification and verification (program logics, model checking, etc.) (68Q60) 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 (6)

Scheduling lower bounds via AND subset sum ⋮ Unnamed Item ⋮ Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle ⋮ Unnamed Item ⋮ Improved Merlin-Arthur protocols for central problems in fine-grained complexity ⋮ Efficiently enumerating hitting sets of hypergraphs arising in data profiling

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