Quantified Derandomization: How to Find Water in the Ocean
From MaRDI portal
Publication:5060673
DOI10.1561/0400000108OpenAlexW4312983967MaRDI QIDQ5060673
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
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- DNF sparsification and a faster deterministic counting algorithm
- The sum of \(D\) small-bias generators fools polynomials of degree \(D\)
- On approximate majority and probabilistic time
- Pseudorandom bits for constant depth circuits
- Derandomizing Arthur-Merlin games using hitting sets
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- The complexity of computing symmetric functions using threshold circuits
- Approximating threshold circuits by rational functions
- Hardness vs randomness
- Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity
- The complexity of constructing pseudorandom generators from hard functions
- In search of an easy witness: Exponential time vs. probabilistic polynomial time.
- Fourier concentration from shrinkage
- Improved bounds for quantified derandomization of constant-depth circuits and polynomials
- Hilbert functions and the finite degree Zariski closure in finite field combinatorial geometry
- Lossless condensers, unbalanced expanders, and extractors
- Every linear threshold function has a low-weight approximator
- Improving Exhaustive Search Implies Superpolynomial Lower Bounds
- Improved Average-Case Lower Bounds for De Morgan Formula Size: Matching Worst-Case Lower Bound
- Reed–Muller Codes for Random Erasures and Errors
- Testers and their applications
- Pseudorandom Bits for Polynomials
- In a World of P=BPP
- Small-Bias Probability Spaces: Efficient Constructions and Applications
- Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
- Parity, circuits, and the polynomial-time hierarchy
- How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
- PP is as Hard as the Polynomial-Time Hierarchy
- Unbalanced expanders and randomness extractors from Parvaresh--Vardy codes
- Asymptotically Optimal Hitting Sets Against Polynomials
- Simple extractors for all min-entropies and a new pseudorandom generator
- Extractors
- Pseudorandom generators for low degree polynomials
- A Pseudorandom Generator from any One-way Function
- Size--Depth Tradeoffs for Threshold Circuits
- The Shrinkage Exponent of de Morgan Formulas is 2
- Simulating Threshold Circuits by Majority Circuits
- The effect of random restrictions on formula size
- Shrinkage of de Morgan formulae under restriction
- Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators
- Formula lower bounds via the quantum method
- Cubic Formula Size Lower Bounds Based on Compositions with Majority
- Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity
- Strong average-case lower bounds from non-trivial derandomization
- Sharp threshold results for computational complexity
- Short PCPs with Projection Queries
- On the Correlation of Parity and Small-Depth Circuits
- Randomness efficient identity testing of multivariate polynomials
- Bootstrapping results for threshold circuits “just beyond” known lower bounds
- Quantified derandomization of linear threshold circuits
- Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQP
- On derandomizing algorithms that err extremely rarely
- Weight Distribution and List-Decoding Size of Reed–Muller Codes
- Computational Complexity
- Average-case lower bounds and satisfiability algorithms for small threshold circuits
- Bounded Independence Fools Halfspaces
- Extensions to the Method of Multiplicities, with Applications to Kakeya Sets and Mergers
- Extractors and pseudorandom generators
- Average-case lower bounds for formula size
- Computational Complexity
- Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
- Derandomizing polynomial identity tests means proving circuit lower bounds
- Extracting all the randomness and reducing the error in Trevisan's extractors
- Pseudo-random generators for all hardnesses
- Pseudorandom generators without the XOR lemma
This page was built for publication: Quantified Derandomization: How to Find Water in the Ocean
