Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with set-multilinear polynomials:
TR16-096 | 14th June 2016
Suryajith Chillara, Mrinal Kumar, Ramprasad Saptharishi, V Vinay

The Chasm at Depth Four, and Tensor Rank : Old results, new insights

Revisions: 2

Agrawal and Vinay [AV08] showed how any polynomial size arithmetic circuit can be thought of as a depth four arithmetic circuit of subexponential size. The resulting circuit size in this simulation was more carefully analyzed by Korian [Koiran] and subsequently by Tavenas [Tav13]. We provide a simple proof of this ... more >>>

TR22-090 | 24th June 2022
Nutan Limaye, Srikanth Srinivasan, S├ębastien Tavenas

On the Partial Derivative Method Applied to Lopsided Set-Multilinear Polynomials

We make progress on understanding a lower bound technique that was recently used by the authors to prove the first superpolynomial constant-depth circuit lower bounds against algebraic circuits.

More specifically, our previous work applied the well-known partial derivative method in a new setting, that of 'lopsided' set-multilinear polynomials. A ... more >>>

ISSN 1433-8092 | Imprint