BUA Senior Named 2022 Regeneron Science Talent Search Scholar
BUA senior Zoe Xi ’22 was named one of the top 300 scholars in this year’s Regeneron Science Talent Search, the nation’s oldest and most prestigious science and math competition for high school seniors.
Zoe’s project, entitled “Approximation Algorithms for Dynamic Time Warping on Run-Length Encoded Strings,” focuses on dynamic time warping (DTW) distance algorithms under the guidance of Bill Kuszmaul, an MIT computer science PhD candidate advised by Professor Charles Leiserson. She writes:
“DTW is a well-known similarity measure for comparing strings that encode time series data. DTW distance was first introduced by Taras Vintsyuk in 1968, who applied it to the problem of speech discrimination. In the decades since, it has become one of the most widely used similarity heuristics for comparing time series in applications such as bioinformatics, signature verification, and speech recognition.
One of the most fundamental questions concerning DTW is how to compute it efficiently. The classical algorithm for computing DTW is relatively slow (as it takes quadratic time), and it is known that, in general, no algorithm can do significantly better. This has led both practitioners and theoreticians to focus on specialized versions of the problem, for example, the case where the time series are run-length encoded. Research (such as mine) that makes algorithmic progress on these specialized versions of the problem has the potential to significantly help practitioners down the road.
My research is primarily on the theoretical front and pushes forward the state of the art for what we know how to accomplish algorithmically. It can potentially help us get unstuck on a fundamental computational problem that has many real-world applications. My primary result includes three fast algorithms that approximate with high accuracy the DTW distance between two special strings consisting of runs, where each run is a string of copies of a single letter. To my knowledge, these are the first approximation DTW algorithms with formally proven time bounds.“
As a top-300 scholar, Zoe will receive $2,000, and BUA will also receive $2,000 to use toward STEM-related activities. Zoe will now be considered for a spot as one of 40 Finalists, who each receive $25,000 and participate in the final competition in March. Congratulations to Zoe on this impressive accomplishment!