Strong communication complexity or generating quasi-random sequences from two communicating semi-random sources

DOI10.1007/BF02579325zbMath0643.94002OpenAlexW2065392541MaRDI QIDQ1102253

Umesh V. Vazirani

Publication date: 1987

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02579325

zbMATH Keywords

communication complexityimperfect and correlated sources of randomnesssemi-random source

Mathematics Subject Classification ID

Communication theory (94A05)

Related Items

On the complexity of approximating the VC dimension., Generating quasi-random sequences from semi-random sources, Incompressible functions, relative-error extractors, and the power of nondeterministic reductions, Deterministic extractors for affine sources over large fields, Efficient learning of typical finite automata from random walks, Simulating BPP using a general weak random source, Extracting information is hard: a Turing degree of non-integral effective Hausdorff dimension, Linear algebraic methods in communication complexity, How to get more mileage from randomness extractors, Some extremal problems arising from discrete control processes, Weak derandomization of weak algorithms: explicit versions of Yao's lemma, Increasing the Output Length of Zero-Error Dispersers, Deterministic extractors for small-space sources, Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs, Improving the Hadamard extractor, Rainbow paths, On extractors and exposure‐resilient functions for sublogarithmic entropy, Extracting all the randomness and reducing the error in Trevisan's extractors, Synthesizers and their application to the parallel construction of pseudo-random functions, Increasing the output length of zero-error dispersers, Extracting randomness: A survey and new constructions, Probabilistic encryption, The Complexity of Differential Privacy

Cites Work

• Generating quasi-random sequences from semi-random sources
• Independent unbiased coin flips from a correlated biased source - a finite state Markov chain
• Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
• The Wire-Tap Channel
• The Efficient Construction of an Unbiased Random Sequence
• Class of constructive asymptotically good algebraic codes
• Unnamed Item
• Unnamed Item
• Unnamed Item