Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > NON-MULTILINEAR CIRCUITS:
Reports tagged with Non-multilinear circuits:
TR13-028 | 14th February 2013
Mrinal Kumar, Gaurav Maheshwari, Jayalal Sarma

Arithmetic Circuit Lower Bounds via MaxRank

We introduce the polynomial coefficient matrix and identify maximum rank of this matrix under variable substitution as a complexity measure for multivariate polynomials. We use our techniques to prove
super-polynomial lower bounds against several classes of non-multilinear arithmetic circuits. In particular, we obtain the following results :

$\bullet$ As ... more >>>




ISSN 1433-8092 | Imprint