A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties
type: Item
instance of: scholarly article
author: Karl Bringmann
author: Nick Fischer
author: Marvin Künnemann
publication date: 2022-07-27T00:00:00Z
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 7564431
zbMATH Keywords: fine-grained complexity
zbMATH Keywords: hardness in P
zbMATH Keywords: hyperclique conjecture
zbMATH Keywords: constrained triangle detection
MaRDI profile type: Publication
cites work: Subtree Isomorphism Revisited
cites work: If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser
cites work: More consequences of falsifying SETH and the orthogonal vectors conjecture
cites work: Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
cites work: More Applications of the Polynomial Method to Algorithm Design
cites work: Consequences of Faster Alignment of Sequences
cites work: Q4864249
cites work: Equivalences among Relational Expressions
cites work: Finding and counting given length cycles
cites work: Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)
cites work: Towards tight approximation bounds for graph diameter and eccentricities
cites work: On Acyclic Conjunctive Queries and Constant Delay Enumeration
cites work: Q3174897
cites work: Improved Approximation for Fréchet Distance on c-packed Curves Matching Conditional Lower Bounds
cites work: Q4607967
cites work: Constraint satisfaction problems: complexity and algorithms
cites work: Classifying the Complexity of Constraints Using Finite Algebras
cites work: Q3305356
cites work: Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility
cites work: Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky
cites work: Structure and complexity of relational queries
cites work: Complexity of generalized satisfiability counting problems
cites work: Complexity classifications of Boolean constraint satisfaction problems
cites work: Q4217593
cites work: Monotone monadic SNP and constraint satisfaction
cites work: The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
cites work: Parametrized complexity theory.
cites work: Completeness for First-Order Properties on Sparse Structures with Algorithmic Applications
cites work: On the complexity of H-coloring
cites work: Upper and lower bounds for first order expressibility
cites work: On the complexity of \(k\)-SAT
cites work: On the algebraic structure of combinatorial problems
cites work: Closure properties of constraints
cites work: Conditional Lower Bounds for All-Pairs Max-Flow
cites work: Q4607968
cites work: On the complexity of database queries
cites work: Q5417690
cites work: Fast approximation algorithms for the diameter and radius of sparse graphs
cites work: The complexity of satisfiability problems
cites work: Finding, minimizing, and counting weighted subgraphs
cites work: A new algorithm for optimal 2-constraint satisfaction and its implications
cites work: Faster decision of first-order graph properties
cites work: Q4607966
full work available at URL: LIPIcs-CCC-2019-31.pdf
OpenAlex ID: W2965422163
title: A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties
DOI: 10.4230/LIPICS.CCC.2019.31
description: scientific article; zbMATH DE number 7564431