Pseudorandom Self-Reductions for NP-Complete Problems

on YouTube ↗13m

" summary

Claim: non-adaptive pseudorandom self-reduction for Max Clique (and every nontrivial hereditary max-subgraph problem) holds assuming the non-uniform planted clique conjecture. The reduction fixes a random set S of size n^ε, preserves edges inside S from the input and randomizes others, so a K-clique maps to roughly K / n^{1-ε} (with at most +3 log n noise) and the outputs are indistinguishable from uniform via an XOR-style argument; a distinguisher would violate the planted-clique hardness.

AI-written summary · about

" chapters (13)

1. 0:00Introduction
2. 0:50Discrete logarithm problem
3. 1:56Nonadaptive selfreduction
4. 2:43Pseudorandom self reduction
5. 3:32Pseudorandom self reduction for MSP
6. 4:00Pseudorandom reduction
7. 4:46MCSP
8. 5:40Pi
9. 6:02conjecture
10. 6:56reduction
11. 7:45properties
12. 9:16pseudonymous
13. 11:45general properties

" related talks

• 41mReducibility and Statistical-Computational Gaps from Secret LeakageGuy Bresler · Computational Phase Transitions (Simons Institute, 2020)
• 42mUsing the Planted Clique Conjecture for Cryptography: Public-Key Encryption from...Riddhi Ghosal · Obfuscation
• 29mOn Basing Auxiliary-Input Cryptography on NP-hardness via Nonadaptive Black-Box ReductionsMikito Nanashima · ITCS 2021
• 01h 01mDerandomization: A Quick TutorialLijie Chen · Minimal Complexity Assumptions for Cryptography 2023
• 44mCorrelation Intractability and SNARGs from Sub-exponential DDHZhengzhong Jin · Minimal Complexity Assumptions for Cryptography 2023
• 01h 06mHardness of the Shortest Vector Problem: A Simplified Proof and a SurveyHuck Bennett · Quantum and Lattices Joint Reunion Workshop
• 59mNew Reductions and Algorithms for Ideal Lattices via Arakelov Random WalksBenjamin Wesolowski, Léo Ducas · Lattices: Geometry, Algorithms and Hardness 2020
• 01h 13mA Zero-Knowledge PCP TheoremNicholas Spooner · Proofs (Simons Institute)