A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties
From MaRDI portal
Publication:5091783
Recommendations
Cites work
- A new algorithm for optimal 2-constraint satisfaction and its implications
- Answering FO+MOD queries under updates on bounded degree databases
- Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
- Classifying the Complexity of Constraints Using Finite Algebras
- Closure properties of constraints
- Completeness for first-order properties on sparse structures with algorithmic applications
- Complexity classifications of Boolean constraint satisfaction problems
- Complexity of generalized satisfiability counting problems
- Conditional Lower Bounds for All-Pairs Max-Flow
- Consequences of Faster Alignment of Sequences
- Constraint satisfaction problems: complexity and algorithms
- Deterministic APSP, orthogonal vectors, and more: quickly derandomizing Razborov-Smolensky
- Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
- Enumeration complexity of conjunctive queries with functional dependencies
- Equivalences among Relational Expressions
- Fast approximation algorithms for the diameter and radius of sparse graphs
- Faster decision of first-order graph properties
- Finding and counting given length cycles
- Finding, minimizing, and counting weighted subgraphs
- scientific article; zbMATH DE number 1222098 (Why is no real title available?)
- scientific article; zbMATH DE number 839556 (Why is no real title available?)
- If the current clique algorithms are optimal, so is Valiant's parser
- Improved Approximation for Fréchet Distance on c-packed Curves Matching Conditional Lower Bounds
- Monotone monadic SNP and constraint satisfaction
- More applications of the polynomial method to algorithm design
- More consequences of falsifying SETH and the orthogonal vectors conjecture
- Multivariate fine-grained complexity of longest common subsequence
- Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility
- On Acyclic Conjunctive Queries and Constant Delay Enumeration
- On the algebraic structure of combinatorial problems
- On the complexity of k-SAT
- On the complexity of database queries
- On the complexity of H-coloring
- On the difference between closest, furthest, and orthogonal pairs: nearly-linear vs barely-subquadratic complexity
- On the possibility of faster \textsc{SAT} algorithms
- Parametrized complexity theory.
- Structure and complexity of relational queries
- Subtree isomorphism revisited
- The complexity of satisfiability problems
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Tight hardness for shortest cycles and paths in sparse graphs
- Towards tight approximation bounds for graph diameter and eccentricities
- Upper and lower bounds for first order expressibility
Cited in
(10)- The fine-grained complexity of multi-dimensional ordering properties
- Algorithms and conditional lower bounds for planning problems
- Finding small satisfying assignments faster than brute force: a fine-grained perspective into boolean constraint satisfaction
- scientific article; zbMATH DE number 7087310 (Why is no real title available?)
- Optimal polynomial-time compression for Boolean Max CSP
- The fine-grained complexity of multi-dimensional ordering properties
- Optimal polynomial-time compression for Boolean Max CSP
- Fine-grained complexity of multiple domination and dominating patterns in sparse graphs
- Faster combinatorial k-clique algorithms
- The role of regularity in (hyper-)clique detection and implications for optimizing Boolean CSPs
This page was built for publication: A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5091783)
