Hardness Magnification for All Sparse NP Languages

Hardness Magnification for All Sparse NP Languages

Explore the concept of Hardness Magnification in computational complexity theory through this 21-minute IEEE conference talk. Delve into topics such as the Minimum Circuit Size Problem, extending known lower bounds, and Hardness Magnification for all sparse NP languages. Learn about algorithms with small non-uniformity, gain insights into the intuition behind these concepts, and understand the proof of Theorem 1.2. Conclude by examining open problems in the field, as presented by speakers Lijie Chen, Ce Jin, and Ryan Williams.