Efficient Probabilistically Checkable Debates

Andrew Drucker

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Probabilistically checkable debate systems (PCDSs) are debates between two competing provers, in which a polynomial-time verifier inspects a constant number of bits of the debate. It was shown by Condon, Feigenbaum, Lund, and Shor that every language in PSPACE has a PCDS in which the debate length is polynomially bounded. Using this result, they showed that the approximation versions of some natural PSPACE-complete problems are also PSPACE-complete.

We give an improved construction of these debates: for any language L that has an ordinary debate system definable by uniform circuits of size s = s(n), we give a PCDS for L whose debate is of total bitlength TeX , with a verifier that uses only log 2 s + log 2 (polylog (s)) bits of randomness. This yields a much tighter connection between the time complexity of natural PSPACE-complete problems and the time complexity of their approximation versions.

Our key ingredient is a novel application of error-resilient communication protocols, as developed by Schulman; we use the more recent protocol of Braverman and Rao. We show that by requiring ordinary debates to be encoded in an error-resilient fashion, we can endow them with a useful “stability” property. Stable debates can then be transformed into PCDSs, by applying efficient PCPPs (as given by Dinur). Our main technical challenge in building stable debates is to enforce error-resilient encoding by the debaters. To achieve this, we show that there is a constant-round debate system, with a very efficient verifier, to debate whether a communication transcript follows the Braverman-Rao protocol.
Original languageEnglish
Title of host publicationApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Subtitle of host publication14th International Workshop, APPROX 2011, and 15th International Workshop, RANDOM 2011, Princeton, NJ, USA, August 17-19, 2011. Proceedings
PublisherSpringer Berlin Heidelberg
Pages519-529
Number of pages11
Volume6845
ISBN (Electronic)978-3-642-22935-0
ISBN (Print)978-3-642-22934-3
DOIs
Publication statusPublished - 2011

Fingerprint

Dive into the research topics of 'Efficient Probabilistically Checkable Debates'. Together they form a unique fingerprint.

Cite this