Author name cluster

A.C. Yao

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

1 paper

1 author row

I&C Journal 1993 Journal Article

A Circuit-Based Proof of Toda′s Theorem

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

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

Details DOI