ECCC-Report TR23-001https://eccc.weizmann.ac.il/report/2023/001Comments and Revisions published for TR23-001en-usThu, 05 Jan 2023 14:43:37 +0200
Paper TR23-001
| New Lower Bounds against Homogeneous Non-Commutative Circuits |
Prerona Chatterjee,
Pavel Hrubes
https://eccc.weizmann.ac.il/report/2023/001We 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. Thu, 05 Jan 2023 14:43:37 +0200https://eccc.weizmann.ac.il/report/2023/001