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,\) where \(G\) and \(k\) are given. \(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 broadly 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:
-
I moved in to Buell Apartments, and met my roommates, groupmates, and the other students at DIMACS REU. On Friday, we met and had lunch with Karthik to dicuss possible research directions. (The meeting lasted from 10:15 to 4:30!) We discussed important background including the FGLSS reduction 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 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:
-
This week, I began reading Dinur's proof of the PCP Theorem, since one of the 7 possible research directions (see above) is related to this proof.
On Tuesday, we met with Mursalin, who suggested that we read Lin et al. [FOCS'23]. The paper seems relevant to our goal of abstracting the details of Chen et al. [SOSA'25] in terms of locally-decodable codes.