Private vs. common random bits in communication complexity
From MaRDI portal
Publication:1182120
DOI10.1016/0020-0190(91)90157-DzbMath0735.68034OpenAlexW2088263428MaRDI QIDQ1182120
Publication date: 27 June 1992
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(91)90157-d
Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
On multi-partition communication complexity ⋮ Multiple Usage of Random Bits in Finite Automata ⋮ On Slepian-Wolf theorem with interaction ⋮ Sample Complexity Bounds on Differentially Private Learning via Communication Complexity ⋮ The communication complexity of the Hamming distance problem ⋮ A characterization of average case communication complexity ⋮ Unnamed Item ⋮ The Cost of Fault Tolerance in Multi-Party Communication Complexity ⋮ The landscape of communication complexity classes ⋮ Superlinear lower bounds for multipass graph processing ⋮ Towards a reverse Newman's theorem in interactive information complexity ⋮ Certifying equality with limited interaction ⋮ Disjointness through the lens of Vapnik-Chervonenkis dimension: sparsity and beyond ⋮ Making Randomness Public in Unbounded-Round Information Complexity ⋮ On public-coin zero-error randomized communication complexity ⋮ Logarithmic Sobolev inequality for lattice gases mixing conditions ⋮ Equality, Revisited ⋮ Space lower bounds for online pattern matching ⋮ Network Decomposition and Distributed Derandomization (Invited Paper) ⋮ Approximate nonnegative rank is equivalent to the smooth rectangle bound ⋮ A note on randomized streaming space bounds for the longest increasing subsequence problem ⋮ Guess-and-verify versus unrestricted nondeterminism for OBDDs and one-way Turing machines. ⋮ A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification ⋮ An efficient superpostional quantum Johnson-Lindenstrauss lemma via unitary \(t\)-designs ⋮ Revisiting time-space tradeoffs for function inversion ⋮ Succinct interactive oracle proofs: applications and limitations ⋮ Low communication complexity protocols, collision resistant hash functions and secret key-agreement protocols ⋮ The unbounded-error communication complexity of symmetric functions ⋮ Communication and information complexity ⋮ Pseudorandom generators, typically-correct derandomization, and circuit lower bounds ⋮ Dimension-free bounds and structural results in communication complexity ⋮ Weak derandomization of weak algorithms: explicit versions of Yao's lemma ⋮ Arthur and Merlin as oracles ⋮ Information complexity and applications. ⋮ An Exponential Separation Between MA and AM Proofs of Proximity ⋮ Lower bounds for sampling algorithms for estimating the average ⋮ An exponential separation between \textsf{MA} and \textsf{AM} proofs of proximity ⋮ Tight Bounds on Communication Complexity of Symmetric XOR Functions in One-Way and SMP Models ⋮ Space Lower Bounds for Online Pattern Matching ⋮ Non-interactive proofs of proximity ⋮ Disjointness through the Lens of Vapnik-Chervonenkis Dimension: Sparsity and Beyond ⋮ Lower bounds for predecessor searching in the cell probe model ⋮ Bounds on tradeoffs between randomness and communication complexity ⋮ Growth and structure of the World Wide Web: Towards realistic modeling ⋮ Partition arguments in multiparty communication complexity ⋮ On Slepian–Wolf Theorem with Interaction ⋮ Arthur and Merlin as Oracles ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Dimension Reduction for Polynomials over Gaussian Space and Applications ⋮ New Strong Direct Product Results in Communication Complexity ⋮ Placing conditional disclosure of secrets in the communication complexity universe ⋮ Rectangles Are Nonnegative Juntas ⋮ Near-optimal communication-time tradeoff in fault-tolerant computation of aggregate functions ⋮ Public vs. private randomness in simultaneous multi-party communication complexity ⋮ Superfast coloring in CONGEST via efficient color sampling ⋮ Choosing, agreeing, and eliminating in communication complexity ⋮ Superfast coloring in CONGEST via efficient color sampling ⋮ Upper and Lower Bounds on the Power of Advice ⋮ New bounds on classical and quantum one-way communication complexity ⋮ Fooling Pairs in Randomized Communication Complexity ⋮ Quantum communication and complexity. ⋮ Unnamed Item ⋮ Upper bounds on communication in terms of approximate rank ⋮ On the streaming indistinguishability of a random permutation and a random function
Cites Work
