dimacs logo color

REU

REU Project

  • Threshold Graphs for Hardness of Approximation of Maximum Inner Product
  • Project Year: 2025
  • REU Student (s):   Reina Itakura | University of California-Davis CA  
  • Project Mentor (s) : Karthik Srikanta - Computer Science
  • Project Abstract: We consider the problem of approximate Maximum Inner Product (MaxIP). While inapproximability results for high dimensions exist using Distributed PCP, this problem has not been well-studied when the dimension is small--particularly d = O(log n). In this paper, we study the application of threshold graphs for hardness of approximation of MaxIP. Specifically, we describe a reduction that would follow through if a threshold graph did exist, and then explore a potential workaround. Additionally, we discuss applications of the same threshold graph to the problem in the Hitting Set Conjecture, and future directions for this problem.