CRA-E’s Undergraduate Research Highlights: “Gluttonous” Algorithm Feeds Research Growth
CRA-E’s “Undergraduate Research Highlights” series showcases outstanding research done by undergraduate students at universities and colleges across North America. Each article features the story of a successful undergraduate researcher and offers personal insights into their experiences with finding an advisor, undertaking new research projects, and discovering how research can impact their personal and professional future. It is one of a number of CRA-E’s activities that foster and recognize talented computing researchers with the goal of increasing the research pipeline, promoting graduate education, and advocating research-based careers.
In addition to helping students understand the process of getting involved in research, the articles also serve as a venue for students to pass along advice to others who aspire to become involved in research themselves. Students selected for the research highlights include those receiving recognition in the CRA Outstanding Undergraduate Researcher Award competition. This series is written and edited by CRA-E Graduate Fellows.
“Gluttonous” Algorithm Feeds Research Growth
Rhea Jain, B.S. Computer Science and Mathematics, Carnegie Mellon University
This Q&A highlight features Rhea Jain, an Honorable Mention in the 2021 CRA Outstanding Undergraduate Researchers award program. Rhea graduated from Carnegie Mellon University and is now a PhD student at the University of Illinois Urbana-Champaign. This interview has been edited for length and clarity.
What originally influenced you to consider doing research as an undergraduate?
I really enjoyed the undergraduate theory course at CMU and later joined the course staff as an undergraduate teaching assistant (TA). Many of the other TAs talked about research opportunities, so I became curious.
I decided to take CMU’s two-semester research seminar course. The first semester is about the research process, especially how to read and analyze papers. In the second semester you’re supposed to work on a small research project. Ultimately, the seminar ended up going virtual in March, so the research project kind of fell apart, but the course was an exciting introduction to the research process and the possibilities out there.
Tell us about the research project that became your senior thesis.
After taking a grad-level algorithms course with Anupam Gupta, I reached out to say I was really interested in what we learned in the course and asked if there were any opportunities for research. We discussed what I’m interested in and my background. He was like, “You know, actually, I have a problem I’ve been thinking of working on—why don’t you go read about this and let me know what you think.” That was the Steiner Forest problem.
Anupam was trying to explore greedy-style algorithms to see if we could get a constant-factor approximation. A greedy algorithm takes the next step that looks the best at the time. So, he defined the “gluttonous” algorithm—more greedy than greedy. He had already shown that the gluttonous algorithm gives a constant-factor approximation, but the analysis was imprecise in some steps, leaving room for improvement. Most of my senior thesis project was asking, what’s the actual approximation factor? I proved a tighter factor and shared my results during the senior thesis presentations.
What challenges did you encounter in research? What did you learn from them?
I often thought I had a proof, but in the process of formally writing it down, realized it broke. That cycle really showed me the difference between research and homework. If you’re stuck on a homework problem, no professor or TA will let you go too far down a rabbit hole. The completely open-ended nature of research was daunting at first. I just had to follow a direction until I hit a wall; there was no one to tell me whether an idea would work.
I learned to be very comfortable with the idea of not “succeeding” in research, not getting any results. The process matters more, especially when first starting out.
What were some of your favorite aspects of research?
I really enjoyed collaborative problem-solving, especially brainstorming sessions with Anupam and his PhD student, Roie. We would talk through ideas for an hour or two at a time. I learned a lot from seeing their thought processes and getting feedback on my ideas. Figuring out even a small piece of a problem was a huge kick.
How has participating in research shaped your professional path?
I loved working as a TA at CMU from sophomore year on, so I definitely saw an academic career as a possibility. Research solidified that desire. Until senior year, my biggest concern with research was: Am I smart enough? Do I know enough? Actually sitting down and working on a project helped me realize research is doable, and more enjoyable than anything else I had done before, like software internships. That gave me a lot of confidence and clarity going into grad school.
Do you have any advice for other students looking to get into research?
Don’t be scared to reach out to professors. You’d be surprised how many are willing to work with you. On the flip side, don’t take it personally if they say no. Talk to upperclassmen and grad students to learn about faculty advising styles and find what will work for you.
— Edited by Nadia Ady and Ian Ludden
