Week 1 (until 6/7)
First week of REU down! I arrived and situated myself in exhilarating New Joysee and the extremely walkable Rutgers campus.
In all seriousness, I'm very glad to have the opportunity to visit and do research. :) I'm very grateful to Professor Assadi for choosing me for his project. A lot of the folks I've met here are very cool, and luckily not as stereotypically nerdy as I thought they were going to be. I can have a social life here!
This week has mainly been a process of exploring campus and trying to get into a solid rhythm of things. Most of my research time was spent navigating the literature, and essentially trying to figure out what exactly my research problem is. Now that I've sorted out what papers to look through, I can actually move forward with reading through some of them. The process will likely be slow and arduous at times, but I'm optimistic :)
I started going to the gym again which is dope. This has nothing to do with research.
Week 2 (until 6/14)
So remember how I said I had worked out which papers to look through last week. Yeah... about that. I kind of spent a few days looking at the "wrong" papers, or at the very least, I could've spent that time looking at more relevant ones. Still though, I think I gained a decent bit of intuition from flailing around with 90's Karger papers.
Yesterday, I found out about a lower bound result on sparsifiers that blocks off a major avenue for potentially developing a better algorithm. However, the graduate student I'm working with, Vihan, believes that the current lower bound result could be improved by a communication complexity argument.
I attended some of the tutorials in the graph workshop and wooooow they were tough to follow. I don't say this because I thought the presenters did a poor job at teaching the material; I think the material is just intrinsically difficult. Also, I'm not the best at following along in lectures anyhow. :p Luckily, they are recorded, so I'll definitely be going back and rewatching! I don't really feel bummed for not being able to follow along. I'm just amazed at the great expanse of content in the field.
Also, I really need to get better at explaining proofs.
Week 3 (until 6/21)
We found a paper that's actually quite useful for our problem! It provides a very space efficient sketch of a graph that yields an approximation to each single requested cut query (i.e. a for-each sparsifier instead of a for-all sparsifier). The sketch is in a regular setting (i.e. the entire input graph is received at once). We need to figure out how to adapt the sketch to the insertion-only streaming model. Also, the sketch itself is a series of data structures; we need to figure out how to obtain a graphical sketch. Progress has been a little slow this week because Professor Assadi and Vihan are at a conference presenting some of their own results. I'm not complaining though, it's been nice to have a bit of a break ;)
Week 4 (until 6/28)
Professor Assadi found a paper that produces a space efficient graphical sketch that suits our needs. What's crazy is that I had actually found that paper before, but I wasn't acquainted enough with the terminology surrouding my problem, so I didn't realize that the paper was actually relevant! >:( A very valuable lesson learned. We plan to use the result of this sketch as a black box and substitute it into an existing algorithm (with modifications). I had a minor concern regarding the application of the result to the existing algorithm, but Vihan found a way to circumvent it. So, it seems like things are looking promising for lowering the upper bound. :)
Week 5 (until 7/5)
Professor Assadi, Vihan, and I had a meeting this week. Professor Assadi managed to prove a lower bound result for our problem in like 15 minutes... damn. Also, we're pretty sure our algorithm improves the upper bound. So, we have tight results for the (unweighted) insertion-only case now! Yippee!!!
Now, we're coming up with ideas to handle the dynamic streaming case. I suspect that the sketching paper with the series of data structures could be promising for a dynamic streaming algorithm. Vihan and I are now working on trying to fully understand the data structures paper. Admittedly, it's kind of poorly written, so we're trying to come up with an alternate representation that's a lot more intuitive (i.e. more in line with common techniques like Karger).
Week 6 (until 7/12)
The start of this week was rough due to personal issues. I didn't make much progress. I felt a lot better later in the week, and Vihan and I developed an intuitive framework for an approximation procedure based on some of the work in the data structures paper. Unfortunately, there is an element of the data structures paper that may be a bit difficult to replicate, as it will require looking at expander decomposition in a dynamic streaming setting. I guess I should've paid more attention during those tutorial talks. Oh boy... :')
Week 7 (until 7/19)
The paper writeup for the insertion-only case is (more or less) done and done! The dynamic streaming case is proving to be a bit difficult, but Professor Assadi and Vihan are both interested in continuing to work on the problem after the program ends! I'm looking forward to their continued mentorship, Lord knows I need it. Now I need to speedrun making my presentation for tomorrow. I told myself I wouldn't wait until the last minute and I still did. o~O
Week 8 (until 7/26)
My presentation was a little wack. Note to self: do not try to present a full algorithm in all of its formal detail in a 9 minute presentation. Also, the paper writeup isn't really done. I essentially wrote the paper in the form of lecture notes lol. Maybe this is another sign that I should be a professor >:)
The dynamic streaming case is proving to be quite difficult, but we're developing a little more understanding of the problem. The barrier comes with being able to find sparse cuts in a space-efficient manner. It is impossible to retreive all of the edges in the sparse cut, as it would violate a known lower bound. However, we don't need all of the edges in the sparse cut. That's about as much as we know right now. Also, the expander decomposition thing is not helpful at all for us... rip
Week 9
Final week done! I've moved out and I'm now living it up in Canada :3
Thank you very much to all of the organizers of the REU! Your efforts have created an invaluable experience for my research career. Though the REU is now over, my work on this project is far from done! The dynamic case is tough, but I believe that we are acapable of achieving some results there. Au revoir! (idk why I'm speaking French, I'm not even in Quebec)
Link to final presentation!