Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > NONCOMMUTATIVE CIRCUITS:
Reports tagged with noncommutative circuits:
TR08-049 | 10th April 2008

#### Derandomizing the Isolation Lemma and Lower Bounds for Noncommutative Circuit Size

Revisions: 3

We give a randomized polynomial-time identity test for
noncommutative circuits of polynomial degree based on the isolation
lemma. Using this result, we show that derandomizing the isolation
lemma implies noncommutative circuit size lower bounds. More
precisely, we consider two restricted versions of the isolation
lemma and show that derandomizing each ... more >>>

TR23-001 | 5th January 2023
Prerona Chatterjee, Pavel Hrubes

#### New Lower Bounds against Homogeneous Non-Commutative Circuits

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 ... more >>>

ISSN 1433-8092 | Imprint