Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
From MaRDI portal
Publication:3787911
DOI10.1137/0217015zbMath0644.94008OpenAlexW2151303208MaRDI QIDQ3787911
Publication date: 1988
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0217015
Related Items
On secret sharing, randomness, and random-less reductions for secret sharing, Extractors: low entropy requirements colliding with non-malleability, Paradigms for Unconditional Pseudorandom Generators, A comprehensive review of quantum random number generators: concepts, classification and the origin of randomness, A lower bound for proving hardness of learning with rounding with polynomial modulus, Deterministic extractors for small-space sources, Improved Extractors for Recognizable and Algebraic Sources, Extracting all the randomness and reducing the error in Trevisan's extractors, Extractors in Paley graphs: a random model, Rectangles Are Nonnegative Juntas, Extractors and Lower Bounds for Locally Samplable Sources, Improved computational extractors and their applications, A lower bound for depth-3 circuits with MOD \(m\) gates, One-message zero knowledge and non-malleable commitments, Deterministic Randomness Extraction from Generalized and Distributed Santha-Vazirani Sources, Zero-Fixing Extractors for Sub-Logarithmic Entropy, How to Compute in the Presence of Leakage, Incompressible functions, relative-error extractors, and the power of nondeterministic reductions, No time to hash: on super-efficient entropy accumulation, From Affine to Two-Source Extractors via Approximate Duality, Extractors for weak random sources and their applications, Tightly secure signatures from lossy identification schemes, Privacy with Imperfect Randomness, Communication Complexity of Conditional Disclosure of Secrets and Attribute-Based Encryption, Lower bounds for one-way probabilistic communication complexity and their application to space complexity, Strong communication complexity or generating quasi-random sequences from two communicating semi-random sources, Local Correlation Breakers and Applications to Three-Source Extractors and Mergers, Deterministic extractors for affine sources over large fields, An Efficient Reduction from Two-Source to Nonmalleable Extractors: Achieving Near-Logarithmic Min-Entropy, Extracting Computational Entropy and Learning Noisy Linear Functions, Efficient learning of typical finite automata from random walks, Communication complexity of matrix computation over finite fields, Hadamard tensors and lower bounds on multiparty communication complexity, Simulating BPP using a general weak random source, Quantum entanglement and the communication complexity of the inner product function, Communication complexity with small advantage, 2-source dispersers for \(n^{o(1)}\) entropy, and Ramsey graphs beating the Frankl-Wilson construction, Space lower bounds for online pattern matching, On the power of circuits with gates of low \(L_{1}\) norms., Leakage Resilience of the Blom’s Key Distribution Scheme, On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing, Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors, Deterministic Randomness Extraction from Generalized and Distributed Santha--Vazirani Sources, Approximation of boolean functions by combinatorial rectangles, Linear algebraic methods in communication complexity, Unnamed Item, On the binary and Boolean rank of regular matrices, Learning under \(p\)-tampering poisoning attacks, Unnamed Item, Unnamed Item, Unnamed Item, 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, Nonmalleable Extractors and Codes, with Their Many Tampered Extensions, Isolation, matching, and counting uniform and nonuniform upper bounds, Increasing the Output Length of Zero-Error Dispersers, Lower bounds for one-way probabilistic communication complexity, Interleaved Group Products, The NOF multiparty communication complexity of composed functions, The hardest halfspace, On the restricted isometry property of the Paley matrix, Information lower bounds via self-reducibility, Space Lower Bounds for Online Pattern Matching, An Introduction to Randomness Extractors, Non-malleable coding against bit-wise and split-state tampering, On the power of small-depth threshold circuits, Bounds on tradeoffs between randomness and communication complexity, Improving the Hadamard extractor, Simpler session-key generation from short random passwords, On extractors and exposure‐resilient functions for sublogarithmic entropy, Post-challenge leakage in public-key encryption, The Paley graph conjecture and Diophantine \(m\)-tuples, Distinguishing Distributions Using Chernoff Information, Extractors from Reed-Muller codes, Weaknesses of Cuckoo Hashing with a Simple Universal Hash Class: The Case of Large Universes, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Leakage-Resilient Cryptography over Large Finite Fields: Theory and Practice, Reusable fuzzy extractors for low-entropy distributions, One-message statistical Zero-Knowledge Proofs and space-bounded verifier, Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$, A unified approach to deterministic encryption: new constructions and a connection to computational entropy, Tradeoff lower lounds for stack machines, Upper and Lower Bounds on the Power of Advice, The Multiparty Communication Complexity of Set Disjointness, Extracting randomness from extractor-dependent sources, How to extract useful randomness from unreliable sources, Unnamed Item, Relations between communication complexity classes, Multi-source non-malleable extractors and applications, Time-space lower bounds for two-pass learning, Sign rank vs discrepancy, Bounds on Fixed Input/Output Length Post-processing Functions for Biased Physical Random Number Generators, Independent unbiased coin flips from a correlated biased source - a finite state Markov chain, Explicit two-source extractors and resilient functions, Unnamed Item, Additive Combinatorics: With a View Towards Computer Science and Cryptography—An Exposition, Synthesizers and their application to the parallel construction of pseudo-random functions, Approximating Rectangles by Juntas and Weakly Exponential Lower Bounds for LP Relaxations of CSPs, Two-Source Dispersers for Polylogarithmic Entropy and Improved Ramsey Graphs, An Additive Combinatorics Approach Relating Rank to Communication Complexity, Communication Lower Bounds Using Directional Derivatives, Increasing the output length of zero-error dispersers, Extracting randomness: A survey and new constructions, Universal tests for nonuniform distributions, Non-malleability against polynomial tampering, Cancellation-free circuits in unbounded and bounded depth, The Many Entropies in One-Way Functions
