Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization

Recommendations

An average-case lower bound against $\mathsf{ACC}^0$
Quantified derandomization of linear threshold circuits
Nonuniform ACC circuit lower bounds
Circuit lower bounds for nondeterministic quasi-polytime from a new easy witness lemma
Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQP

Cites work

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

Cited in

(9)

Improved bounds for quantified derandomization of constant-depth circuits and polynomials
Robustness of average-case meta-complexity via pseudorandomness
Paradigms for Unconditional Pseudorandom Generators
The value of help bits in randomized and average-case complexity
A technique for hardness amplification against AC^0
Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity
Depth-$d$ threshold circuits vs. depth-$(d+1)$ and-or trees
Range avoidance, remote point, and hard partial truth table via satisfying-pairs algorithms
Nondeterministic quasi-polynomial time is average-case hard for \textsf{ACC} circuits

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)