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.

Intro
A puzzle
Sum of Squares (sos) Algorithm
sos-based Algorithms
Sum-of-squares Proof System
Example Cauchy Schwarz
Sos Algorithm Cartoon
Take Home Message
Low degree PRG'S
Breaking Degree 2 PRG'S
Matrix Recovery: Motivation
Tensor Recovery
Stepping Back
Sos Optimality Conjecture
Open Questions