LECTURES A GRATIS GLOBAL SERVICE
⌕ SEARCH GRATIS GLOBAL ↗
LECTURES
From PCPs to Parallel PCPs: Hardness of Approximation in Parameterized Complexity
SOURCE: YOUTUBE · NO TRACKING UNTIL YOU PRESS PLAY · TROUBLE PLAYING? WATCH AT THE SOURCE ↗

From PCPs to Parallel PCPs: Hardness of Approximation in Parameterized Complexity

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

Karthik C. S. of Rutgers University presents a seminar on parameterized complexity and hardness of approximation, recorded as part of a Computer Science/Discrete Mathematics Seminar series. He opens with a primer on parameterized complexity before surveying recent results in hardness of approximation, building toward a proof sketch of a specific hardness theorem: assuming the Exponential Time Hypothesis, no algorithm running in n^(k/polylog k) time can distinguish perfectly satisfiable 2-CSP instances on k variables over an alphabet of size n from instances where every assignment satisfies at most 1 percent of the constraints. The talk traces the conceptual path from classical probabilistically checkable proofs (PCPs) to parallel PCP constructions that underlie these hardness results. Pitched at a technical seminar audience, it assumes familiarity with complexity theory and constraint satisfaction problems while walking through the key insights step by step.

At a glance

Lecture facts

Runtime compared with the other 734 Mathematics lectures
Runtime2 h 1 m
Compared with MathematicsLonger than 96%
Source channelInstitute for Advanced Study (YouTube)