Algorithmic Decorrelation and Planted Clique in Dependent Random Graphs

Explore a technical lecture from MIT's Guy Bresler examining the computational relationships between Planted Clique problems and statistical challenges through average-case reductions. Delve into a novel framework for evaluating average-case reductions based on perturbation sensitivity, with specific focus on planted clique scenarios in dependent random graphs. Learn how triangle removal techniques can eliminate edge dependencies while maintaining clique properties in Erdos-Renyi graphs modified with random triangles. Understand the bidirectional nature of reductions between Planted Clique and other computational problems, demonstrating their fundamental equivalence. The collaborative research presented with Chenghao Guo and Yury Polyanskiy provides insights into algorithmic decorrelation methods and their applications in graph theory.