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 optimal conditional time lower bounds under ETH for parameterized k-biclique problem. Even better, prove total FPT inapproximability of the problem.
  6. Prove the total FPT inapproximability of parameterized k-set cover problem assuming W[2] is not contained in FPT.
  7. Construct a subquadratic-time self-reduction from exact bichromatic Max-IP on n Boolean vectors in O(log3 n) dimensions to constant-gap bichromatic Max-IP on n1+o(1) Boolean vectors in polylog(n) dimensions.
  8. Prove that parameterized k-clique is W[1]-hard to approximate to √k factor. Even better, prove total FPT inapproximability of the problem assuming W[1] is not contained in FPT.
  9. Disprove that SETH can imply Gap-SETH via a polynomial-time Karp reduction.
  10. Prove that ETH implies Gap-ETH.