General Information
| Student: | Gary Peng |
|---|---|
| Office: | Computing Research and Education Building (CoRE), Room 442 96 Frelinghuysen Road, Piscataway, 08854-8018 |
| School: | University of Maryland |
| E-mail: | gpeng1 [at] terpmail [dot] umd [dot] edu |
| Project: | Inapproximability of \(k\)-Clique |
About Me
I am a rising senior at the University of Maryland studying computer science and mathematics. I am broadly interested in theoretical computer science, but I am especially interested in algorithms, complexity theory, and economics and computation. Outside of research, I enjoy playing board games, playing sports (casually), and spending time with friends and family.
Project Description
In the \(k\)-clique problem, we are asked whether there exists a clique of \(k\) vertices in a graph \(G.\) \(k\)-clique is a fundamental problem in the theories of NP-completeness, fixed-parameter tractability, and fine-grained complexity, and our research group will be studying the hardness of approximating \(k\)-clique.
I am very fortunate to be advised by my mentors Karthik C.S. and Mursalin Habib and to work with my groupmates Reina Itakura and Mayank Motwani.
Weekly Log
- Week 1: First Week
-
I moved in to Buell Apartments, and met my roommates, groupmates, and the other students at DIMACS REU. On Friday, we had lunch with Karthik and talked about possible research directions. We discussed important background (e.g., the FGLSS reduction and label-extended graphs) and completed an exercise together where rephrased the self-reduction from \((k, k - 1)\)-gap clique to \((q^k, k \cdot q^{k - 1})\)-gap clique in Chen et al. [SOSA'25] in terms of constraint-satisfication problems (CSPs). Karthik also brainstormed 7 possible research directions for us to pursue! After the meeting, Reina and I began to work on an overview of our research that we will present next Tuesday.
In the evenings, we played board games (I won Coup 3/5 times) and soccer, which was fun.
- Week 2: The PCP Theorem
-
This week felt rather slow. I spent most of my time trying to read and understand Dinur's proof the PCP Theorem, since one of the 7 research directions (see above) is related to this. We also had two meetings this week. On Tuesday, we met with Mursalin, who suggested that we read Lin et al. [FOCS'23], which seems relevant to our goal of abstracting the reduction in Chen et al. [SOSA'25] in terms of locally-decodable codes (LDCs). The next day, we met with Karthik, and Reina presented the proof of Lemma 3.3 in Lin [SODA'15], which uses threshold graphs to prove the W[1]-hardness of \(k\)-biclique. After the meeting, Reina, Mayank, and I got boba :)
- Week 3: Abstracting the Self-Reduction
-
Since we are now three weeks in, I thought it would be good to summarize my 2 current research directions:
- Abstract the reduction in Chen et al. [SOSA'25] in terms of LDCs. Motivation: After identifying the assumptions on the LDC needed for the reduction to hold, we can substitute in specific LDCs to try to improve the inapproximability gap.
- Simplify Dinur's proof of the PCP Theorem to prove inapproximability of \(k\)-clique. Motivation: Currently, all that we know about the inapproximability of \(k\)-clique in the NP world comes from the FGLSS reduction. Can we show inapproximabiliy directly, without first going through CSPs?
On Saturday, we did an escape room and escaped with 54 seconds left!
- Week 4: PCP Theorem for \(k\)-clique: Degree Reduction
-
This week, I mainly worked on the second research direction (see above). In fact, I think I will be focusing on this research direction for the foreseeable future.
On Monday, I reviewed some relevant exercises from our first meeting with Karthik and was able to understand them much better with the help of Mayank (thanks!).
On Tuesday, I proved my first (albeit minor) result of the REU: Let \(G = (V, E, \Sigma, C)\) be a CSP, and let \(G' = (V', E', \Sigma, C')\) be the CSP obtained from the degree-reduction step of Dinur's proof, except that we use a weak notion of vertex expanders instead of edge expanders. Then, the clique gap of \(\Phi(G')\) is at least a constant fraction of the clique gap of \(\Phi(G)\), where \(\Phi(G)\) and \(\Phi(G')\) are the label-extended graphs of \(G\) and \(G'\), respectively. Importantly, this constant depends on the average degree of \(G\), so if we want to adapt Dinur's proof for \(k\)-clique, we will have to make sure that the average degree of the CSP doesn't increase too much throughout the process.
On Wednesday, we met with Karthik and Mursalin. Afterwards, Reina, Mayank, and I browsed a Barnes & Noble and got froyo.
For the rest of the week, I began to think about how to modify Dinur's graph-powering step for \(k\)-clique.
- Week 5: PCP Theorem for \(k\)-clique: Graph Powering
-
This week, I was able to complete the proof of the following theorem: Let \(G = (V, E, \Sigma, C)\) be CSP, where \(G\) is a weak vertex expander. If we apply a modified version of Dinur's graph-powering operation with parameter \(t\) to \(G\) to obtain a new CSP \(G^t = (V, E', \Sigma', C')\), then the clique gap of \(\Phi(G^t)\) is larger than that of \(\Phi(G)\) by a constant factor that grows exponentially with \(t\).
For the rest of the week, I began to work on modifying Dinur's alphabet-reduction step for \(k\)-clique. The following is some intuition I gained about this part of her proof: Let \(G = (V, E, \Sigma, C)\) be a \(2\)-ary CSP over a large (but constant-sized) alphabet. One natural way to reduce the alphabet size is to encode each \(a \in \Sigma\) using \(\ell = O(\log |\Sigma|)\) bits and to think of \(G\) as an \((2\ell)\)-ary CSP over a binary alphabet. However, we want to work with \(2\)-ary CSPs, not \((2\ell)\)-ary CSPs. In \(2\)-ary CSPs, we only need to look at \(2\) variables to check if a given constraint is satisfied, but if we think of \(G\) as an \((2\ell)\)-ary CSP, we now have to look at \(2\ell\) variables to do this. To get around this, Dinur uses an assignment tester \(\mathcal{P}\) to reduce the number of queries from \(2\ell\) back down to \(2\). More precisely, given a candidate satisfying assignment for an \(2\ell\)-ary constraint along with a proof, \(\mathcal{P}\) only needs to query \(2\) bits in total, across both the assignment and the proof, to check if the assignment satisfies the constraint, albeit at the cost of some loss in the soundness.
I have been thinking about how to do something along these lines for \(k\)-clique, but have not been able to make much progress yet.