Computer Science/Discrete Mathematics Seminar II

In this talk, I will begin with a quick primer to parameterized complexity, present some key insights from recent hardness of approximation results in the area, and end with a proof sketch of the following result: Assuming 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 those where every assignment satisfies at most 1% of the constraints.