When: Sunday, March 21, 10am
Where: Schreiber 309
Speaker: Karthik C. S., NYU
Title: Extremal Combinatorial Objects in Hardness of Approximation in P
In recent years, the area of hardness of approximation for problems solvable in polynomial time has emerged. A prototypical result in this area is the following: given n points in high dimension, if no algorithm can find the (exact) closest pair of points in n^{1.99} time then no algorithm can even compute an approximate closest pair in O(n^{1.99}) time. Most of the machinery developed to prove such inapproximability results rely on the existence and efficient construction of highly 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.
Furthermore, we motivate the talk via the following concrete result: given a graph G, its inner product dimension
(IP(G)) is defined to be the smallest dimension d such that we can realize every vertex of G as a point in
d-dimensional Euclidean space and the following holds. For every pair of vertices sharing an edge, the
corresponding pair of points have inner product to be exactly equal to 1 and for every pair of vertices not
sharing an edge, the corresponding pair of points have inner product less than 0.99. It is known that for a random
graph G on n vertices, IP(G) is at least n/15 w.h.p. In this talk, we shall construct a class of dense bipartite
graphs G* for which IP(G*) is polylog(n).