Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > COUNTING HIERARCHY:
Reports tagged with Counting Hierarchy:
TR96-023 | 21st March 1996
Eric Allender

#### A Note on Uniform Circuit Lower Bounds for the Counting Hierarchy

A very recent paper by Caussinus, McKenzie, Therien, and Vollmer
[CMTV] shows that ACC^0 is properly contained in ModPH, and TC^0
is properly contained in the counting hierarchy. Thus, [CMTV] shows
that there are problems in ModPH that require superpolynomial-size
uniform ACC^0 ... more >>>

TR01-041 | 23rd May 2001
Eric Allender, Michal Koucky, Detlef Ronneburger, Sambuddha Roy, V Vinay

#### Time-Space Tradeoffs in the Counting Hierarchy

We extend the lower bound techniques of [Fortnow], to the
unbounded-error probabilistic model. A key step in the argument
is a generalization of Nepomnjascii's theorem from the Boolean
setting to the arithmetic setting. This generalization is made
possible, due to the recent discovery of logspace-uniform TC^0
more >>>

TR05-037 | 8th April 2005
Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, Peter Bro Miltersen

#### On the Complexity of Numerical Analysis

We study two quite different approaches to understanding the complexity
of fundamental problems in numerical analysis. We show that both hinge
on the question of understanding the complexity of the following problem,
which we call PosSLP:
Given a division-free straight-line program
producing an integer N, decide whether N>0.
more >>>

TR12-007 | 28th January 2012
Ruiwen Chen, Valentine Kabanets

#### Lower Bounds against Weakly Uniform Circuits

Revisions: 1

A family of Boolean circuits $\{C_n\}_{n\geq 0}$ is called \emph{$\gamma(n)$-weakly uniform} if
there is a polynomial-time algorithm for deciding the direct-connection language of every $C_n$,
given \emph{advice} of size $\gamma(n)$. This is a relaxation of the usual notion of uniformity, which allows one
to interpolate between complete uniformity (when $\gamma(n)=0$) ... more >>>

TR13-177 | 10th December 2013
Eric Allender, Nikhil Balaji, Samir Datta

#### Low-depth Uniform Threshold Circuits and the Bit-Complexity of Straight Line Programs

Revisions: 1

We present improved uniform TC$^0$ circuits for division, matrix powering, and related problems, where the improvement is in terms of majority depth'' (initially studied by Maciel and Therien). As a corollary, we obtain improved bounds on the complexity of certain problems involving arithmetic circuits, which are known to lie in ... more >>>

TR22-053 | 24th April 2022
Eric Allender, Nikhil Balaji, Samir Datta, Rameshwar Pratap

#### On the Complexity of Algebraic Numbers, and the Bit-Complexity of Straight-Line Programs

We investigate the complexity of languages that correspond to algebraic real numbers, and we present improved upper bounds on the complexity of these languages. Our key technical contribution is the presentation of improved uniform TC^0 circuits
for division, matrix powering, and related problems, where the improvement is in terms of ... more >>>

ISSN 1433-8092 | Imprint