A Survey on MCSP

on YouTube ↗01h 08m

" summary

Defines MCSP and variants (decision, search, optimization, approximate) and frames the core open: is MCSP NP‑hard or in P. Shows the explicit construction obstacle blocking standard reductions and rules out many local reductions; gives a positive NP‑completeness and approximation story for DNF → set cover instances. Connects MCSP average‑case complexity to natural proofs and cryptographic one‑way functions, links average‑case easiness to learnability, and records modest unconditional lower bounds (not AC0, quadratic formula bounds) with stronger bounds still open.

AI-written summary · about

" chapters (7)

1. 0:00Start
2. 0:46What Is Mcsp
3. 12:33Explicit Constructions
4. 21:34Np-Hardness Reductions
5. 25:53Local Reductions
6. 26:09The Local Reduction
7. 30:55What's the Complexity of Mcsp

" related talks

• 37mMutual Empowerment Between Circuit Obfuscation and Circuit MinimizationIlya Volkovich · Minimal Complexity Assumptions for Cryptography 2023
• 45mNP-Hardness of Approximating Meta-Complexity: A Cryptographic ApproachRahul Ilango · Lower Bounds, Learning, and Average-Case Complexity
• 51mWhat Can and What Cannot Be Done by LP and SDP (An Incomplete Overview)Alexander Barg · Advances in the Theory of Error-Correcting Codes
• 32mThe Computational Benefit of Correlated InstancesShafi Goldwasser · KARPfest80
• 01h 03mComplexity of Lattice ProblemsNoah Stephens-Davidowitz · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020
• 47mMCSat Approaches for Solving Non-linear Modular ArithmeticDaniela Kaufmann · Satisfiability: Theory, Practice, and Beyond 2023
• 46mNP-Hardness of Approximating Meta-Complexity: A Cryptographic ApproachHanlin Ren · Minimal Complexity Assumptions for Cryptography 2023
• 01h 08mTutorial on Proof SystemsAbhishek Jain · Minimal Complexity Assumptions for Cryptography 2023