Comparing EQP and MOD_{p^k}P using Polynomial Degree Lower Bounds

M. de Graaf, P. Valiant

We show that an oracle A that contains either 1/4 or 3/4 of all strings of length n can be used to separate EQP from the counting classes MOD_{p^k}P. Our proof makes use of the deg…