Publications (9)
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…
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 -vertex complete graph whose edges are labeled positive or negative, the graph is considered \emph{bal…
Low Sensitivity Hopsets
Vikrant Ashvinkumar, Aaron Bernstein, Chengyuan Deng +2
Given a weighted graph , a -hopset is an edge set such that for any , where can reach in , there is a path from to in $G \…
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…
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 -vertex -edge graphs using near-linear work and $o(\sqrt…
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 whose e…