A finite-model-theoretic view on propositional proof complexity
From MaRDI portal
Recommendations
Cites work
- A combinatorial characterization of resolution width
- A definability dichotomy for finite valued CSPs
- Affine systems of equations and counting infinitary logic
- An optimal lower bound on the number of variables for graph identification
- Constraint Satisfaction Problems Solvable by Local Consistency Methods
- Counting in team semantics
- Definability of semidefinite programming and Lasserre lower bounds for CSPs
- Descriptive complexity of linear equation systems and applications to propositional proof complexity
- Elements of finite model theory.
- Expander graphs and their applications
- Finite model theory and its applications.
- Hierarchies in transitive closure logic, stratified Datalog and infinitary logic
- scientific article; zbMATH DE number 4035805 (Why is no real title available?)
- scientific article; zbMATH DE number 1254648 (Why is no real title available?)
- scientific article; zbMATH DE number 1256733 (Why is no real title available?)
- scientific article; zbMATH DE number 1324669 (Why is no real title available?)
- scientific article; zbMATH DE number 1860652 (Why is no real title available?)
- scientific article; zbMATH DE number 7204319 (Why is no real title available?)
- Limitations of algebraic approaches to graph isomorphism testing
- Linear Diophantine Equations, Group CSPs, and Graph Isomorphism
- Lower bounds for the polynomial calculus and the Gröbner basis algorithm
- On sufficient conditions for unsatisfiability of random formulas
- On symmetric circuits and fixed-point logics
- On the resolution complexity of graph non-isomorphism
- PEBBLE GAMES AND LINEAR EQUATIONS
- Proof Complexity Meets Algebra
- Rank logic is dead, long live rank logic!
- Sherali-Adams relaxations and indistinguishability in counting logics
- Sherali-Adams relaxations of graph isomorphism polytopes
- The Complexity of Propositional Proofs
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- The expressive power of stratified logic programs
- The relative efficiency of propositional proof systems
Cited in
(17)- A simple combinatorial proof for the small model property of two-variable logic
- A reduction of proof complexity to computational complexity for 𝐴𝐶⁰[𝑝] Frege systems
- On the convergence of reduction-based and model-based methods in proof theory
- scientific article; zbMATH DE number 1556962 (Why is no real title available?)
- scientific article; zbMATH DE number 1765670 (Why is no real title available?)
- Connecting Complexity Classes, Weak Formal Theories, and Propositional Proof Systems (Invited Talk)
- Approximations of isomorphism and logics with linear-algebraic operators
- scientific article; zbMATH DE number 7204319 (Why is no real title available?)
- Descriptive complexity of linear equation systems and applications to propositional proof complexity
- Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem
- On the descriptive complexity of temporal constraint satisfaction problems
- Combinatorics of first order structures and propositional proof systems
- Pebble games and algebraic proof systems
- Pebble games and algebraic proof systems
- Supercritical size-width tree-like resolution trade-offs for graph isomorphism
- Symmetric proofs in the ideal proof system
- A purely model-theoretic proof of the exponential succinctness gap between CTL\(^{+}\) and CTL
This page was built for publication: A finite-model-theoretic view on propositional proof complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4625692)
