Communication complexity vs randomness complexity in interactive proofs

DOI10.4230/LIPICS.ITC.2024.2MaRDI QIDQ6864458zbMATH OpenFDO

Authors Benny Applebaum, Kaartik Bhushan, Manoj Prabhakaran

Publication date 3 February 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ITC.2024.2

zbMATH Keywords

communication complexitycompressionhash functionsinteractive proof systemspseudo-random generators

Mathematics Subject Classification ID

Communication complexity, information complexity (68Q11) Communication theory (94A05) Cryptography (94A60)

Cites work

• A Mathematical Theory of Communication
• Algebraic methods for interactive proof systems
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• Compression of samplable sources
• Computational Complexity
• Derandomization in Cryptography
• Derandomizing Arthur-Merlin games using hitting sets
• Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
• scientific article; zbMATH DE number 2185600 (Why is no real title available?)
• scientific article; zbMATH DE number 1261820 (Why is no real title available?)
• scientific article; zbMATH DE number 2019636 (Why is no real title available?)
• scientific article; zbMATH DE number 1559537 (Why is no real title available?)
• scientific article; zbMATH DE number 7563815 (Why is no real title available?)
• scientific article; zbMATH DE number 7706036 (Why is no real title available?)
• Incompressible functions, relative-error extractors, and the power of nondeterministic reductions
• IP = PSPACE
• Low-End Uniform Hardness versus Randomness Tradeoffs for AM
• Nondeterministic direct product reductions and the success probability of SAT solvers
• On Emulating Interactive Proofs with Public Coins
• On promise problems: a survey
• On the hardness of computing the permanent of random matrices
• Pseudorandomness for approximate counting and sampling
• Random generation of combinatorial structures from a uniform distribution
• Simple extractors for all min-entropies and a new pseudorandom generator
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• The knowledge complexity of interactive proof-systems
• Uniform hardness versus randomness tradeoffs for Arthur-Merlin games
• Universal classes of hash functions
• Weak derandomization of weak algorithms: explicit versions of Yao's lemma
• Worst-case interactive communication. I. Two messages are almost optimal

This page was built for publication: Communication complexity vs randomness complexity in interactive proofs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6864458)