The Revitalized Relationship Between Probabilistically Checkable Debate Systems, IP, and PSpace
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 [4, 5]. In particular, it was shown that SPACE = PCDS[log n, 1] = RPCDS [log...
Main Authors: | Russell, Alexander, Sundaram, Ravi |
---|---|
Published: |
2023
|
Online Access: | https://hdl.handle.net/1721.1/149213 |
Similar Items
-
Probabilistically checkable proofs
by: Sudan, Madhu
Published: (2010) -
Implementing Probabilistically Checkable Proofs of Proximity
by: Bhattacharyya, Arnab
Published: (2005) -
Fine-grained complexity meets IP = PSPACE
by: Chen, Lijie, et al.
Published: (2021) -
Digital signatures from probabilistically checkable proofs
by: Sidney, Raymond M. (Raymond Mark)
Published: (2007) -
Probabilistically checkable proofs and the testing of Hadamard-like codes
by: Kiwi, Marcos
Published: (2005)