Short Proofs for the Determinant Identities

DOI10.1137/130917788OpenAlexW2034804004WikidataQ113779160 ScholiaQ113779160MaRDI QIDQ5252690

Iddo Tzameret, Pavel Hrubeš

Publication date: 2 June 2015

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1112.6265

zbMATH Keywords

determinantproof complexityarithmetic circuitsfeasible mathematicsfrege proofs

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Complexity of computation (including implicit computational complexity) (03D15) Classical propositional logic (03B05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)

Related Items (6)

Short proofs of the Kneser-Lovász coloring principle ⋮ Propositional Proofs in Frege and Extended Frege Systems (Abstract) ⋮ Characterizing Propositional Proofs as Noncommutative Formulas ⋮ Unnamed Item ⋮ Witnessing matrix identities and proof complexity ⋮ Quasipolynomial size proofs of the propositional pigeonhole principle

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Matrix identities and the pigeonhole principle
• On computing the determinant in small parallel time using a small number of processors
• The proof complexity of linear algebra
• Dual weak pigeonhole principle, Boolean complexity, and derandomization
• Balancing syntactically multilinear arithmetic circuits
• Fast Parallel Computation of Polynomials Using Few Processors
• Arithmetic Circuits: A survey of recent results and open questions
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• On the Parallel Evaluation of Multivariate Polynomials
• The Parallel Evaluation of General Arithmetic Expressions
• Computer Science Logic
• The Complexity of Propositional Proofs

This page was built for publication: Short Proofs for the Determinant Identities