Eric Allender, Jia Jiao, Meena Mahajan, V Vinay

We investigate the phenomenon of depth-reduction in commutative

and non-commutative arithmetic circuits. We prove that in the

commutative setting, uniform semi-unbounded arithmetic circuits of

logarithmic depth are as powerful as uniform arithmetic circuits of

polynomial degree; earlier proofs did not work in the ...
more >>>

Eric Allender, Vikraman Arvind, Meena Mahajan

The aim of this paper is to use formal power series techniques to

study the structure of small arithmetic complexity classes such as

GapNC^1 and GapL. More precisely, we apply the Kleene closure of

languages and the formal power series operations of inversion and

root ...
more >>>

Mrinal Kumar

We show that over the field of complex numbers, every homogeneous polynomial of degree $d$ can be approximated (in the border complexity sense) by a depth-$3$ arithmetic circuit of top fan-in at most $d+1$. This is quite surprising since there exist homogeneous polynomials $P$ on $n$ variables of degree $2$, ... more >>>

Marco Carmosino, Russell Impagliazzo, Shachar Lovett, Ivan Mihajlin

We show that proving mildly super-linear lower bounds on non-commutative arithmetic circuits implies exponential lower bounds on non-commutative circuits. That is, non-commutative circuit complexity is a threshold phenomenon: an apparently weak lower bound actually suffices to show the strongest lower bounds we could desire.

This is part of a recent ... more >>>

Nathanael Fijalkow, Guillaume Lagarde, Pierre Ohlmann, Olivier Serre

We study the complexity of representing polynomials by arithmetic circuits in both the commutative and the non-commutative settings. Our approach goes through a precise understanding of the more restricted setting where multiplication is not associative, meaning that we distinguish $(xy)z$ from $x(yz)$.

Our first and main conceptual result is a ... more >>>