Ramtin Afshar, a doctoral student in the UC Irvine Center for Algorithms and Theory of Computation advised by Mike Goodrich, passed his defense today, becoming Mike’s 25th completed doctoral student. Ramtin’s dissertation, Exact Learning of Graphs from Queries, was based on papers from ESA 2020, LATIN 2022, and STACS 2022, all of which involved asking questions to find out the structure of an unknown graph.

A possibly familiar example here is the traceroute program, used to debug internet connections by finding a path from one networked computer to another. It uses a feature of internet protocols that allow packets to “time out” if they make too many hops, returning an error message back to the originating computer when they do. By setting the timeout to a parameter \(k\), you can force the timeout to happen at the \(k\)th step of a shortest path to another computer, and by doing so find out who is at that \(k\)th step. You might think that you would need to trace the routes between all pairs of computers on the network to find out where its edges are (and this does work, with a quadratic number of \(k\)th-step queries), but Ramtin and his coauthors (Goodrich and two other UCI students, Pedro Matias and Martha Osegueda) showed that with some natural assumptions on the network topology, only a near-linear number of queries is needed.

Beyond the papers used in his thesis, Ramtin is a coauthor on more papers in SPIRE 2020 on related problems of string reconstruction, in SPAA 2020 on reconstructing evolutionary trees or other binary trees, and in SEA 2022 on learning road maps from shortest path hop counts. His traceroute work in STACS 2022 was also the subject of a brief announcement at SPAA 2021.

His next step is to work for Google in the San Francisco Bay Area, involving a temporary two-body problem while his wife finishes her own studies at the University of Southern California.

Congratulations, Ramtin!

(Discuss on Mastodon)