Short proofs for the determinant identities

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F15%3A00443869" target="_blank" >RIV/67985840:_____/15:00443869 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1137/130917788" target="_blank" >http://dx.doi.org/10.1137/130917788</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1137/130917788" target="_blank" >10.1137/130917788</a>

Result language
angličtina
Original language name
Short proofs for the determinant identities
Original language description
We study arithmetic proof systems Pc(F) and Pf (F) operating with arithmetic circuits and arithmetic formulas, respectively, and that prove polynomial identities over a field F. We establish a series of structural theorems about these proof systems, themain one stating that Pc(F) proofs can be balanced: if a polynomial identity of syntactic degree d and depth k has a Pc(F) proof of size s, then it also has a Pc(F) proof of size poly(s, d) in which every circuit has depth O(k+log2 d+log d log s). As a corollary, we obtain a quasi-polynomial simulation of Pc(F) by Pf (F). Using these results we obtain the following: consider the identities det(XY) = det(X) det(Y ) and det(Z) = z11 znn, where X, Y , and Z are n n square matrices and Z is a triangular matrix with z11, . . . , znn on the diagonal (and det is the determinant polynomial). Then we can construct a polynomial-size arithmetic circuit det such that the above identities have Pc(F) proofs of polynomial size using circuits of O(log2
Czech name
—
Czech description
—

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BA - General mathematics
OECD FORD branch
—

Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year
2015
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)