LECTURES A GRATIS GLOBAL SERVICE
⌕ SEARCH GRATIS GLOBAL ↗
LECTURES
Algorithms for Solving Random and Semirandom Planted Constraint Satisfaction Problems
SOURCE: YOUTUBE · NO TRACKING UNTIL YOU PRESS PLAY · TROUBLE PLAYING? WATCH AT THE SOURCE ↗

Algorithms for Solving Random and Semirandom Planted Constraint Satisfaction Problems

125 MIN · EN · STATUS: [ STREAMING ]
RATE THIS
IAS

Peter Manohar of the Institute for Advanced Study presents new algorithmic results for random and semirandom planted constraint satisfaction problems. Random CSPs are built by first fixing a solution and then sampling constraints it satisfies, while semirandom CSPs mix worst-case, NP-hard structure with average-case randomness. Manohar walks through algorithms that solve both settings, then connects the techniques to noisy k-sparse linear equations over F_2, equivalent to the sparse Learning Parity with Noise problem used in cryptography. The talk draws on joint work with Arpon Basu, Venkatesan Guruswami, Jun-Ting Hsieh, Pravesh K. Kothari, and Andrew D. Lin, delivered as part of the IAS Computer Science/Discrete Mathematics Seminar II. It is a technical research seminar aimed at an audience already versed in constraint satisfaction and complexity theory, covering the problem setup, the algorithmic ideas, and their cryptographic implications in detail.

At a glance

Lecture facts

Runtime compared with the other 507 Mathematics lectures
Runtime2 h 5 m
Compared with MathematicsLonger than 98%
Source channelInstitute for Advanced Study (YouTube)