2026-08-17T06:35:27Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9453 2024-03-06T10:44:26Z ddc:004 open_access

Round Complexity Versus Randomness Complexity in Interactive Proofs Leshkowitz, Maya 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 resulting interactive proof system has perfect completeness. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Maya Leshkowitz 2018 Is Part Of LIPIcs, Volume 116, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2018.49 urn:nbn:de:0030-drops-94530 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.49 eng https://creativecommons.org/licenses/by/3.0/legalcode