Browsing LCS Technical Memos (1974 - 2003) by Author "Sundaram, Ravi"

Now showing items 1-3 of 3

    • The Revitalized Relationship Between Probabilistically Checkable Debate Systems, IP, and PSpace 

      Russell, Alexander; Sundaram, Ravi (1993-09)
      In 1990, PSPACE was shown to be identical to IP, the class of languages with interactive proofs [11, 2]. Recently, PSPACE was again recharacterized, this time in terms of (Random) Probabilistically Checkable Debate Systems ...

    • Symmetric Alteration Captures BPP 

      Russell, Alexander; Sundaram, Ravi (1995-11)
      We introduce the natural class Sp2 containing those languages which may be expressed terms of two symmetric quantifiers. This class lies between ?p2 and ? and naturally generates a "symmetric" hierarchy corresponding to ...

    • Symmetric Alternation Captures BPP 

      Russell, Alexander; Sundaram, Ravi (1995-11)
      We introduce the natural class Sp2 containing those languages which may be expressed in terms of two symmetric quantifiers. This class lies between ? and ? and naturally generates a "symmetric" hierarchy corresponding to ...