Events

PhD Defense Two Algorithms Pertaining to $s$ to $t$
Export Event Save iCal Send to Google Calendar Send to Yahoo Calendar Send to Outlook Live Send to Microsoft Outlook Save iCal Preserve formatting in description (only supported in some calendar applications) Close Thursday, May 28, 2026, 02:00pm - 04:00pm

Speaker: Vikrant Ashvinkumar

Bio

Location : CoRE 301

Committee: 

Professor Jie Gao (Chair / Co-Advisor)

Professor Aaron Bernstein (Co-Advisor)

Professor Mario Szegedy

Assistant Professor Greg Bodwin (external)

Event Type: PhD Defense

Abstract: This dissertation compiles together (with some revisions) the works \cite{ashvinkumar2025faster,ashvinkumar2026parallel} whose algorithms are concerned with $n$ vertex $m$ edge digraphs $G=(V,E)$ and paths within them (say from $s \in V$ to $t \in V$). We first discuss the restricted shortest paths problem where edges of $G$ are assigned two non-negative weights: lengths and costs. For a fixed source $s \in V$ and a cost threshold $C$ we wish to find, for each target $t \in V$, the length of the shortest $(s,t)$-path whose total cost is at most $C$. This problem is NP-hard --- for instance, the $0$-$1$ knapsack problem is a special case where $G$ is a dipath --- hence the focus on finding approximate solutions for the past 20 or so years. We give the first sub-$mn$ time $(1+\varepsilon, 1+\varepsilon)$-approximation algorithm for digraphs, where both the length-optimality and cost-constraint may be off by a multiplicative $(1 + \varepsilon)$ factor for an arbitrary constant $\varepsilon > 0$. This answers a problem posed by Bernstein in 2012 after his breakthrough in the undirected case. Next, we turn to algorithmic versions of the so-called folklore shortcut set (and hopset), which is a set of edges $H$ such that $G \cup H$ has the exact same reachability relations as $G$, but shortest paths in $G \cup H$ use no more than $n^{1+o(1)}/\sqrt{|H|}$ edges. Close to 30 years after its conception, Jambulapati, Liu, and Sidford gave the first near-linear time construction for $|H| \approx n$. In a perfect world scenario where the matrix multiplication exponent $\omega = 2$, we complete this picture for $n \lesssim |H| \lesssim n^2$. In the world we live in right now (2026), our result still leads to a near-linear time construction of a shortcut set closer in parameters to the folklore. Like prior work, this is designed to parallelize, which then leads to faster work-efficient parallel algorithms for single-source reachability and shortest paths when $m \gg n$. Both algorithms use sparsification, but in a somewhat oblique way (typically, the input graph is sparsified); the first algorithm sparsifies an algorithm, and the second algorithm sparsifies a proof object.

Organization: 

Contact  Professor Jie Gao

Zoom Link: https://rutgers.zoom.us/j/96572411687?pwd=fjzie2PEG9kFF47DAZvfEQibXfnlfC.1