scientific article; zbMATH DE number 7029303
From MaRDI portal
Publication:4625692
zbMath1451.03023arXiv1802.09377MaRDI QIDQ4625692
Wied Pakusa, Benedikt Pago, Martin Grohe, Erich Grädel
Publication date: 25 February 2019
Full work available at URL: https://arxiv.org/abs/1802.09377
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Model theory of finite structures (03C13) Complexity of proofs (03F20) Descriptive complexity and finite models (68Q19)
Related Items (2)
Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem ⋮ Unnamed Item
Cites Work
- Finite model theory and its applications.
- Elements of finite model theory.
- The expressive power of stratified logic programs
- Affine systems of equations and counting infinitary logic
- An optimal lower bound on the number of variables for graph identification
- Hierarchies in transitive closure logic, stratified Datalog and infinitary logic
- Lower bounds for the polynomial calculus and the Gröbner basis algorithm
- Sherali-Adams relaxations of graph isomorphism polytopes
- On symmetric circuits and fixed-point logics
- A combinatorial characterization of resolution width
- Sherali-Adams relaxations and indistinguishability in counting logics
- Constraint Satisfaction Problems Solvable by Local Consistency Methods
- Limitations of Algebraic Approaches to Graph Isomorphism Testing
- PEBBLE GAMES AND LINEAR EQUATIONS
- Expander graphs and their applications
- The relative efficiency of propositional proof systems
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Linear Diophantine Equations, Group CSPs, and Graph Isomorphism
- Proof Complexity Meets Algebra
- Counting in Team Semantics
- On the Resolution Complexity of Graph Non-isomorphism
- A Definability Dichotomy for Finite Valued CSPs
- Rank logic is dead, long live rank logic!
- The Complexity of Propositional Proofs
- On sufficient conditions for unsatisfiability of random formulas
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication:
