On Toda’s Theorem in structural communication complexity

Abstract

We prove Toda’s Theorem in the context of structural communication complexity, i.e. PHcc Í BP · ÅPcc Í Pcc (#Pcc) = Pcc (PPcc). The class PSPACEcc was defined via alternating protocols with O(log n) many alternations. We consider the class BP · ÅPcc of Toda’s Theorem and show that every language in this class can be decided with alternating protocols using O(log n/ log log n) many alternations. The proof is based on a new alternating protocol for the inner product function IP with O(log n/ log log n) many alternations.