Vikrant Ashvinkumar

activity

20192026

collaborators

10 papers

cs.DS2026

A Deterministic Near-Linear Time Approximation Algorithm for Restricted Shortest Paths in Directed Graphs

Vikrant Ashvinkumar

In the restricted shortest paths problem, we are given an $n$ -vertex $m$ -edge directed graph $G$ whose edges are assigned two non-negative weights (or resources) called lengths and…

cs.DS2026

Parallel Reachability and Shortest Paths on Non-sparse Digraphs: Near-linear Work and Sub-square-root Depth

Vikrant Ashvinkumar, Aaron Bernstein, Maximilian Probst Gutenberg +1

We present parallel algorithms for computing single-source reachability and shortest paths on directed $n$ -vertex $m$ -edge graphs using near-linear $O ~ (m)$ work and $o(\sqrt…

cs.IT2025

Algorithmic Improvements to List Decoding of Folded Reed-Solomon Codes

Vikrant Ashvinkumar, Mursalin Habib, Shashank Srivastava

Folded Reed-Solomon (FRS) codes are a well-studied family of codes, known for achieving list decoding capacity. In this work, we give improved deterministic and randomized algorith…

cs.DS2025

Vantage Point Selection Algorithms for Bottleneck Capacity Estimation

Vikrant Ashvinkumar, Rezaul Chowdhury, Jie Gao +3

Motivated by the problem of estimating bottleneck capacities on the Internet, we formulate and study the problem of vantage point selection. We are given a graph $G = (V, E)$ whose e…

cs.DS2024

Faster Approximation Algorithms for Restricted Shortest Paths in Directed Graphs

Vikrant Ashvinkumar, Aaron Bernstein, Adam Karczmarz

In the restricted shortest paths problem, we are given a graph $G$ whose edges are assigned two non-negative weights: lengths and delays, a source $s$ , and a delay threshold $D$ . T…

math.CO2024

Palette Sparsification via FKNP

Vikrant Ashvinkumar, Charles Kenney

A random set $S$ is $p$ -spread if, for all sets $T$ , $P (S \supseteq T) \leq p^{∣ T ∣} .$ There is a constant $C > 1$ large enough that for every graph $G$ with maximum degree…

cs.DS2024

Low Sensitivity Hopsets

Vikrant Ashvinkumar, Aaron Bernstein, Chengyuan Deng +2

Given a weighted graph $G$ , a $(β, ε)$ -hopset $H$ is an edge set such that for any $s, t \in V (G)$ , where $s$ can reach $t$ in $G$ , there is a path from $s$ to $t$ in $G \c…

cs.DS2023

Evaluating Stability in Massive Social Networks: Efficient Streaming Algorithms for Structural Balance

Vikrant Ashvinkumar, Sepehr Assadi, Chengyuan Deng +2

Structural balance theory studies stability in networks. Given a $n$ -vertex complete graph $G = (V, E)$ whose edges are labeled positive or negative, the graph is considered \emph{bal…

cs.DC2023

Parallel, Distributed, and Quantum Exact Single-Source Shortest Paths with Negative Edge Weights

Vikrant Ashvinkumar, Aaron Bernstein, Nairen Cao +5

This paper presents parallel, distributed and quantum algorithms for single-source shortest paths when edges can have negative weights (negative-weight SSSP). We show a framework t…

cs.CG2019

Local Routing in Sparse and Lightweight Geometric Graphs

Vikrant Ashvinkumar, Joachim Gudmundsson, Christos Levcopoulos +2

Online routing in a planar embedded graph is central to a number of fields and has been studied extensively in the literature. For most planar graphs no $O (1)$ -competitive online r…