Weak derandomization of weak algorithms: explicit versions of Yao's lemma
From MaRDI portal
Publication:451107
DOI10.1007/S00037-011-0006-4zbMATH Open1252.68127OpenAlexW2174440985WikidataQ124833657 ScholiaQ124833657MaRDI QIDQ451107FDOQ451107
Authors: 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
Recommendations
Randomized algorithms (68W20) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cites Work
- The space complexity of approximating the frequency moments
- Hardness vs randomness
- Undirected connectivity in log-space
- How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
- Communication Complexity
- Generating quasi-random sequences from semi-random sources
- Pseudorandomness for network algorithms
- Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
- CREW PRAM<scp>s</scp> and Decision Trees
- Strong communication complexity or generating quasi-random sequences from two communicating semi-random sources
- \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
- Randomness vs time: Derandomization under a uniform assumption
- Pseudorandomness and average-case complexity via uniform reductions
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- Derandomizing polynomial identity tests means proving circuit lower bounds
- Pseudorandom generators without the XOR lemma
- Randomness is linear in space
- Complexity measures and decision tree complexity: a survey.
- MORE ON THE SUM-PRODUCT PHENOMENON IN PRIME FIELDS AND ITS APPLICATIONS
- Private vs. common random bits in communication complexity
- Extractors and rank extractors for polynomial sources
- Title not available (Why is that?)
- Pseudorandom generators for space-bounded computation
- On recycling the randomness of states in space bounded computation
- Pseudorandom Generators and Typically-Correct Derandomization
- Title not available (Why is that?)
- Title not available (Why is that?)
- Extracting randomness: A survey and new constructions
- Can every randomized algorithm be derandomized?
- Title not available (Why is that?)
- Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators
- Title not available (Why is that?)
- 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
Cited In (10)
- Pseudorandom generators, typically-correct derandomization, and circuit lower bounds
- Improved Extractors for Recognizable and Algebraic Sources
- Incompressible functions, relative-error extractors, and the power of nondeterministic reductions
- Title not available (Why is that?)
- Exposure-resilient extractors and the derandomization of probabilistic sublinear time
- (Nondeterministic) hardness vs. non-malleability
- Amplification and Derandomization without Slowdown
- On derandomizing Yao's weak-to-strong OWF construction
- Typically-correct derandomization for small time and space
- An Introduction to Randomness Extractors
This page was built for publication: Weak derandomization of weak algorithms: explicit versions of Yao's lemma
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q451107)
