Non-Black-Box Worst-Case to Average-Case Reductions Within $\mathsf{NP}$

Cryptography (94A60) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

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
The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
Language compression and pseudorandom generators
$BPP$ has subexponential time simulations unless $EXPTIME$ has publishable proofs
Hardness vs randomness
Decoding of Reed Solomon codes beyond the error-correction bound
On the limits of nonapproximability of lattice problems
Randomness vs time: Derandomization under a uniform assumption
Complexity theory. Abstracts from the workshop held November 15--21, 2015
Some results on derandomization
Zero knowledge and circuit minimization
The minimum oracle circuit size problem
Lossless condensers, unbalanced expanders, and extractors
Pseudorandomness and average-case complexity via uniform reductions
If NP languages are hard on the worst-case, then it is easy to find their hard instances
Natural Proofs versus Derandomization
Tensor-based Hardness of the Shortest Vector Problem to within Almost Polynomial Factors
On basing one-way functions on NP-hardness
Algebrization
Random-Self-Reducibility of Complete Sets
Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
Minimum Circuit Size, Graph Isomorphism, and Related Problems
Circuit minimization problem
On the Complexity of Learning Minimum Time-Bounded Turing Machines
Lattice problems in NP ∩ coNP
Relations between average case complexity and approximation complexity
Minimizing Disjunctive Normal Form Formulas and $AC^0$ Circuits Given a Truth Table
Average Case Complete Problems
Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
A Pseudorandom Generator from any One-way Function
Foundations of Cryptography
A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms
New Insights on the (Non-)Hardness of Circuit Minimization and Related Problems
On Basing Size-Verifiable One-Way Functions on NP-Hardness
On the NP-Completeness of the Minimum Circuit Size Problem.
Learning algorithms from natural proofs
Extractors and pseudorandom generators
Worst‐Case to Average‐Case Reductions Based on Gaussian Measures
Power from Random Strings
On Worst‐Case to Average‐Case Reductions for NP Problems
An Unconditional Study of Computational Zero Knowledge
Natural proofs
Extracting all the randomness and reducing the error in Trevisan's extractors
Pseudorandom generators without the XOR lemma
Average-case hardness of NP from exponential worst-case hardness assumptions

This page was built for publication: Non-Black-Box Worst-Case to Average-Case Reductions Within $\mathsf{NP}$

Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\)