On Optimal Algorithms and Assumption Factories

Explore optimal algorithms and assumption factories in this 50-minute presentation by Boaz Borak at the "Beyond Crypto: A TCS Perspective" event, affiliated with Crypto 2018. Delve into topics such as Sum of Squares (SOS) algorithms, SOS-based algorithms, and SOS proof systems. Examine practical examples like the Cauchy Schwarz theorem and learn about low-degree PRGs, matrix recovery, and tensor recovery. Gain insights into the SOS optimality conjecture and consider open questions in the field. Enhance your understanding of theoretical computer science concepts and their applications in cryptography.