An Optimal Space Lower Bound for Approximating MAX-CUT

Learn about advanced algorithmic analysis through a research talk that demonstrates how extending beyond traditional KKL/hypercontractivity bounds enables tight analysis of the Implicit Hidden Partition (IHP) problem, ultimately establishing a definitive lower bound for streaming algorithm space complexity in MAX-CUT value approximation. Explore the application of Fourier analysis on boolean cubes as a framework for understanding information propagation in communication problems, presented in collaboration with Michael Kapralov at the Hausdorff Center for Mathematics.