From the 1 of 21 linked papers with an AI index.
21 papers
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,…
Bounds and Limitations on Codes Achieving List Recovery Capacity
Joshua Brakensiek, Yeyuan Chen, Aaron Putterman +1
In coding theory, list recoverability is a fundamental concept which robustly captures how ``spread-out'' codewords are in a code. More formally, given a code an…
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}$…