All reports by Author Chris Pollett:

__
TR04-014
| 26th November 2003
__

Chris Pollett#### Languages to diagonalize against advice classes

__
TR02-051
| 16th July 2002
__

Chris Pollett#### Nepomnjascij's Theorem and Independence Proofs in Bounded Arithmetic

__
TR02-013
| 30th January 2002
__

Chris Pollett, Farid Ablayev, Cristopher Moore, Chris Pollett#### Quantum and Stochastic Programs of Bounded Width

Revisions: 1

__
TR02-013
| 30th January 2002
__

Chris Pollett, Farid Ablayev, Cristopher Moore, Chris Pollett#### Quantum and Stochastic Programs of Bounded Width

Revisions: 1

Chris Pollett

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

Chris Pollett

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

Chris Pollett, Farid Ablayev, Cristopher Moore, Chris Pollett

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

Chris Pollett, Farid Ablayev, Cristopher Moore, Chris Pollett

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