Matrix identities and the pigeonhole principle

DOI10.1007/S00153-003-0205-ZzbMATH Open1057.03049OpenAlexW1977405062MaRDI QIDQ701728FDOQ701728

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

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

zbMATH Keywords

matrix identitiesFrege proofspigeonhole principle

Mathematics Subject Classification ID

Complexity of proofs (03F20)

Cited In (6)

• Short Proofs for the Determinant Identities
• Title not available (Why is that?)
• A Logical Autobiography
• Ballot matrix as Catalan matrix power and related identities
• The proof complexity of linear algebra
• LA, permutations, and the Hajós calculus

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)