Reina Itakura

DIMACS REU: Rutgers University, Summer 2025


`

About Me

I am an undergraduate computer science and mathematics student at UC Davis. I love graph theory and combinatorics. I also like all things algorithms, and have a recent interest in complexity theory. I enjoy (but am bad at) competitive programming. My account is ritakura1 on codeforces if you want to stalk me.

Project Description

The project I am working on is the Fine-Grained Complexity project. At this moment in time we are working on the k-clique problem and the hardness of approximating k-clique.
I am also working on constructing a threshold graph (described in [Lin'19]) but the construction of such a graph seems... uh...

Weekly Log

Day 0: Before the REU started my groupmates zoom-met Karthik and Mursalin like twice? I read some papers and did some background reading on LDCs.
Day 1: I arrived on Thursday (5.29.25), and attended the workshop at 11:00 am. Then Gary and Mayank caught me up to what they were working on. Right now we are stuck on generalizing the Sidon set construction in the k-clique paper to general LDCs. We are meeting Karthik tomorrow (5.30.25)! I am hoping we get to grab coffee or something since I think Karthik likes coffee. Mursalin is gone this week. I left the office at 6:30 pm.
Day 2: TGIF!! It's Friday!!! (I came in at 9:15 am). We met with Karthik at 10:15 a.m. We in fact did not get coffee but rather met in his office. I asked if we could meet in a coffee shop next time and he said yes. what a nice guy. I showed him my yo-yo. But this is not all we did. We went over the FGLSS reduction to go from a CSP to the label extension graph, and we were trying to kind of like short-cut the CSP part and see if we could get any nice things from going directly. (this already broke my brain). Then we talked about the 7 directions that we could go in. (details to be explained in presentation on Tuesday. check the slides, will be posted somehwere). Then we had lunch. which the CS department paid for. It was very yummy. I love curry and bread. Then we went back to work, and tried proving the paper section 5 but using the CSP stuff instead of how the paper analyzed it (same thing but different perspective). Then we probably did more stuff but as i said earlier my brain was fried and i can't remember the details. We left at around 4:28 pm. That's a lot of yapping! (we didn't yap, maybe I did a little). I need (want) to watch a series of videos now on PCP (out of order. jk.) so that'll be fun (maybe). Then we went back to our office, worked on our presentation and website, which is what i'm doing now. I will leave the office at 6:15 pm. I will go play board games at 6:30 hopefully. But i need trader joes frozen food first.
References:

  1. Yijia Chen, Yi Feng, Bundit Laekhanukit, and Yanlin Liu. 2023. Simple Combinatorial Construction of the o(1)-Lower Bound for Approximating the Parameterized k-Clique. CoRR abs/2304.07516 (2023). https://doi.org/10.48550/arXiv.2304.07516arXiv:2304.07516

  2. Lin, Bingkai. "The parameterized complexity of k-biclique." Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 2014..

Monday: I came in at 8:30, but didn't start work until 8:45. I pretty much spent the entire day reading the k-biclique paper (2). I left the office at around 6:10. Overall although I was in the office for a long time, I felt very unproductive.

Tuesday: I came in late at 9:20 ish. I spent my morning reading the PCP Theorem Proof (the 41 page one). Did not understand any of it. Today was the day of our presentation, which I will link below. Then I watched some of the PCP Theorem proof videos by O'Donnell before our meeting with Mursalin at 2:00. I feel like my first in-person meeting with Mursalin went pretty terribly (as in I was terrible, Mursalin was great). I was being dumb and idiotic pretty much the entire time + being sleepy from waking up so early. Note to REU students: it's a horrible idea to do the REU + school (I woke up early at 5:00 am to watch lectures for school work). But yeah... Then we got back to our office, and I'm working on my notes for presenting section 3 of the k-biclique paper which I have to present on tomorrow at 1 p.m. I'm so screwed... I haven't finished the notes but my brain is fried so here I am working on my website/log instead. If you can't tell I'm in doom mode rn. On a more positive note I gained like a million ducks. If anyone is reading this the culprit behind many of the duck-nappings are me. I felt bad for stealing so many ducks so I put three blue ones back. I don't intend on leaving the office until I finish my notes, and it's already 6:45 pm. wish me luck...
(Update 1): It's 8:05 pm, and my brain is completely fried. I still need to do the most important part of my notes but I NEED sugar and I am also hungry so I am going to go back to my dorm now. I'll probably leave the office at like 8:10. Will update once I finish notes.

Wednesday: I came in around 9:00 am. I in fact did not finish my notes yesterday, so spent most of the morning doing that. I also found out how to print stuff in the Student Center (thank you Andrew and Nadya)!! So I printed my notes. Our meeting with Karthik was at 1:00. As far as presenting papers go, I think I did pretty terribly, but on the bright side, the bar for doing "better" is extremely low now (but is it low enough? we'll find out). Karthik was pretty disapointed in the paper itself (and maybe also me but we'll never know) so he gave me a different problem to work on. We finished at like 3:15 and we (Gary, Mayank and I) had promised to get boba afterwards so we went to College Ave and got boba. It was ok.

Thursday: My update for today is that I have none. I spent my entire day studying for my ECS 222A final that I ended up not taking (a whole another story). Now I must skip out on NBA + Werewolf night to study some more for MAT 146 final (aka. GENERATING FUNCTIONS). TBH tho I really like this class so it's totally welcome. I suspect that I will not be doing much research tomorrow either... (I'm so sorry Karthik).

Slides: Hardness of Approximating k-clique
References:
  1. Yijia Chen, Yi Feng, Bundit Laekhanukit, and Yanlin Liu. 2023. Simple Combinatorial Construction of the o(1)-Lower Bound for Approximating the Parameterized k-Clique. CoRR abs/2304.07516 (2023). https://doi.org/10.48550/arXiv.2304.07516arXiv:2304.07516
  2. Bingkai Lin. The Parameterized Complexity of k-Biclique. 2019. arXiv: 1406. 3700 [cs.CC]. url: https://arxiv.org/abs/1406.3700.
  3. Lin, Bingkai, et al. "Improved hardness of approximating k-clique under ETH." 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2023.
  4. Irit Dinur. The PCP theorem by gap amplification. J. ACM, 54(3):12, 2007. (Preliminary Version in 38th STOC, 2006). doi:10.1145/1236457.1236459.

Acknowledgements

I would like to thank my mentor Karthik, his PhD student Mursalin, and my collaborators Gary and Mayank for their guidance and support. I would also like to thank Dr. Lazaros Gallos and Larry Frolov, the many other amazing participants of the DIMACS program, and the DIMACS REU itself for this amazing opportunity. This project was funded by the NSF (CCF-2447342).

Totally Not-Suspicious Section of My Website

yep. do u believe me?

don't click me (or click me)

Unfortunately for you, there's nothing here!
That being said, here's a picture of my icpc teammates from NAC 2025:

Here's a demonstration on the only correct way to hold a psyduck:

And finally here's a list (2) of cp problems I've written: