Variants of Kannan's Theorem are given where the circuits of the original theorem are replaced by arbitrary recursively presentable classes of languages that use advice strings and satisfy certain mild conditions. These variants imply that $\DTIME(n^{k'})^{\NE}/n^k$ does not contain $\PTIME^{\NE}$, $\DTIME(2^{n^{k'}})/n^k$ does not contain $\EXP$, $\SPACE(n^{k'})/n^k$ does not contain $\PSPACE$, ... more >>>

The use of Nepomnjascij's Theorem in the proofs of independence results for bounded arithmetic theories is investigated. Using this result and similar ideas, the following statements are proven: (1) At least one of S_1 or TLS does not prove the Matiyasevich-Davis-Robinson-Putnam Theorem and (2) TLS does not prove Sigma^b_{1,1}=Pi^b_{1,1}. Here ... more >>>

We prove upper and lower bounds on the power of quantum and stochastic branching programs of bounded width. We show any NC^1 language can be accepted exactly by a width-2 quantum branching program of polynomial length, in contrast to the classical case where width 5 is necessary unless \NC^1=\ACC. This ... more >>>

We prove upper and lower bounds on the power of quantum and stochastic branching programs of bounded width. We show any NC^1 language can be accepted exactly by a width-2 quantum branching program of polynomial length, in contrast to the classical case where width 5 is necessary unless \NC^1=\ACC. This ... more >>>