All reports by Author Alexander Russell:

__
TR08-093
| 1st October 2008
__

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

__
TR02-030
| 3rd June 2002
__

Lars Engebretsen, Jonas Holmerin, Alexander Russell#### Inapproximability Results for Equations over Finite Groups

Revisions: 1

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

Lars Engebretsen, Jonas Holmerin, Alexander Russell

An equation over a finite group G is an expression of form

w_1 w_2...w_k = 1_G, where each w_i is a variable, an inverted

variable, or a constant from G; such an equation is satisfiable

if there is a setting of the variables to values in G ...
more >>>