Eric Allender

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

Eric Allender, Michal Koucky, Detlef Ronneburger, Sambuddha Roy, V Vinay

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

Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, Peter Bro Miltersen

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

Ruiwen Chen, Valentine Kabanets

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

Eric Allender, Nikhil Balaji, Samir Datta

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 Therien). As a corollary, we obtain improved bounds on the complexity of certain problems involving arithmetic circuits, which are known to lie in ... more >>>