Descriptive complexity of linear equation systems and applications to propositional proof complexity

MaRDI QIDQ5144627zbMATH OpenFDO

Authors Martin Grohe, Wied Pakusa

Publication date 19 January 2021

Full work available at URL http://dl.acm.org/citation.cfm?id=3330016

Mathematics Subject Classification ID

Complexity of proofs (03F20) Descriptive complexity and finite models (68Q19)

Recommendations

• On the Descriptive Complexity of Linear Algebra
• Definability of linear equation systems over groups and rings
• Definability of linear equation systems over groups and rings
• A finite-model-theoretic view on propositional proof complexity
• scientific article; zbMATH DE number 7204319

Cited in

(11)

• A descriptive complexity approach to the linear hierarchy.
• On the expressive power of linear algebra on graphs
• Descriptive complexity of deterministic polylogarithmic time and space
• Definability of linear equation systems over groups and rings
• On the Descriptive Complexity of Linear Algebra
• A finite-model-theoretic view on propositional proof complexity
• Definability of linear equation systems over groups and rings
• On the expressive power of linear algebra on graphs
• Approximations of isomorphism and logics with linear-algebraic operators
• Pebble games and algebraic proof systems
• Pebble games and algebraic proof systems

This page was built for publication: Descriptive complexity of linear equation systems and applications to propositional proof complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5144627)