$\mathrm{Almost}\text{-}\oplus\mathrm{P} = \mathrm{BP}\cdot\oplus\mathrm{P}$ and a Random-Oracle Proof of Toda's Theorem

Lance Fortnow

REVIEW

$\mathrm{Almost}\text{-}\oplus\mathrm{P} = \mathrm{BP}\cdot\oplus\mathrm{P}$ and a Random-Oracle Proof of Toda's Theorem

Lance Fortnow

Computational Complexity · Submitted 28 Sep 2026 · 13 references

Pith's verdict: Genuine new class equality with clean internal math; the one load-bearing external correlation bound needs a referee's fidelity check against the source.

T0 · AI review

How this review was made: An AI referee (deepseek/deepseek-v4-flash) read the paper on September 29, 2026 and answered a fixed list of questions about it. T0 is the starting level every paper gets. The levels describe how deeply Pith has checked the paper, never the authors.

T0 AI review An AI read the paper and answered a fixed list of questions.
T1 Audit Automatic checks that the references and files the paper relies on exist and match.
T2 Compute The paper's code or calculations re-run with the same results.
T3 Formal statement The claims written out in a formal math language a computer can read.
T4 Proof Those claims proved, and the proof checked by computer.

How Pith checks papers →

· 1 major objection · 4 minor · Ask about this paper · The compiled record · Read the full review →

Challenge this review Comment (0) Read on arXiv ↗

Cite ▾

arXiv ID2609.35326 (version 1)

Pith IDWHQEVLBS, Pith's permanent record of this paper and its review

CitationLance Fortnow. "$\mathrm{Almost}\text{-}\oplus\mathrm{P} = \mathrm{BP}\cdot\oplus\mathrm{P}$ and a Random-Oracle Proof of Toda's Theorem." arXiv:2609.35326 (2026). https://pith.science/paper/WHQEVLBS

Cite this reviewBibTeX for Pith's review of this paper

Claim paper

Why Pith says this

Highlight any text to comment on it.

Editor's note

read the letter

The paper settles a real open question: Almost-⊕P = BP·⊕P, the parity analogue of Bennett–Gill and Nisan–Wigderson. That equality was blocked on exactly what [CHLLTV26] just supplied, so the result is genuinely new and well-timed. I walked through the internal argument and it holds. Lemma 3.1's hybrid is sound: k = ⌈log(20N)⌉ ≤ T+6, √ℓ ≥ 4dt makes the hybrid step exactly (1/2)(2dt/√ℓ)^k ≤ 2^{k−1} ≤ ε/4N, and s(T) = kq² = O(T⁹). The polynomial-based design—distinct degree-≤T polynomials over GF(q) intersect in ≤T points—gives the near-disjoint blocks. Lemma 4.1's degree bound, Lemma 4.2's uniformization via outer regularity, and both Borel–Cantelli arguments (Prop 4.4 and Theorem 5.1's "hashing from far away," error (1−1/(8(m+1)))^{16(m+1)n} ≤ e^{−2n}) all check. The real content is the class equality. The Toda application is a new derivation of a known theorem (PH ⊆ BP·⊕P dates to 1991), and Section 7 is honest about this, framing the two proofs as opposite trades. No overclaiming, good discussion. One genuine soft spot, the only one: the entire Almost-⊕P ⊆ BP·⊕P inclusion rests on the external correlation bound (1), quoted from [CHLLTV26, Thm A.1], an ECCC report the paper doesn't reproduce. The transcription looks slightly garbled, and the referee's job is to check it against the source. The stress-test's analysis is right: the theorem tolerates constant distortion—a factor c>2 in the bound only pushes k to O(T) and ℓ to Θ(c²d²t²), keeping s(T) polynomial. Only a qualitative error (bound not exponentially small in k, or block size 2^{Ω(d)}) would break it, and that would contradict the cited report's headline result. So this is a verification duty, not a demonstrated gap. Worth a serious referee? Yes. The class equality is significant enough, and the single external premise is checkable. I'd send it out and expect acceptance after that fidelity check.

What would settle it

