ÌÇÐÄVlogÊÓƵ

Thesis Defense: C. Shane Elder | August 12, 2026 | 12pm

CBD and CPCB are proud to announce the following thesis defense:

Title: Robust Unlabeled Distance Recovery in One Dimension: Algorithms and Mathematical Programming for the Turnpike Family

C.Shane Elder

For Zoom details, please contact Nicole Stenger 

Committee:

Carl Kingsford (Chair), ÌÇÐÄVlogÊÓƵ 
Guillaume Marçais, ÌÇÐÄVlogÊÓƵ
James Faeder, University of Pittsburgh
Steven Skiena, Stony Brook University 

Abstract:
One-dimensional unlabeled distance recovery asks for a latent point configuration given only a multiset of pairwise distances. Classical examples include Turnpike, for points on a line, and Beltway, for points on a circle. In the biological and physical measurement settings that motivate this dissertation, the data are rarely exact: distances may be noisy, quantized, duplicated, missing, or only partially labeled.

This dissertation develops a unified approach to robust one-dimensional distance recovery built around three complementary ideas. First, it gives scalable optimization-based solvers that treat recovery as a coupled assignment-and-regression problem and exploit implicit sorting structure to handle large noisy instances. Second, it develops a modular modeling framework for structured observation variants, including missing, duplicated, partially labeled, and circular-distance data. Third, it introduces combinatorial LP/ILP formulations based on triangle equalities, yielding certificate mechanisms for realizability together with deterministic robustness guarantees under bounded perturbation and rounding.

The resulting framework separates large-scale best-fit recovery from exact certification while keeping both views centered on the same latent object: an assignment between observed distances and interval indices. Across the dissertation, this perspective leads to algorithms that scale to large biological instances, exact formulations for moderate-sized structured problems, and new arithmetic and geometric analyses that clarify when unlabeled distance recovery is computationally tractable, diagnostically meaningful, and robust to finite-precision effects.