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

Eric Allender, Nikhil Balaji, Samir Datta, Rameshwar Pratap

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

Nikhil Balaji, Samir Datta

The Sum of Square Roots (SSR) problem is the following computational problem: Given positive integers $a_1, \dots, a_k$, and signs $\delta_1, \dots, \delta_k \in \{-1, 1\}$, check if $\sum_{i=1}^k \delta_i \sqrt{a_i} > 0$. The problem is known to have a polynomial time algorithm on the real RAM model of computation, ... more >>>