Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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