Computing has been a part of Kalina Petrova’s life since she first took part in a 5th grade extra-curricular programming class. Fascinated by the process of solving computational problems, Kalina had immersed herself in research by the time she reached high school, presenting research projects at national conferences around her home country of Bulgaria. She also participated in the Research Science Institute, a 6-week research program for high school students at MIT, working on a computational neuroscience project.
When the time came to select a university, her experiences in research convinced Kalina to pursue a degree in engineering at Princeton, where a semester of research is built into the undergraduate curriculum. Inspired by the work of her Theory of Algorithms professor, Dr. Robert Tarjan, Kalina sought him out as a research advisor. The choice proved to be a wise one, as they worked together not only for the required semester but also for the following year.
Rather than assigning Kalina a project, Dr. Tarjan encouraged her to choose one on her own, and she read several published articles on algorithms, eventually focusing on computational geometry and data structures. In particular, her research focused on the following problem: Given a set of horizontal and vertical segments in a plane, how can we efficiently support inserting new segments and responding to queries in the form “given a rectangle, report all intersections of segments in that rectangle”? At the conclusion of her project, Kalina had devised an algorithm to support these operations in sublinear time and subquadratic space in terms of the number of objects (segments or rectangles). This proved to be a significant achievement, as the best previously known algorithms took more than linear time or more than quadratic space. Kalina presented her research–eventually titled “A Data Structure for Dynamic Segment and Rectangle Intersection Range Queries”–as a paper at the Fifteenth International Workshop on Algebraic and Coding Theory, and as a poster for the Princeton Computer Science department.
Kalina believes that research has benefited her both personally and professionally, stating that “it makes me more patient, more creative, more rational, and it helps me believe in myself more.” Moreover, Kalina says, research has “helped me approach new material more critically… given me confidence that I can understand highly complex material if I tinker with it myself.” She enjoys the learning aspect of research, noting that the best way for her to understand something in math and theoretical computer science is to work it out herself — trying to find a proof of some theorem as opposed to just reading through somebody else’s proof or thinking about open questions. When asked if she had any advice for other students looking to get into research, Kalina touches on the importance of being independent and not relying too heavily on one’s advisor, as well as the importance of keeping up to date on the “latest trends and techniques in their respective area of research.” She also advises fellow students not to confine their imagination, remarking, “You never know when you might come up with something interesting and valuable, so explore every hunch you have no matter how fruitless it appears to be.”
Apart from research, while at Princeton, Kalina also participated in ACM ICPC, a worldwide programming competition for college students, where in her senior year her team made it to the world finals. Looking back over her many experiences in computing and research has led Kalina to believe she would enjoy an academic career. As such, she is currently pursuing a master’s degree at ETH Zurich, where one semester is devoted entirely to research, after which she plans to attend graduate school.
-Written and edited by Keith Feldman and Booma S Balasubramani