- Hardness of Approximation for Clique
- Project Year:
2025
- REU Student (s):
Gary Peng | University of Maryland-College Park MD
- Student 1 Institution:
University of Maryland-College Park
- Project Mentor:
Karthik Srikanta
- Project Mentor Area:
Computer Science
- Project Abstract:
We present a simple proof that any constant-approximation for clique requires (n^{Omega(log n)}) time under the Exponential Time Hypothesis. In particular, our proof avoids the highly non-trivial PCP Theorem, the foundation for all known hardness-of-approximation results for clique at the time of writing.
