Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR17-055 | 26th March 2017 19:11

Round Complexity Versus Randomness Complexity in Interactive Proofs

RSS-Feed




TR17-055
Authors: Maya Leshkowitz
Publication: 26th March 2017 19:25
Downloads: 1220
Keywords: 


Abstract:

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 resulting interactive proof system has perfect completeness.



ISSN 1433-8092 | Imprint