Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR96-018 | 16th April 1997 00:00

On the Complexity of Interactive Proof with Bounded Communication Revision of: TR96-018

RSS-Feed




Revision #2
Authors: Oded Goldreich, Johan Håstad
Accepted on: 16th April 1997 00:00
Downloads: 3468
Keywords: 


Abstract:

We investigate the computational complexity of languages
which have interactive proof systems of bounded message complexity.
In particular, denoting the length of the input by $n$, we show that
(1) If $L$ has an interactive proof in which the total
communication is bounded by $c(n)$ bits
then $L$ can be recognized by a probabilitic machine
in time exponential in $O(c(n) + \log(n))$.
(2) If $L$ has an AM-proof in which the prover sends $c(n)$ bits
then $L$ can be recognized by a probabilitic machine
in time exponential in $O(c(n)\log(c(n)) + \log(n))$.
(3) If $L$ has an interactive proof in which the prover sends $c(n)$ bits
then $L$ can be recognized by a probabilitic machine with an NP-oracle
in time exponential in $O(c(n)\log(c(n)) + \log(n))$.


Revision #1 to TR96-018 | 11th April 1997 00:00

On the Message Complexity of Interactive Proof Systems Revision of: TR96-018





Revision #1
Authors: Oded Goldreich, Johan Håstad
Accepted on: 11th April 1997 00:00
Downloads: 3266
Keywords: 


Abstract:

We investigate the computational complexity of languages
which have interactive proof systems of bounded message complexity.
In particular, denoting the length of the input by $n$, we show that
(1) If $L$ has an interactive proof in which the total
communication is bounded by $c(n)$ bits
then $L$ can be recognized by a probabilitic machine
in time exponential in $O(c(n) + \log(n))$.
(2) If $L$ has an AM-proof in which the prover sends $c(n)$ bits
then $L$ can be recognized by a probabilitic machine
in time exponential in $O(c(n)\log(c(n)) + \log(n))$.
(3) If $L$ has an interactive proof in which the prover sends $c(n)$ bits
then $L$ can be recognized by a probabilitic machine with an NP-oracle
in time exponential in $O(c(n)\log(c(n)) + \log(n))$.


Paper:

TR96-018 | 23rd February 1996 00:00

On the Message Complexity of Interactive Proof Systems





TR96-018
Authors: Oded Goldreich, Johan Håstad
Publication: 24th February 1996 11:21
Downloads: 3333
Keywords: 


Abstract:

We investigate the computational complexity of languages
which have interactive proof systems of bounded message complexity.
In particular, we show that
(1) If $L$ has an interactive proof in which the total
communication is bounded by $c(n)$ bits
then $L$ can be recognized a probabilitic machine
in time exponential in $O(c(n) + \log(n))$.
(2) If $L$ has an AM-proof in which the prover sends $c(n)$ bits
then $L$ can be recognized a probabilitic machine
in time exponential in $O(c(n)\log(c(n)) + \log(n))$.
(3) If $L$ has an interactive proof in which the prover sends $c(n)$ bits
then $L$ can be recognized a probabilitic machine with an NP-oracle
in time exponential in $O(c(n)\log(c(n)) + \log(n))$.



ISSN 1433-8092 | Imprint