Weak derandomization of weak algorithms: explicit versions of Yao's lemma

DOI10.1007/s00037-011-0006-4zbMath1252.68127OpenAlexW2174440985WikidataQ124833657 ScholiaQ124833657MaRDI QIDQ451107

Ronen Shaltiel

Publication date: 21 September 2012

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.215.8356

zbMATH Keywords

circuit complexityderandomizationcommunication complexitypseudorandomnessrandomness extractors

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Randomized algorithms (68W20)

Related Items (8)

Incompressible functions, relative-error extractors, and the power of nondeterministic reductions ⋮ (Nondeterministic) hardness vs. non-malleability ⋮ Unnamed Item ⋮ Pseudorandom generators, typically-correct derandomization, and circuit lower bounds ⋮ Amplification and Derandomization without Slowdown ⋮ Improved Extractors for Recognizable and Algebraic Sources ⋮ An Introduction to Randomness Extractors ⋮ Typically-correct derandomization for small time and space

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Extractors and rank extractors for polynomial sources
• Generating quasi-random sequences from semi-random sources
• Strong communication complexity or generating quasi-random sequences from two communicating semi-random sources
• Private vs. common random bits in communication complexity
• Pseudorandom generators for space-bounded computation
• The space complexity of approximating the frequency moments
• Extracting randomness: A survey and new constructions
• \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
• Hardness vs randomness
• Randomness vs time: Derandomization under a uniform assumption
• Complexity measures and decision tree complexity: a survey.
• Randomness is linear in space
• Pseudorandomness and average-case complexity via uniform reductions
• Pseudorandomness for network algorithms
• On recycling the randomness of states in space bounded computation
• Can every randomized algorithm be derandomized?
• How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
• Undirected connectivity in log-space
• Pseudorandom Generators and Typically-Correct Derandomization
• Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
• CREW PRAM<scp>s</scp> and Decision Trees
• Communication Complexity
• Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• MORE ON THE SUM-PRODUCT PHENOMENON IN PRIME FIELDS AND ITS APPLICATIONS
• Deterministic Extractors for Bit‐Fixing Sources and Exposure‐Resilient Cryptography
• Deterministic Extractors for Bit‐Fixing Sources by Obtaining an Independent Seed
• Deterministic extractors for small-space sources
• Cryptography and Coding
• Pseudo-random generators for all hardnesses
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Pseudorandom generators without the XOR lemma

This page was built for publication: Weak derandomization of weak algorithms: explicit versions of Yao's lemma