Weak derandomization of weak algorithms: explicit versions of Yao's lemma
From MaRDI portal
Recommendations
Cites work
- scientific article; zbMATH DE number 1820017 (Why is no real title available?)
- scientific article; zbMATH DE number 1820025 (Why is no real title available?)
- scientific article; zbMATH DE number 549850 (Why is no real title available?)
- scientific article; zbMATH DE number 1097580 (Why is no real title available?)
- scientific article; zbMATH DE number 2019636 (Why is no real title available?)
- scientific article; zbMATH DE number 1559537 (Why is no real title available?)
- scientific article; zbMATH DE number 1857655 (Why is no real title available?)
- scientific article; zbMATH DE number 1445300 (Why is no real title available?)
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators
- CREW PRAM<scp>s</scp> and Decision Trees
- Can every randomized algorithm be derandomized?
- Communication Complexity
- Complexity measures and decision tree complexity: a survey.
- Cryptography and Coding
- Derandomizing polynomial identity tests means proving circuit lower bounds
- 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
- Extracting randomness: A survey and new constructions
- Extractors and rank extractors for polynomial sources
- Generating quasi-random sequences from semi-random sources
- Hardness vs randomness
- How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
- MORE ON THE SUM-PRODUCT PHENOMENON IN PRIME FIELDS AND ITS APPLICATIONS
- On recycling the randomness of states in space bounded computation
- Private vs. common random bits in communication complexity
- Pseudo-random generators for all hardnesses
- Pseudorandom Generators and Typically-Correct Derandomization
- Pseudorandom generators for space-bounded computation
- Pseudorandom generators without the XOR lemma
- Pseudorandomness and average-case complexity via uniform reductions
- Pseudorandomness for network algorithms
- Randomness is linear in space
- Randomness vs time: Derandomization under a uniform assumption
- Strong communication complexity or generating quasi-random sequences from two communicating semi-random sources
- The space complexity of approximating the frequency moments
- Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
- Undirected connectivity in log-space
- \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
Cited in
(10)- Pseudorandom generators, typically-correct derandomization, and circuit lower bounds
- Amplification and Derandomization without Slowdown
- An introduction to randomness extractors
- Improved Extractors for Recognizable and Algebraic Sources
- Incompressible functions, relative-error extractors, and the power of nondeterministic reductions
- Fine-grained derandomization: from problem-centric to resource-centric complexity
- On derandomizing Yao's weak-to-strong OWF construction
- Exposure-resilient extractors and the derandomization of probabilistic sublinear time
- Typically-correct derandomization for small time and space
- (Nondeterministic) hardness vs. non-malleability
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)
