Weak derandomization of weak algorithms: explicit versions of Yao's lemma
type: Item
instance of: scholarly article
title: Weak derandomization of weak algorithms: explicit versions of Yao's lemma
zbMATH Open document ID: 1252.68127
author: Ronen Shaltiel
published in: Computational Complexity
publication date: 2012-09-21T00:00:00Z
full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68W20
zbMATH DE Number: 6085137
zbMATH Keywords: derandomization
zbMATH Keywords: randomness extractors
zbMATH Keywords: pseudorandomness
zbMATH Keywords: communication complexity
zbMATH Keywords: circuit complexity
MaRDI profile type: Publication
OpenAlex ID: W2174440985
Wikidata QID: Q124833657
cites work: Q4287354
cites work: The space complexity of approximating the frequency moments
cites work: \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
cites work: How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
cites work: MORE ON THE SUM-PRODUCT PHENOMENON IN PRIME FIELDS AND ITS APPLICATIONS
cites work: Complexity measures and decision tree complexity: a survey.
cites work: Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
cites work: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
cites work: Extractors and rank extractors for polynomial sources
cites work: Q4952613
cites work: Deterministic Extractors for Bit‐Fixing Sources by Obtaining an Independent Seed
cites work: Q4440439
cites work: Can every randomized algorithm be derandomized?
cites work: Pseudorandomness for network algorithms
cites work: Q4526985
cites work: Randomness vs time: Derandomization under a uniform assumption
cites work: Q3152808
cites work: Derandomizing polynomial identity tests means proving circuit lower bounds
cites work: Deterministic extractors for small-space sources
cites work: Deterministic Extractors for Bit‐Fixing Sources and Exposure‐Resilient Cryptography
cites work: Pseudorandom Generators and Typically-Correct Derandomization
cites work: Cryptography and Coding
cites work: Communication Complexity
cites work: Q4788614
cites work: Private vs. common random bits in communication complexity
cites work: CREW PRAM<scp>s</scp> and Decision Trees
cites work: Pseudorandom generators for space-bounded computation
cites work: Extracting randomness: A survey and new constructions
cites work: Hardness vs randomness
cites work: Randomness is linear in space
cites work: Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators
cites work: On recycling the randomness of states in space bounded computation
cites work: Undirected connectivity in log-space
cites work: Generating quasi-random sequences from semi-random sources
cites work: Q3152800
cites work: Pseudorandom generators without the XOR lemma
cites work: Pseudorandomness and average-case complexity via uniform reductions
cites work: Pseudo-random generators for all hardnesses
cites work: Strong communication complexity or generating quasi-random sequences from two communicating semi-random sources
cites work: Q4372786
DOI: 10.1007/S00037-011-0006-4
description: scientific article; zbMATH DE number 6085137