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 circuits, and problems in the counting hierarchy that ... more >>>

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 circuits for iterated multiplication. ... more >>>

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. We show ... more >>>