Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Maya Leshkowitz:

TR17-055 | 26th March 2017
Maya Leshkowitz

Round Complexity Versus Randomness Complexity in Interactive Proofs

Consider an interactive proof system for some set S that has randomness complexity r(n) for instances of length n, and arbitrary round complexity. We show a public-coin interactive proof system for S of round complexity O(r(n)/log n). Furthermore, the randomness complexity is preserved up to a constant factor, and the ... more >>>

TR16-066 | 19th April 2016
Oded Goldreich, Maya Leshkowitz

On Emulating Interactive Proofs with Public Coins

The known emulation of interactive proof systems by public-coins interactive proof systems proceeds by selecting, at each round, a message such that each message is selected with probability that is at most polynomially larger than its probability in the original protocol.
Specifically, the possible messages are essentially clustered according to ... more >>>

ISSN 1433-8092 | Imprint