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