Miklos Ajtai

We prove that for all positive integer $k$ and for all

sufficiently small $\epsilon >0$ if $n$ is sufficiently large

then there is no Boolean (or $2$-way) branching program of size

less than $2^{\epsilon n}$ which for all inputs

$X\subseteq \lbrace 0,1,...,n-1\rbrace $ computes in time $kn$

the parity of ...
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 >>>