Quantified Derandomization: How to Find Water in the Ocean

DOI10.1561/0400000108OpenAlexW4312983967MaRDI QIDQ5060673FDOQ5060673

Authors: Roei Tell 

Publication date: 11 January 2023

Published in: Foundations and Trends® in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1561/0400000108

Recommendations

• On derandomizing algorithms that err extremely rarely
• Improved bounds for quantified derandomization of constant-depth circuits and polynomials
• Improved bounds for quantified derandomization of constant-depth circuits and polynomials
• scientific article; zbMATH DE number 1789922
• Can every randomized algorithm be derandomized?

zbMATH Keywords

computational complexityrandomness in computation

Mathematics Subject Classification ID

Computer science (68-XX)

Cites Work

• Computational Complexity
• \(\Sigma_ 1^ 1\)-formulae on finite structures
• Hardness vs randomness
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
• A Pseudorandom Generator from any One-way Function
• Size--Depth Tradeoffs for Threshold Circuits
• Derandomizing Arthur-Merlin games using hitting sets
• How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
• Computational Complexity
• Computational analogues of entropy
• Parity, circuits, and the polynomial-time hierarchy
• Pseudorandom bits for constant depth circuits
• The complexity of constructing pseudorandom generators from hard functions
• PP is as Hard as the Polynomial-Time Hierarchy
• Simple extractors for all min-entropies and a new pseudorandom generator
• Title not available (Why is that?)
• Weight Distribution and List-Decoding Size of Reed–Muller Codes
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Pseudorandom generators without the XOR lemma
• Pseudorandom bits for polynomials
• Bounded Independence Fools Halfspaces
• Unconditional pseudorandom generators for low degree polynomials
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Shrinkage Exponent of de Morgan Formulas is 2
• The effect of random restrictions on formula size
• Shrinkage of de Morgan formulae under restriction
• Average-case lower bounds for formula size
• The sum of \(D\) small-bias generators fools polynomials of degree \(D\)
• Fourier concentration from shrinkage
• DNF sparsification and a faster deterministic counting algorithm
• In search of an easy witness: Exponential time vs. probabilistic polynomial time.
• Approximating threshold circuits by rational functions
• Every linear threshold function has a low-weight approximator
• Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes
• Simulating Threshold Circuits by Majority Circuits
• Randomness efficient identity testing of multivariate polynomials
• Title not available (Why is that?)
• In a world of \(\mathrm{P}=\mathrm{BPP}\)
• Pseudorandom generators for low degree polynomials
• Pseudo-random generators for all hardnesses
• Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators
• Title not available (Why is that?)
• Lossless condensers, unbalanced expanders, and extractors
• Short PCPs with projection queries
• Extractors and pseudorandom generators
• On approximate majority and probabilistic time
• Extensions to the method of multiplicities, with applications to Kakeya sets and mergers
• Extractors
• Title not available (Why is that?)
• Title not available (Why is that?)
• Improving exhaustive search implies superpolynomial lower bounds
• Asymptotically Optimal Hitting Sets Against Polynomials
• Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity
• Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQP
• Title not available (Why is that?)
• Extracting all the randomness and reducing the error in Trevisan's extractors
• The complexity of computing symmetric functions using threshold circuits
• Improved average-case lower bounds for De Morgan formula size: matching worst-case lower bound
• Testers and their applications
• On the Correlation of Parity and Small-Depth Circuits
• Average-case lower bounds and satisfiability algorithms for small threshold circuits
• Hilbert functions and the finite degree Zariski closure in finite field combinatorial geometry
• Formula lower bounds via the quantum method
• Title not available (Why is that?)
• Strong average-case lower bounds from non-trivial derandomization
• Reed–Muller Codes for Random Erasures and Errors
• Improved bounds for quantified derandomization of constant-depth circuits and polynomials
• Satisfiability and derandomization for small polynomial threshold circuits
• Luby-Veličković-Wigderson revisited: improved correlation bounds and pseudorandom generators for depth-two circuits
• Sharp threshold results for computational complexity
• Bootstrapping results for threshold circuits ``just beyond known lower bounds
• Quantified derandomization of linear threshold circuits
• On derandomizing algorithms that err extremely rarely
• Tight bounds on the Fourier spectrum of \(\mathsf{AC}^0\)
• Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity
• Algorithms for circuits and circuits for algorithms: connecting the tractable and intractable
• Cubic Formula Size Lower Bounds Based on Compositions with Majority
• Title not available (Why is that?)
• On randomness extraction in \({\mathcal{AC}}^0\)
• Small bias requires large formulas

Cited In (2)

• On hitting-set generators for polynomials that vanish rarely
• When Arthur has neither random coins nor time to spare: superfast derandomization of proof systems

This page was built for publication: Quantified Derandomization: How to Find Water in the Ocean

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5060673)