Coursera Flash Sale
40% Off Coursera Plus for 3 Months!
Grab it
Explore the intersection of parameterized complexity and hardness of approximation in this comprehensive seminar lecture. Begin with a foundational primer on parameterized complexity theory before delving into recent breakthrough results in hardness of approximation within this framework. Examine key insights from cutting-edge research and follow a detailed proof sketch demonstrating that, under the Exponential Time Hypothesis, no n^{k / polylog k}-time algorithm can distinguish between perfectly satisfiable 2-CSP instances on k variables over an alphabet of size n and instances where every assignment satisfies at most 1% of the constraints. Learn how classical Probabilistically Checkable Proofs (PCPs) extend to parallel PCPs and their implications for computational complexity theory. Gain deep understanding of the mathematical foundations underlying these hardness results and their significance for algorithm design in parameterized settings.
