Speaker: Karthik C.S (Rutgers University)

Title: Extremal Combinatorial Objects in Hardness of Approximation in P

Abstract: In the last decade, the area of hardness of approximation for problems solvable in polynomial time has emerged. One of the popular frameworks for proving such results is called threshold graph composition and relies on the existence and efficient construction of non-trivial extremal combinatorial objects.

In this talk, we shall focus on defining and constructing these extremal objects while briefly outlining their applications to hardness of approximation in P.
 

https://math.mit.edu/combin/