Matrix identities and the pigeonhole principle

DOI10.1007/S00153-003-0205-ZMaRDI QIDQ701728zbMATH OpenOpenAlexFDO

Authors Michael Soltys, Alasdair Urquhart

Publication date 16 December 2004

Published in Archive for Mathematical Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00153-003-0205-z

zbMATH Keywords

matrix identitiesFrege proofspigeonhole principle

Mathematics Subject Classification ID

Complexity of proofs (03F20)

Recommendations

• An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
• Proving properties of matrices over \({\mathbb{Z}_{2}}\)
• Short proofs for the determinant identities
• Bounded-Depth Frege Lower Bounds for Weaker Pigeonhole Principles
• Polynomial size proofs of the propositional pigeonhole principle

Cited in

(6)

• A Logical Autobiography
• Short Proofs for the Determinant Identities
• Ballot matrix as Catalan matrix power and related identities
• LA, permutations, and the Hajós calculus
• The proof complexity of linear algebra
• scientific article; zbMATH DE number 4047879 (Why is no real title available?)

This page was built for publication: Matrix identities and the pigeonhole principle

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