Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with lowerbounds:
TR98-036 | 11th June 1998
Vince Grolmusz, Gábor Tardos

Lower Bounds for (MOD p -- MOD m) Circuits

Modular gates are known to be immune for the random
restriction techniques of Ajtai; Furst, Saxe, Sipser; and Yao and
Hastad. We demonstrate here a random clustering technique which
overcomes this difficulty and is capable to prove generalizations of
several known modular circuit lower bounds of Barrington, Straubing,
Therien; Krause ... more >>>

TR19-170 | 27th November 2019
Prerona Chatterjee, Mrinal Kumar, Adrian She, Ben Lee Volk

A Quadratic Lower Bound for Algebraic Branching Programs

Revisions: 3

We show that any Algebraic Branching Program (ABP) computing the polynomial $\sum_{i = 1}^n x_i^n$ has at least $\Omega(n^2)$ vertices. This improves upon the lower bound of $\Omega(n\log n)$, which follows from the classical result of Baur and Strassen [Str73, BS83], and extends the results by Kumar [Kum19], which showed ... more >>>

ISSN 1433-8092 | Imprint