Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > PARTIAL DERIVATIVE MATRIX:
Reports tagged with Partial derivative matrix:
TR15-022 | 9th February 2015
Nutan Limaye, Guillaume Malod, Srikanth Srinivasan

#### Lower bounds for non-commutative skew circuits

Revisions: 1

Nisan (STOC 1991) exhibited a polynomial which is computable by linear sized non-commutative circuits but requires exponential sized non-commutative algebraic branching programs. Nisan's hard polynomial is in fact computable by linear sized skew circuits (skew circuits are circuits where every multiplication gate has the property that all but one of ... more >>>

TR17-124 | 6th August 2017
Mrinal Kumar, Ben Lee Volk

#### An Almost Quadratic Lower Bound for Syntactically Multilinear Arithmetic Circuits

Revisions: 2

We prove a lower bound of \$\Omega(n^2/\log^2 n)\$ on the size of any syntactically multilinear arithmetic circuit computing some explicit multilinear polynomial \$f(x_1, \ldots, x_n)\$. Our approach expands and improves upon a result of Raz, Shpilka and Yehudayoff [RSY08], who proved a lower bound of \$\Omega(n^{4/3}/\log^2 n)\$ for the same ... more >>>

ISSN 1433-8092 | Imprint