Reina Itakura

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).

Friday: Same thing as thursday. I basically studied the entire day for my MAT 146 final. I think it went ok. 2 more to go...

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.
5. Sergey Yekhanin. Locally Decodable Codes. https://people.csail.mit.edu/dmoshkov/courses/codes/LDC_now.pdf

Monday: Oh god it's already week 3? its so over. Started the day reading the paper Mursalin sent.

Tuesday: I'm writing this on Thursday, and the fact that I can't remember what I was doing proves how unproductive I was. I know I read through the "Dream on" slides... and I think I was also trying to work on plugging in a different kind of code into the k-clique paper reduction and was struggling.

Wednesday: Spent the entire day studying for Galois theory. it went terribly.

Thursday: Watched lecture 11 of DIMACS videos on fine-grained complexity. Met with Karthik at 11:00 a.m. I am a disappointment to Karthik (and society as a whole). After the meeting I tried constructing a threshold graph but honestly it's pretty complicated. I wrote code to help me through it but then realized that I was being an idiot.

Friday: Wrote down reduction for MIP to 2-Set intersection.

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. Amir Abboud, Aviad Rubinstein, and Ryan Williams. Distributed PCP Theorems for Hardness of Approximation in P. 2017. arXiv: 1706.06407 [cs.CC]. url: https:// arxiv.org/abs/1706.06407.
5. Virginia V. Williams. On some fine-grained questions in algorithms and complexity. https://people.csail.mit.edu/virgi/eccentri.pdf

Monday: Tried to work out the soundness case of reduction. Briefly met with Karthik. Turns out the edge set definition was wrong (tbf I thought that was probably the case). Finished writing out reduction. Briefly read page 27 (Section 6) of the monochromatic bichromatic paper. Now comparing tensoring to threshold graph.

Tuesday: Wow I'm slacking off on logging... (this is written Thursday). Frankly I can't remember what I did on Tuesday at all. I just only remember that I stayed pretty late in the office. And Nadya bought me an acai bowl (it was very good).

Wednesday: Met with Karthik in the morning (zoom). Grabbed lunch with other people. Met with Mursalin in the afternoon. After all that we were drained so we left the office early (I guess Tuesday balances it out?) and explored Barnes and Noble. We also got froyo! Gary and Mayank never had froyo before, so I'm glad I got to be there for both their first boba and froyo. Pasta competiton was also today. We lost.

Thursday: I have a lot to work on. Also hoping to go to gym today.
Update: I did NOT go to the gym because I fell asleep after lunch and did like no work (I swear it was unintentional). I will work over the weekend. I won the beginner poker tournament.

Friday: Roommates and I went to Haraz Coffee House. I give it a 0/10. I ordered a matcha latte and the matcha was clumping up. I shouldve also clarified that I wanted it sweetened... I also ordered the Dubai chocolate and it came melted. It was severely overpriced for what it was. At the coffee house I got a lot of cf done, planning to do work today and also stretch hopefully.

Sunday: Got a cookie at Hidden Grounds Coffee. It did not meet my expectations. 3/10. I also got a matcha latte there. It was acceptable. 6/10.

References:

1. 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.
2. Karthik C. S. and Pasin Manurangsi. On closest pair in euclidean metric: Monochromatic is as hard as bichromatic, 2018. URL https://arxiv.org/abs/1812.00901.
3. Amir Abboud, Aviad Rubinstein, and Ryan Williams. Distributed PCP Theorems for Hardness of Approximation in P. 2017. arXiv: 1706.06407 [cs.CC]. url: https:// arxiv.org/abs/1706.06407.