All reports by Author Cristopher Moore:

__
TR08-093
| 1st October 2008
__

Cristopher Moore, Alexander Russell#### A simple constant-probability RP reduction from NP to Parity P

__
TR04-012
| 19th December 2003
__

Paul Beame, Joseph Culberson, David Mitchell, Cristopher Moore#### The Resolution Complexity of Random Graph $k$-Colorability

__
TR02-013
| 30th January 2002
__

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

Revisions: 1

__
TR99-032
| 7th July 1999
__

Cristopher Moore#### Quantum Circuits: Fanout, Parity, and Counting

Cristopher Moore, Alexander Russell

The proof of Toda's celebrated theorem that the polynomial hierarchy is contained in $\P^\numP$ relies on the fact that, under mild technical conditions on the complexity class $\mathcal{C}$, we have $\exists \,\mathcal{C} \subset \BP \cdot \oplus \,\mathcal{C}$. More concretely, there is a randomized reduction which transforms nonempty sets and the ... more >>>

Paul Beame, Joseph Culberson, David Mitchell, Cristopher Moore

We consider the resolution proof complexity of propositional formulas which encode random instances of graph $k$-colorability. We obtain a tradeoff between the graph density and the resolution proof complexity.

For random graphs with linearly many edges we obtain linear-exponential lower bounds on the length of resolution refutations. For any $\epsilon>0$, ...
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 >>>

Cristopher Moore

We propose definitions of $\QAC^0$, the quantum analog of the

classical class $\AC^0$ of constant-depth circuits with AND and OR

gates of arbitrary fan-in, and $\QACC^0[q]$, the analog of the class

$\ACC^0[q]$ where $\Mod_q$ gates are also allowed. We show that it is

possible to make a `cat' state on ...
more >>>