Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with lower bound for circuit size:
TR14-139 | 31st October 2014
Hong Van Le

Lower bounds for the circuit size of partially homogeneous polynomials

Revisions: 1

In this paper
we associate to each multivariate polynomial $f$ that is homogeneous relative to a subset of its variables a series of polynomial families $P_\lambda (f)$ of $m$-tuples of homogeneous polynomials of equal degree such that the circuit size of any member in $P_\lambda (f)$ is bounded from above ... 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