Isaac M. Hair

collaborators

4 papers

cs.DS2026

Bellman-Ford in Almost-Linear Time

Isaac M. Hair, George Z. Li, Jason Li +1

We consider the single-source shortest paths problem on a directed graph with real-valued (possibly negative) edge weights and solve this problem in $m^{1 + o (1)}$ time.

cs.DS2026

Improved Strongly Polynomial Work-Span Tradeoffs for Directed Single Source Shortest Paths

Isaac M. Hair, George Z. Li, Jason Li +1

We revisit the single-source shortest paths (SSSP) problem on directed graphs with nonnegative real weights and give a deterministic parallel algorithm with $O(n^{1+o(1)}t^2 + m^{1…

cs.CG2026

A Linear Time Algorithm for the Maximum Overlap of Two Convex Polygons Under Translation

Timothy M. Chan, Isaac M. Hair

Given two convex polygons $P$ and $Q$ with $n$ and $m$ edges, the maximum overlap problem is to find a translation of $P$ that maximizes the area of its intersection with $Q$ . We g…

cs.IT2026

List Recovery for Random Low-Rate Linear Codes

Isaac M Hair, Amit Sahai

We prove a list recovery guarantee for random low-rate linear codes over sufficiently large prime fields. For fixed dimension $d$ , error fraction $I^\pm$ , and accuracy parameter $\var…