Check equation (1) directly for small parameters: take k = 3, ℓ odd near 16d²t² with d = t = 2, search all degree-2 $\mathbb{F}_2$-polynomials in $\mathbb{F}_2^{3\ell}$, and compute $|E_x[(-1)^{p(x)+\oplus_a \mathrm{Maj}(x^{(a)})}]|$. If any single polynomial beats $(2d/\sqrt{\ell})^k$ by a constant factor, the hybrid chains of Lemma 3.1 — which need the factor $(2dt/\sqrt{\ell})^k \le 2^{-k}$ — miss their error budget and Proposition 4.3 collapses. Independently, open [CHLLTV26, Theorem A.1] and confirm its statement matches equation (1) in the dependence of the exponent on k and in the size of ℓ; a mismatch in the ℓ-versus-d tradeoff would push the seed length $s(T) = O(T^9)$ to super-polynomial and void the Almost-⊕P ⊆ BP·⊕P inclusion.

Referee report

Significance

If correct, this is a genuine conceptual step: it completes the parity analogue of the classical Almost-class characterizations and re-frames the first half of Toda's theorem as a random-oracle collapse plus a single hardness-versus-randomness derandomization step. The structure is clean and modular, and — notably — every internal derivation verifies. I checked the hybrid parameters of Lemma 3.1 (k = ⌈log(2N/ε)⌉ ≤ T+6, √ℓ ≥ 4dt making (2dt/√ℓ)^k ≤ 2^{-k}, s(T) = kq² = O(T^9)); the uniformization argument of Lemma 4.2 (outer regularity, pigeonhole on cylinders, R_σ uniform on [σ]); the Borel–Cantelli error sums in Propositions 4.4 and Theorem 5.1 (Σ_n 2^n·2^{-2n} < ∞); the 'hashing from far away' isolation probability (1−1/(8(m+1)))^{16(m+1)n} ≤ e^{-2n}; and the collapse step via Fact 2.1. The single load-bearing external premise is bound (1), which the manuscript quotes rather than proves, and the argument is robust to constant-factor distortions of it. This is a paper I would expect to be widely cited as the definitive Almost-⊕P = BP·⊕P reference.

Major objections (1)

[§3, Eq. (1)] The entire error budget of Lemma 3.1, and therefore of Proposition 4.3 and Corollary 6.1, rests on the exact shape of the correlation bound quoted from [CHLLTV26, Theorem A.1]. I verified that all internal steps check out (k = ⌈log(2N/ε)⌉ ≤ T+6, √ℓ = 4dt makes (1/2)(2dt/√ℓ)^k = 2^{-k-1} ≤ ε/4N, s(T) = O(T^9)), so my request is a verification duty rather than a demonstrated gap: please confirm that (1) matches the source verbatim, namely degree d, k blocks of ℓ odd bits, and the constant 2. A qualitative transcription mismatch — for instance, a bound that is not exponentially small in k, or a hypothesis requiring block size 2^{Ω(d)} — would break the derivation. I note that the argument tolerates any constant factor c in the bound by raising ℓ to Θ(c²d²t²) and k to O(T), keeping s(T) polynomial, so a constant-scale mistranscription would be harmless; only a qualitative mismatch would matter, and that would contradict the cited report's stated headline content.

Minor objections (4)

[Abstract and §1] Several LaTeX spacing artifacts make formulas hard to read: 'betweenF 2-polynomials' in the abstract is missing a space, and in §2 and §5 expressions such as '⊕P ⊕PA = ⊕P A' and 'P ⊕PKR⊕R' render ambiguously; these should be typeset with proper superscripts (⊕P^{⊕P^A}, P^{⊕P^{K^R⊕R}}).
[§5, Theorem 5.1 (hashing from far away)] The strings 1^{p(|x|)+10}⟨x,i,b⟩ are claimed to be distinct and of length greater than p(|x|); this is true for a standard injective prefix-free encoding, but stating the encoding explicitly would make the claim immediately checkable and would remove any doubt that the hash bits lie outside the queried prefix p(|x|).
[§3, design paragraph] The sentence justifying the swap from the original combinatorial design to the polynomial-based design ('The analysis is unchanged') is correct because (1) applies to uniform blocks regardless of how the sets S_w are generated, but one clause making that point, and noting that |A| = ℓ is odd by the choice of the least odd ℓ ≥ 16d²t², would aid the reader.
[§5, specification formalism] The finite-specification formalism for Σ^R_k is clear and well chosen, and the remark that Σ^R_k is closed under join with R justifies the composition of time bounds p_Π; a one-sentence remark that this join property is what lets each N_i query R directly would round out the exposition.

How Pith checks papers → · Full audit of this paper →

The paper

