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 (23)

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

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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

This page was built for publication: Strong communication complexity or generating quasi-random sequences from two communicating semi-random sources