Last year I participated in POSTECH’s 2025 Undergraduate Research Program (UGRP for short). This is a rough summary of the journey I’ve taken, along with a few stuff I learnt about research.
Prologue
Before the start of the first semester, all first grade students of POSTECH spend a week at the school learning about some essential stuff about the school. The students are split up into classes, with each class being led by 4 senior students. Anyway, two of the seniors in my class attended the awards ceremony for 2024 UGRP, and that’s how I found out that such a program exists.
The Beginning
Since my high school had an R&E program, and I thoroughly enjoyed it. So naturally, I wanted to take a go at UGRP as well. That way I can continue to do research (hopefully with higher quality), and also get a chance at getting an award, thus money. In fact, the prize money for this program is quite large, and at the time one of my friends said that by just staying until the end gives a 50% chance at getting an award. So there was no reason to not try.
The program requires a minimum team of 3 people, so I just took my two friends in my ICPC team, as I was planning to do something related to algorithms. However, upon inspecting the research topics of previous award winners, pretty much all of them were either AI, or some type of engineering. This significantly lowered my chances of winning, but I still had to give it a shot.
As for exactly what topic I wanted to go with, took some time to figure out. During high school everything I did was related to heuristics, as they are easy to mess with and easy to compile results out of. It’s not really fun though, so this time I wanted to do something that is purely algorithms, or related to theoretical CS. To get some pointers, I contacted professor Eunjin Oh (who is also our advisor for the program). The conclusion was that by slightly changing the conditions of a previous research, I could get a problem that is somewhat doable.
The topic I eventually settled on was the APSP problem on unit disk graphs (UDG). At the time the only previous research I could find on APSP on unit disk graph was this paper showing an algorithm that finds APSP on unweighted unit disk graphs in slightly subquadratic time. Other researches like this one and this one were about SSSP. In fact, the subprocesses used in the SSSP papers for weighted UDGs and the subprocess used in the APSP paper were quite similar, which was the ultimate reason why I went for APSP on weighted UDGs.
So the topic of our research was APSP on weighted unit disk graphs. This was around March of 2025. We wrote all the necessary boring papers (research plans and stuff), and a few weeks later we got accepted into the program with roughly 800K won research grant. By the way, about half of that grant was used on ChatGPT Plus plan (around 10 months).
The Plan
So here was the overall plan:
- This paper solves APSP on unweighted UDGs by using a subprocess that finds the shortest path from $k$ points that make a clique. This subprocess is achieved by solving the following subproblem:
- Given two sets of points $R$ (for red) and $B$ (for blue) that are separated by a line, Find the subset of points in $B$ that are connected with some point in $R$ in $O(n)$ time after preprocessing.
- This paper solves SSSP on weighted UDGs in $O(n \log^2 n)$ time by using a modified version of Dijkstra’s algorithm. Unlike the standard algorithm, this one takes multiple points and uses them to update the distance of multiple points at the same time. The rough details is as follows:
- Given two sets of points $U$ and $V$, separated by a line, we can create an additively weighted Voronoi diagram that supports offline insertion queries of $U$, so that by inserting points of $U$ one at a time we can query points in $V$ to find the point that closest in $U$ in the diagram.
- Both of the papers mentioned above use a subprocess that updates distances of a set of points using another set of points that are separated by a line.
- In other words, wouldn’t it be possible to modify the algorithm in the APSP paper somewhat like the subprocess in the second paper to make it work with weighted UDGs?
So for the next few months I was focused on making the modified Dijkstra algorithm of the SSSP paper to work with multiple starting points.
The Downfall
Things didn’t go as planned.
While the registration for the program ended in March, we didn’t do anything until after summer break was over, which was like September. Things were okay up until this point, as I anticipated that this would happen, and we had a place to begin. Since the deadline was some time in January, I thought that we had enough time.
In addition to all this, I started getting help from a senior from professor Eunjin Oh’s lab, via a freshman research participation class. Therefore, I had a solid idea of where to start, plus help from someone who has actual experience with research in this area. I was positive that we’d manage to do something. I was wrong.
So problem 1: my teammates won’t do anything. We agreed to work on this every Sunday. Well, it turns out that weekends are cramped with a million other schedules and we barely managed to meet at Sundays. Still, since our research topic didn’t really require us to be together, we could still get things done. However, no matter how many times I asked them to, NEITHER of them would put in ANY effort to fully read a SINGLE full paper. Like, yes they are busy, but I can GUARANTEE that NEITHER of them were as busy as I was. I had the most classes, most clubs, did the most Codeforces rounds, was doing another competition on top of everything, and so on. Like, I asked them to read some papers, just understand the main idea, and they couldn’t put in the effort to do that. At some point I just gave up on them, and decided it was better to go solo.
Anyway, with my rant aside, the second problem was that this was just impossible. I don’t remember exactly, but in the APSP paper the fact the the graph was unweighted played a very important role in bounding the number of stuff to compute. Moving this to the weighted version, this was no longer possible, and no matter the efforts of me and my senior we couldn’t bound anything, thus unable to find a better solution. As things got dire I met up with professor Eunjin Oh to get some help. Again, we didn’t really manage to get much further, as the simple fact that the graph is weighted made it unable to bound anything making it impossible for us to find an algorithm better than a quadratic one.
By the way, it was around November by the time I met with the professor, and with time running out, I gave a shot at an approximation algorithm. However, with the knowledge I had at the time, an approximation faster than the one in the SSSP paper was pretty much impossible because of a very fundamental $O(\log n)$ operation of finding the smallest distance point in Dijkstra. So even this hit a dead end.
It was now December, and with finals coming up, things weren’t looking good.
The Uprise
However, I was not about to give up, as if I did, I’d probably have to pay for the ChatGPT Plus subscription my team has been using, which I did not want to do.
Since I’ve seemingly made 0 progress until now, I decided to start over and look for more previous studies that had any similarity with what I was doing. Before the freshman research participation class ended, my senior suggested to look at studies on planar graphs, so I started there. Long story short, I found out that distance oracles were another name for APSP (or what I wanted to do), and when I searched for researches on distance oracles instead of APSP, I got a whole lot more than what I had at the start. So yeah, that was surprising to say the least.
So, with a new arsenal of researches, I had stuff to work with again. The good news was that the papers were very recent, with some being uploaded on arxiv as late as 2025, so there was a higher chance that I would find some answers that I wanted. The bad news was that the papers were very recent and thus extremely difficult, requiring prior knowledge that I did not have. And with finals coming I did not have the time to read through all of them. Still, I had to try.
I skimmed through most of them and figured out two things:
- Most of these studies on distance oracles split the graph into clusters, and solve for distances inside clusters and outside clusters separately.
- The notion of VC dimension is used to bound the number of vertices inside a cluster. Of course, I had no idea what VC dimension was at the time.
With that figured out, I took my finals, and the semester came to an end. I was now half way through December, with around 3 weeks to get some kind of new result I can write about. Bad news is that I signed up to take a winter semester course at SNU, so I was not entirely free.
Still, I gave my everything and spent the classes at SNU reading the papers instead of listening to the class, and about a week later I had a rough plan of what to do:
- I am not going to explain what VC dimension is, so if you’re curious here’s the Wikipedia article.
- This paper gives an approximate distance oracle with additive error. They show the definitions for distance VC dimension and distance encoding VC dimension, prove that both are bounded on unweighted UDGs, and use that to bound the number of patterns / balls in a cluster.
- In addition, by the Sauer-Shelah Lemma, simply showing that the VC dimension is bounded is enough to show that the number of combinatorial objects themselves are bounded by some polynomial in relation to the VC dimension.
The paper proves that the VC dimension is bounded for unweighted UDGs, but not for weighted UDGs. In addition, I later found out that in the case of $K$-minor free graphs, the VC dimension is bounded even when the graph has real weights. After more digging around, I came to the conclusion that there is no previous studies on the VC dimension of weighted UDGs, and started to try and prove whether or not it was bounded. Now I had around a week left.
At first I thought that it would be bounded. I mean, the whole reason unit disk graphs are difficult is because they can admit large cliques. In fact, because of the geometric constraints, two crossing paths must admit a new edge between those paths, which is the crucial reason why VC dimensions are bounded in the unweighted setting. Surely these tight conditions would also apply to the weighted case, right?
Well, turns out I was wrong. After compiling a few conditions for a weighted UDG to have unbounded VC dimension, it didn’t take me long to actually construction that for any given constant $d$, emits a weighted UDG with VC dimension $d$. Thus, unbounded.
What this means is that the previous methods used for making distance oracles in unweighted UDGs and $K$-minor free graphs, do not work for weighted UDGs. In other words, I have mathematically proven that all of my efforts for the past 2~3 months were essentially all for nothing, and I was trying to achieve something impossible. So yeah, hooray me.
Still, this was a new result that had at least a little bit of academic meaning, so I was pretty satisfied.
I managed to do all this 3 days before the deadline. So the rest of 3 days I spent writing the final report of my painful journey, and to make things worse I caught a cold, so I was pretty much dying that week. Thankfully I managed to finish everything in time, and just had to wait for the results.
Ending
So yeah, by some miracle I managed to get a somewhat okay result. It’s not a full algorithm like I originally planned, but it’s still within the boundaries of math and theoretical CS, so I was pretty satisfied.
At the beginning of this program I thought it’d be nice if I won an award. After finishing, I felt like I had to win something. Like, I went through all that to come out empty handed? No way. Also, like, I can say for sure that what I did had a better quality than some previous winners, although it is hard to compare theory and engineering researches. I just had to get something.
Oh, and I got better average grades that semester than both of my teammates, so I still don’t understand how they couldn’t have put some effort into working with me, because they clearly didn’t spend more time on their studies than me.
Awards
So after a week or two of waiting we ended up getting the 3rd place prize (not to be confused with 3rd place). Now, this is the lowest prize there is, but there are only 3 types of prized (1st 2nd and 3rd), and I’m going to take most of the prize money anyway, so I was satisfied. Maybe if my teammates helped we could have gotten a better prize, just saying.
There was an award ceremony so me and one of my teammate attended it. Looking at the winners, it was, again, stuff about engineering (rocket at some chemistry stuff got the 1st place prize).
Here are some pictures.
My research was the only theoretical research out of all the researches submitted, which was very disappointing, though understandable.
The total prize money is 2 million won, which is a lot. Honestly, I wanted to take like 99% of it, since I literally did 99% of the work, but because I’m generous I let each of them take 200K won and I took the rest of 1,600,000 won.
In addition, remember how I said one of my friends mentioned that winning a prize had like a 50% chance? Well, that was true last year, as they gave 13 prizes out of 25 teams. This year however? There was a whopping 40 teams total that submitted the final report, making it actually challenging to win a prize. So, well done me, I actually did a pretty good job.
Epilogue
So, what did I learn from this? Well first of all my teammates seem to suck for anything other than ICPC stuff. Any team play stuff in the future, I would like to do it with someone else.
Other than that, I have thoroughly felt the importance of prior research. During high school my teacher talked time and time again about the importance of prior studies and research and made me look through like 30, but I didn’t really understand it at the time. Now though? I felt the importance through my soul, and any research I do from here on out, I will be sure to spend at least a month on just searching up prior materials. I cannot stress the importance of this enough.
For the future, I would like to do this again (of course, with more cooperative teammates), and use what I’ve learnt this time to conduct a more proper research by fully using the time given. As for the topic, I’m not sure if I’ll go pure math or theoretical again. I mean, pure theory is my favorite type of research, but it is very hard to do (at least, for an undergrad), and it is clear that pure theory isn’t really favored in this program. I might give a shot at AI, but with some theory sprinkled in, not sure though.
Anyway, that was my journey through the 2025 undergraduate research program. It wasn’t easy, but it was quite fun, and I did learn a whole bunch from it. Hopefully I get to give it a shot next year, and if so I can write about it again. That’s all from me, cheers.