A Circuit-Based Proof of Toda′s Theorem

We present a simple proof of Toda′s result (Toda (1989), in "Proceedings, 30th Annual IEEE Symposium on Foundations of Computer Science, " pp. 514-519), which states that ⊕ P is hard for the Polynomial Hierarchy under randomized reductions. Our approach is circuit-based in the sense that we start with uniform circuit definitions of the Polynomial Hierarchy and apply the Valiant-Vazirani lemma on these circuits (Valiant and Vazirani (1986), Thoeret. Comput. Sci. 47, 85-93).

Authors

• R. Kannan
• H. Venkateswaran
• V. Vinay
• A.C. Yao

Keywords

No keywords are indexed for this paper.