Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization

Cites Work

Computational Complexity
$\Sigma_ 1^ 1$-formulae on finite structures
Hardness vs randomness
Proof verification and the hardness of approximation problems
Probabilistic checking of proofs
Algorithmic polynomials
Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
Cryptography in constant parallel time
Linear-time encodable and decodable error-correcting codes
Computational Complexity
Boolean function complexity. Advances and frontiers.
Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
On the Power of Small-Depth Computation
One way functions and pseudorandom generators
Majority gates vs. general weighted threshold gates
Parity, circuits, and the polynomial-time hierarchy
Computing Partitions with Applications to the Knapsack Problem
Bounded-width polynomial-size branching programs recognize exactly those languages in $NC^ 1$
Threshold circuits of bounded depth
Separating Nondeterministic Time Complexity Classes
Pseudorandomness and average-case complexity via uniform reductions
The Complexity of Local List Decoding
Simple extractors for all min-entropies and a new pseudorandom generator
Hardness Amplification Proofs Require Majority
Natural proofs
Pseudorandom generators without the XOR lemma
Cryptography in $NC^0$
Title not available (Why is that?)
Algebrization
Title not available (Why is that?)
In search of an easy witness: Exponential time vs. probabilistic polynomial time.
Algebraic methods for interactive proof systems
IP = PSPACE
Uniform constant-depth threshold circuits for division and iterated multiplication.
Short PCPs with Projection Queries
Extractors and pseudorandom generators
A Turing machine time hierarchy
On approximate majority and probabilistic time
Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized
Improving exhaustive search implies superpolynomial lower bounds
Nonuniform ACC Circuit Lower Bounds
Verifying and decoding in constant depth
Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQP
A polynomial restriction lemma with applications
Random oracles separate PSPACE from the polynomial-time hierarchy
New algorithms and lower bounds for circuits with linear threshold gates
Exploring crypto dark matter: new simple PRF candidates and their applications
Garbled Circuits as Randomized Encodings of Functions: a Primer
Natural proofs versus derandomization
Circuit Lower Bounds for Merlin–Arthur Classes
The polynomial method strikes back: tight quantum query bounds via dual polynomials
Pseudorandom Generators from the Second Fourier Level and Applications to AC0 with Parity Gates
Average-case rigidity lower bounds
A \#SAT algorithm for small constant-depth circuits with PTF gates
An average-case lower bound against $\mathsf{ACC}^0$
Title not available (Why is that?)
Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity
Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of #SAT Algorithms.
Inverse-exponential correlation bounds and extremely rigid matrices from a new derandomized XOR lemma
Title not available (Why is that?)
Title not available (Why is that?)

Cited In (6)

Robustness of average-case meta-complexity via pseudorandomness
Improved bounds for quantified derandomization of constant-depth circuits and polynomials
Paradigms for Unconditional Pseudorandom Generators
The value of help bits in randomized and average-case complexity
Depth-$d$ threshold circuits vs. depth-$(d+1)$ and-or trees
Range avoidance, remote point, and hard partial truth table via satisfying-pairs algorithms

This page was built for publication: Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization

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