Home
Publications
Communications
Students
Teaching
NYC Food
Visiting Bangalore

Karthik C. S.

Below is a list of open problems that I care about (in no particular order). If an AI model correctly solves any of them in the future, I would be very grateful to be informed, so that I can digest and help communicate the result if needed.

  1. Prove the Parameterized Inapproximability Hypothesis (PIH): it is W[1]-hard to decide Gap-2-CSP parameterized by the number of variables.
  2. Prove or disprove conditional subquadratic lower bounds for some constant-factor approximation of the Euclidean Closest Pair problem.
  3. Prove optimal conditional time lower bounds for 2-CSPs on constant-degree constraint graphs, parameterized by the number of variables.
  4. Determine the optimal polynomial-time approximation factor for Euclidean k-center, for any of the three variants of the problem.
  5. Prove that ETH implies Gap-ETH.