Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > HANKEL MATRIX:
Reports tagged with Hankel matrix:
TR99-026 | 7th July 1999
Miklos Ajtai

#### A Non-linear Time Lower Bound for Boolean Branching Programs

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

TR18-180 | 3rd November 2018
Nathanael Fijalkow, Guillaume Lagarde, Pierre Ohlmann, Olivier Serre

#### Lower bounds for arithmetic circuits via the Hankel matrix

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

ISSN 1433-8092 | Imprint