The paper claims

This paper proves Almost-⊕P = BP·⊕P: for parity computation, random oracle acceptance equals bounded-error random seed acceptance, yielding a new random-oracle proof of the first half of Toda's theorem.

The reading

This paper establishes that Almost-⊕P = BP·⊕P = $BPP^{{⊕P}}$: a language is accepted with probability one by a ⊕P machine relative to a random oracle if and only if an ordinary bounded-error ⊕P machine accepts it using polynomially many random bits. That settles the parity analogue of Bennett and Gill's Almost-P = BPP and Nisan and Wigderson's Almost-PH = PH, a gap earlier pseudorandom generators could not close because their seed length was exponential in the degree. The engine is a new pseudorandom generator that fools polynomials over $\mathbb{F}_2$ of polynomial degree on exponentially many variables with polynomial seed length, built on the recent exponential correlation bounds between $\mathbb{F}_2$-polynomials and the XOR of majorities. Combined with Regan and Royer's observation that the polynomial hierarchy collapses into ⊕P relative to a random oracle, the equality yields a new proof of the first half of Toda's theorem, $\mathrm{PH} \subseteq \mathrm{BP}\cdot\oplus\mathrm{P} \subseteq \mathrm{P}^{\#\mathrm{P}}$, in which no probabilistic quantifier is ever moved through an oracle; the randomness is global, spent once to replace the oracle by a short seed.

What carries the argument

The load-bearing object is the pseudorandom generator $G_T$ of Lemma 3.1: a map from a seed of length $s(T) = O(T^9)$ to the truth assignment of every string of length at most T, which fools every $\mathbb{F}_2$-polynomial of degree at most T with error at most 1/10. Its analysis rests entirely on the external correlation bound (1) of [CHLLTV26]: for any $\mathbb{F}_2$-polynomial p of degree at most d on k blocks of ℓ bits, $|E_x[(-1)^{p(x)+\oplus_a \mathrm{Maj}(x^{(a)})}]| \le (2d/\sqrt{\ell})^k$. The proof is a hybrid argument — the XOR of k majorities is installed bit by bit, and each hybrid gap is controlled by the bound with $d := dt$ and the choice $\sqrt{\ell} \ge 4dt$, giving total error $\varepsilon/4$. The construction replaces the combinatorial design of [CHLLTV26] with a polynomial-based design, $S_w = \{(\alpha, f_w(\alpha)) : \alpha \in A \subseteq \mathrm{GF}(q)\}$ for distinct degree-at-most-T polynomials $f_w$, so each of the exponentially many output bits is computable in $\mathrm{poly}(T)$ time from the seed while pairwise intersections of the sets have size at most T; earlier output bits, restricted to $S_{w_j} \cap S_{w_i}$, have degree less than t, which keeps the substituted polynomial at degree below $dt$, exactly where bound (1) applies.

Extended reading notes

Core claim

The paper proves Theorem 1.1, that Almost-⊕P equals BP·⊕P, which in turn equals $BPP^{{⊕P}}$. Almost-⊕P collects the languages L for which L ∈ ⊕P^R holds with probability one when R is chosen by flipping each bit independently, while BP·⊕P is the bounded-error probabilistic class over ⊕P. The forward inclusion, Almost-⊕P ⊆ BP·⊕P, converts a ⊕P machine that is almost surely correct against a random oracle into one that is correct with probability 0.89 over a seed of polynomial length: by the degree lemma the machine is an $\mathbb{F}_2$-polynomial of degree at most T in the oracle bits, and the new generator fools all such polynomials with error 0.1. The reverse inclusion, BP·⊕P ⊆ Almost-⊕P, is a Borel-Cantelli argument: a BP·⊕P machine errs with probability summable over inputs, so relative to a random oracle it errs only finitely often and a finite table patches the remainder. The paper then combines Theorem 1.1 with the random-oracle collapse $\mathrm{PH}^R \subseteq \oplus\mathrm{P}^R$ (Theorem 5.1, credited to Regan and Royer) to obtain Corollary 6.1, $\mathrm{PH} \subseteq \mathrm{BP}\cdot\oplus\mathrm{P} \subseteq \mathrm{P}^{\#\mathrm{P}}$, the first half of Toda's theorem, proved with no probabilistic quantifier ever moved through an oracle. The distinctive feature is the trade the author draws between this route and the elementary 2009 proof: here the collapse of the hierarchy becomes straightforward and all of the difficulty is concentrated in a single hardness-versus-randomness step.

Load-bearing premise

Everything rests on the exponential correlation bound (1), quoted from an external report, which says a degree-d $\mathbb{F}_2$-polynomial has correlation at most $(2d/\sqrt{\ell})^k$ with the XOR of k majorities of ℓ-bit blocks; if that bound were any weaker, or needed a larger block size, the generator's seed length would stop being polynomial and Almost-⊕P ⊆ BP·⊕P would fail.

Editorial extensions

If this is right

PH ⊆ BP·⊕P follows without ever moving a probabilistic quantifier through an oracle: the hierarchy collapses relative to a random oracle, and the equality Almost-⊕P = BP·⊕P just removes that oracle (Corollary 6.1).
Consequently PH ⊆ P^#P, the full content of the first half of Toda's theorem, via the known inclusion BP·⊕P ⊆ P^#P (Corollary 6.1).
An exponentially long random oracle can, for ⊕P computation, be replaced by polynomially many random bits without loss of accepting power (Theorem 1.1).
The argument relativizes: for every oracle A, {L : Pr_R[L ∈ ⊕P^{A⊕R}] = 1} = BP·⊕P^A, so the derandomization holds relative to any fixed oracle (Remark 4.5).

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The quantitative bottleneck of the whole route is the ℓ-versus-d tradeoff inside bound (1): the seed length $s(T) = O(T^9)$ comes from choosing ℓ ≥ 16d²t² and k ≈ log N, so a stronger bound allowing ℓ to grow only linearly in d would shrink the seed and sharpen the inclusion, while a weaker bound would break it; the paper itself does not chase such a tightening.
The 'hashing from far away' move of Theorem 5.1 — reading Valiant-Vazirani's random hashes from oracle strings longer than the machine's query length — looks like a reusable template: to derandomize a random oracle for a class, the oracle must supply independent randomness beyond the reach of the machine, and the bracket that removes the oracle is independent of how the classes are defined.
The random-oracle route itself never produces the BP·⊕P ⊆ P^#P step; the paper quotes [Tod91] and [For09] for it. I read the paper's value as explanatory rather than a new upper bound: it reframes the first half of Toda as 'collapse relative to an oracle plus derandomization', a claim about why the theorem is true, not a cheaper proof of it.

Original abstract

Using the recent exponential correlation bounds of Chattopadhyay, Hatami, Lee, Lovett, Tal and Viola between $\mathbb{F}_2$-polynomials and the XOR of majorities, we show that $\mathrm{Almost}\text{-}\oplus\mathrm{P} = \mathrm{BP}\cdot\oplus\mathrm{P}$, where $\mathrm{Almost}\text{-}\oplus\mathrm{P}$ is the class of languages that lie in $\oplus\mathrm{P}^R$ with probability one for a random oracle $R$. This is the parity analogue of Bennett and Gill's $\mathrm{Almost}\text{-}\mathrm{P} = \mathrm{BPP}$ and Nisan and Wigderson's $\mathrm{Almost}\text{-}\mathrm{PH} = \mathrm{PH}$. The key ingredient is a pseudorandom generator with polynomial seed length that fools $\mathbb{F}_2$-polynomials of polynomial degree on exponentially many variables. As an application we complete a random-oracle proof of the first half of Toda's theorem, $\mathrm{PH} \subseteq \mathrm{BP}\cdot\oplus\mathrm{P}$, following an approach of Regan and Royer. Relative to a random oracle, the polynomial hierarchy collapses into $\oplus\mathrm{P}$ by applying Valiant-Vazirani and Papadimitriou-Zachos level by level, with no probabilistic quantifier ever moved through an oracle. Our result then removes the oracle. We compare this argument with the simple proof of Toda's theorem by Fortnow (2009).

The compiled record

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-09-29: 1 request, 6,009 input tokens.

What the abstract itself states, as probabilities: claims first 0.10 · states limitation 0.18 · human participants 0.01 · controlled comparison 0.05 · randomized assignment 0.07 · states quantitative result 0.29 · compares with prior results 0.97 · mentions code or data availability 0.02.

The abstract, sentence by sentence

arXiv listing abstract v1. Results and the main claim are underlined; show every role.

Using the recent exponential correlation bounds of Chattopadhyay, Hatami, Lee, Lovett, Tal and Viola between $\mathbb{F}_2$-polynomials and the XOR of majorities, we show that $\mathrm{Almost}\text{-}\oplus\mathrm{P} = \mathrm{BP}\cdot\oplus\mathrm{P}$, where $\mathrm{Almost}\text{-}\oplus\mathrm{P}$ is the class of languages that lie in $\oplus\mathrm{P}^R$ with probability one for a random oracle $R$. This is the parity analogue of Bennett and Gill's $\mathrm{Almost}\text{-}\mathrm{P} = \mathrm{BPP}$ and Nisan and Wigderson's $\mathrm{Almost}\text{-}\mathrm{PH} = \mathrm{PH}$. The key ingredient is a pseudorandom generator with polynomial seed length that fools $\mathbb{F}_2$-polynomials of polynomial degree on exponentially many variables. As an application we complete a random-oracle proof of the first half of Toda's theorem, $\mathrm{PH} \subseteq \mathrm{BP}\cdot\oplus\mathrm{P}$, following an approach of Regan and Royer. Relative to a random oracle, the polynomial hierarchy collapses into $\oplus\mathrm{P}$ by applying Valiant-Vazirani and Papadimitriou-Zachos level by level, with no probabilistic quantifier ever moved through an oracle. Our result then removes the oracle. We compare this argument with the simple proof of Toda's theorem by Fortnow (2009).

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#	sentence	role	the authors' own work	states the main conclusion	strength
s0	Using the recent exponential correlation bounds of Chattopadhyay, Hatami, Lee, Lovett, Tal and Viola between $\mathbb{F}_2$-polynomials and the XOR of majorities, we show that $\mathrm{Almost}\text{-}\oplus\mathrm{P} = \mathrm{BP}\cdot\oplus\mathrm{P}$, where $\mathrm{Almost}\text{-}\oplus\mathrm{P}$ is the class of languages that lie in $\oplus\mathrm{P}^R$ with probability one for a random oracle $R$.	result 0.89	0.94	0.91	asserted 1.00
s1	This is the parity analogue of Bennett and Gill's $\mathrm{Almost}\text{-}\mathrm{P} = \mathrm{BPP}$ and Nisan and Wigderson's $\mathrm{Almost}\text{-}\mathrm{PH} = \mathrm{PH}$.	interpretation 0.61	0.22	0.08	asserted 1.00
s2	The key ingredient is a pseudorandom generator with polynomial seed length that fools $\mathbb{F}_2$-polynomials of polynomial degree on exponentially many variables.	method 0.84	0.71	0.04	asserted 1.00
s3	As an application we complete a random-oracle proof of the first half of Toda's theorem, $\mathrm{PH} \subseteq \mathrm{BP}\cdot\oplus\mathrm{P}$, following an approach of Regan and Royer.	contribution 0.52	0.90	0.10	asserted 1.00
s4	Relative to a random oracle, the polynomial hierarchy collapses into $\oplus\mathrm{P}$ by applying Valiant-Vazirani and Papadimitriou-Zachos level by level, with no probabilistic quantifier ever moved through an oracle.	method 0.79	0.48	0.06	asserted 1.00
s5	Our result then removes the oracle.	contribution 0.36	0.91	0.13	asserted 1.00
s6	We compare this argument with the simple proof of Toda's theorem by Fortnow (2009).	contribution 0.66	0.79	0.03	asserted 0.79

What kind of paper the classifier reports this is: theoretical result 1.00 · evidence from proof or derivation 1.00.

What was examined, and what was not

sources read

arXiv listing abstract v1

not examined

full text
figures and tables
references and citing sentences
relations to other papers

levels run

P abstract

not run

S sections
T body sentences
C citations
R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

References

Works cited (13)

[1]

K. Ambos-Spies. Randomness, relativizations, and polynomial reducibilities. In Structure in Complexity Theory , volume 223 of Lecture Notes in Computer Science , pages 23--34. Springer, 1986

View on Pith 1986
[2]

C. H. Bennett and J. Gill. Relative to a random oracle A , P ^ A NP ^ A co - NP ^ A with probability 1. SIAM Journal on Computing , 10(1):96--113, 1981

View on Pith 1981
[3]

A. Bogdanov. Pseudorandom generators for low degree polynomials. In Proceedings of the 37th ACM Symposium on Theory of Computing , pages 21--30, 2005

View on Pith 2005
[4]

E. Chattopadhyay, P. Hatami, C. H. Lee, S. Lovett, A. Tal, and E. Viola. Exponential correlation bounds for polynomials. Electronic Colloquium on Computational Complexity, Report No. 208, 2026

View on Pith 2026
[5]

L. Fortnow. A simple proof of T oda's theorem. Theory of Computing , 5(7):135--140, 2009

View on Pith 2009
[6]

S. Lovett. Unconditional pseudorandom generators for low degree polynomials. Theory of Computing , 5(1):69--82, 2009

View on Pith 2009
[7]

N. Nisan and A. Wigderson. Hardness vs randomness. Journal of Computer and System Sciences , 49(2):149--167, 1994

View on Pith 1994
[8]

C. H. Papadimitriou and S. Zachos. Two remarks on the power of counting. In Proceedings of the 6th GI Conference on Theoretical Computer Science , volume 145 of Lecture Notes in Computer Science , pages 269--276. Springer, 1983

View on Pith 1983
[9]

K. W. Regan and J. S. Royer. On closure properties of bounded two-sided error complexity classes. Mathematical Systems Theory , 28:229--243, 1995

View on Pith 1995
[10]

S. Toda. PP is as hard as the polynomial-time hierarchy. SIAM Journal on Computing , 20(5):865--877, 1991

View on Pith 1991
[11]

E. Viola. The sum of d small-bias generators fools polynomials of degree d . Computational Complexity , 18(2):209--217, 2009

View on Pith 2009
[12]

L. G. Valiant and V. V. Vazirani. NP is as easy as detecting unique solutions. Theoretical Computer Science , 47:85--93, 1986

View on Pith 1986
[13]

S. Zachos. Probabilistic quantifiers and games. Journal of Computer and System Sciences , 36(3):433--451, 1988

View on Pith 1988

Discussion

Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.

[1] [1]

K. Ambos-Spies. Randomness, relativizations, and polynomial reducibilities. In Structure in Complexity Theory , volume 223 of Lecture Notes in Computer Science , pages 23--34. Springer, 1986

View on Pith 1986

[2] [2]

C. H. Bennett and J. Gill. Relative to a random oracle A , P ^ A NP ^ A co - NP ^ A with probability 1. SIAM Journal on Computing , 10(1):96--113, 1981

View on Pith 1981

[3] [3]

A. Bogdanov. Pseudorandom generators for low degree polynomials. In Proceedings of the 37th ACM Symposium on Theory of Computing , pages 21--30, 2005

View on Pith 2005

[4] [4]

E. Chattopadhyay, P. Hatami, C. H. Lee, S. Lovett, A. Tal, and E. Viola. Exponential correlation bounds for polynomials. Electronic Colloquium on Computational Complexity, Report No. 208, 2026

View on Pith 2026

[5] [5]

L. Fortnow. A simple proof of T oda's theorem. Theory of Computing , 5(7):135--140, 2009

View on Pith 2009

[6] [6]

S. Lovett. Unconditional pseudorandom generators for low degree polynomials. Theory of Computing , 5(1):69--82, 2009

View on Pith 2009

[7] [7]

N. Nisan and A. Wigderson. Hardness vs randomness. Journal of Computer and System Sciences , 49(2):149--167, 1994

View on Pith 1994

[8] [8]

C. H. Papadimitriou and S. Zachos. Two remarks on the power of counting. In Proceedings of the 6th GI Conference on Theoretical Computer Science , volume 145 of Lecture Notes in Computer Science , pages 269--276. Springer, 1983

View on Pith 1983

[9] [9]

K. W. Regan and J. S. Royer. On closure properties of bounded two-sided error complexity classes. Mathematical Systems Theory , 28:229--243, 1995

View on Pith 1995

[10] [10]

S. Toda. PP is as hard as the polynomial-time hierarchy. SIAM Journal on Computing , 20(5):865--877, 1991

View on Pith 1991

[11] [11]

E. Viola. The sum of d small-bias generators fools polynomials of degree d . Computational Complexity , 18(2):209--217, 2009

View on Pith 2009

[12] [12]

L. G. Valiant and V. V. Vazirani. NP is as easy as detecting unique solutions. Theoretical Computer Science , 47:85--93, 1986

View on Pith 1986

[13] [13]

S. Zachos. Probabilistic quantifiers and games. Journal of Computer and System Sciences , 36(3):433--451, 1988

View on Pith 1988