Weak derandomization of weak algorithms: explicit versions of Yao's lemma
From MaRDI portal
Publication:451107
DOI10.1007/s00037-011-0006-4zbMath1252.68127OpenAlexW2174440985WikidataQ124833657 ScholiaQ124833657MaRDI QIDQ451107
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
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
