Short proofs for the determinant identities

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Short proofs for the determinant identities

Popis výsledku v původním jazyce

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

Název v anglickém jazyce

Short proofs for the determinant identities

Popis výsledku anglicky

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

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2015

Kód důvěrnosti údajů

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

Název periodika

Siam Journal on Computing

ISSN

0097-5397

e-ISSN

—

Svazek periodika

44

Číslo periodika v rámci svazku

2

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

44

Strana od-do

340-383

Kód UT WoS článku

000353967200004

EID výsledku v databázi Scopus

2-s2.0-84928716550