- Threshold Graphs for Hardness of Approximation of Maximum Inner Product
- Project Year:
2025
- REU Student (s):
Reina Itakura | University of California-Davis CA
- Student 1 Institution:
University of California-Davis
- Project Mentor:
Karthik Srikanta
- Project Mentor Area:
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.
