From the 1 of 24 linked papers with an AI index.
18 papers · 1 filter
Reachability in Directed Acyclic Graphs with Near-Linear Cut Queries
Sanjeev Khanna, Aaron Putterman, Junkai Song
In the cut-query model, an algorithm is given access to a graph \emph{only} via cut queries. This model has seen significant attention in the undirected graph setting,…
A Unified Theory of Sparsification
Sanjeev Khanna, Aaron Putterman, Madhu Sudan
We study the sparsifiability of \emph{real-valued codes}, a unifying abstraction that generalizes both combinatorial and continuous notions of sparsification, including spectral sp…
Bounded-Independence Sampling of Edges for Combinatorial Graph Properties
Aaron Putterman, Salil Vadhan, Vadim Zaripov
The paper investigates how bounded‑independence edge sampling can preserve graph properties such as connectivity and cycle‑freeness, and provides explicit derandomization technique…
A Near-Optimal Parallel Algorithm for Finding Matroid Bases
Sanjeev Khanna, Aaron Putterman, Junkai Song
We settle the classic question of the parallel complexity of computing a matroid basis, as first posed in the seminal work of Karp, Upfal, and Wigderson (FOCS 1985, JCSS 1988). Our…
Resizable Retrieval
William Kuszmaul, Aaron Putterman, Tingqiang Xu +2
A dynamic retrieval data structure encodes a function for a set , while supporting queries for , insertions \texttt{Insert}$…
An Round Parallel Algorithm for Matroid Bases
Sanjeev Khanna, Aaron Putterman, Junkai Song
We study the parallel (adaptive) complexity of the classic problem of finding a basis in an -element matroid, given access via an \emph{independence oracle}. In this model, the…