Hardness self-amplification: simplified, optimized, and unified

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Optimal detection of sparse principal components in high dimension
Chernoff-type direct product theorems
Highly resilient correctors for polynomials
Self-testing/correcting with applications to numerical problems
Randomness in interactive proofs
Expected complexity of graph partitioning problems
On the hardness of computing the permanent of random matrices
Hiding cliques for cryptographic security
Sparse CCA: adaptive estimation and computational barriers
On the Bogolyubov-Ruzsa lemma
On hardness of several string indexing problems
Computational barriers in minimax submatrix detection
Public-key cryptography from different assumptions
Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture
Hidden Cliques and the Certification of the Restricted Isometry Property
How Hard Is It to Approximate the Best Nash Equilibrium?
On Yao’s XOR-Lemma
A Sample of Samplers: A Computational Perspective on Sampling
How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
Approximate List-Decoding of Direct Product Codes and Uniform Hardness Amplification
Large Cliques Elude the Metropolis Process
Counting Walks and Graph Homomorphisms via Markov Chains and Importance Sampling
A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem
Average-case fine-grained hardness
Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication
The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs
Hardness Amplification Proofs Require Majority
Using Nondeterminism to Amplify Hardness
Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
On Worst‐Case to Average‐Case Reductions for NP Problems
List-Decoding with Double Samplers
Hardness Amplification of Optimization Problems
Hardness amplification within NP

This page was built for publication: Hardness self-amplification: simplified, optimized, and unified