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 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 clique problem, we are asked whether there exists a clique of \(k\) vertices in a graph \(G.\) 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 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, we 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 clique. Motivation: Currently, all that we know about the inapproximability of 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 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 Dinur's proof, except that we use a weak notion of vertex expanders instead of edge expanders. Then, the clique gap of \(\Psi(G')\) is at least a constant fraction of the clique gap of \(\Psi(G)\), where \(\Psi(G)\) and \(\Psi(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 the rest of Dinur's proof for 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, we 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 clique.
- Week 5: PCP Theorem for 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 \(\Psi(G^t)\) is larger than that of \(\Psi(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 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 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 clique, but have not been able to make much progress yet.
- Week 6: PCP Theorem for Clique: Alphabet Reduction
-
On Monday, we met with Karthik in New York City! After working in a coffee shop for a bit, we got lunch at John's of Bleecker Street, a pizzeria that has apparently been around since 1929. We were joined by Dr. Amir Abboud, who works in fine-grained complexity, and Karthik had each of us practice giving a short pitch about our research to Dr. Abboud. After lunch, we spent some time in Washington Square Park, where Karthik answered some questions we had about graduate school. We then got boba at Xing Fu Tang. We ended the day working in another coffee shop, where we were joined by Henry Fleischmann, one of Karthik's students from the 2022 DIMACS REU. We practiced our research pitches again and talked with Henry about graduate school and his experience at DIMACS REU. Overall, the trip to New York turned out to be a very memorable experience. I am especially grateful to Karthik for showing us around and generously buying us lunch and boba.
On Tuesday, I figured out how to adapt Dinur's alphabet-reduction step for clique. In particular, I showed that there exists \(\Sigma_0\), where \(|\Sigma_0|\) is a universal constant, such that given any CSP \(G = (V, E, \Sigma, C)\), we can construct a CSP \(G' = (V', E', \Sigma_0, C')\) that only loses \(1 / 2\) of the clique gap.
Now that I understand Dinur's proof at a deeper level, I guess I have enough background to aim for new results. In particular, Karthik suggested the following research directions:
- Adapt Dinur's proof to obtain a self-reduction for clique that incurs a smaller blow-up in the size of the problem instance than PCP + FGLSS.
- Find a one-shot self-reduction showing the hardness of approximating clique under the Exponential Time Hypothesis (ETH).
- Find a self-reduction showing the hardness of approximating clique that involves completely different ideas than those of Dinur's proof.
- Week 7: Hardness of Approximation for Clique Under ETH
-
This week, I found a simple proof that no polynomial-time constant approximation for clique exists under ETH. The proof is not too exciting, although it does bypass the PCP Theorem. I plan to focus on this result in my presentation next Wednesday.
- Week 8: Final Presentation and Final Report
-
I spent the first half of this week preparing for my presentation on Wednesday. After the presentation, I began to work on my final report, which will likely just be a write-up of a strengthened version of the result I presented on: By optimizing some paramemters in my reduction, I was able to show that any constant approximation for clique requires \(n^{\Omega(\log n)}\) time, under the Exponential Time Hypothesis.