- Hardness of Approximation for Clique
- Project Year:
2025
- REU Student (s):
Gary Peng | University of Maryland-College Park MD
- Project Mentor (s) :
Karthik Srikanta - 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.
