Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR23-001 | 5th January 2023 13:01

New Lower Bounds against Homogeneous Non-Commutative Circuits

RSS-Feed




TR23-001
Authors: Prerona Chatterjee, Pavel Hrubes
Publication: 5th January 2023 14:43
Downloads: 455
Keywords: 


Abstract:

We give several new lower bounds on size of homogeneous non-commutative circuits. We present an explicit homogeneous bivariate polynomial of degree $d$ which requires homogeneous non-commutative circuit of size $\Omega(d/\log d)$. For an $n$-variate polynomial with $n>1$, the result can be improved to $\Omega(nd)$, if $d\leq n$, or $\Omega(nd \frac{\log n}{\log d})$, if $d\geq n$.
Under the same assumptions, we also give a quadratic lower bound for the ordered version of the central symmetric polynomial.



ISSN 1433-8092 | Imprint