1 citations · 2 across the 25 of their papers we have counts for
16 papers · 1 filter
Cores Characterize the One-Pass Streaming Complexity of CSPs
Joshua Brakensiek, Aaron Putterman, Amatya Sharma +1
We study the one-pass streaming complexity of CSPs over a fixed finite relation under three natural objectives: , deciding whether all constraints can be satis…
The Reach of Abelian Covers in Hypergraphs
Joshua Brakensiek, Venkatesan Guruswami, Aaron Putterman
Covers in hypergraphs are frequently studied to capture various forms of dependence between hyperedges. For example, even covers--which check if each vertex appears in an even numb…
Separating Non-redundancy and Chain Length
Joshua Brakensiek, Venkatesan Guruswami, Aaron Putterman
For a constraint satisfaction problem defined by a relation , its non-redundancy is the size of largest instance (as a function of the number of variables)…
Algorithmic List Decoding of Reed-Solomon Codes up to Capacity
Joshua Brakensiek, Yeyuan Chen, Aaron Putterman +2
We give a deterministic polynomial-time list-decoding algorithm for Reed-Solomon codes over prime fields that approaches list-decoding capacity for every evaluation set and every c…
Optimal Sparsifiers for Minkowski Sums and Sums of Seminorms
Arpon Basu, Joshua Brakensiek, Yeyuan Chen +3
We extend the recent work of Reis and Rothvoss on sparsifying sums of norms to the more general task of sparsifying (Minkowski) sums of centrally symmetric, convex sets. A…
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 and…
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…
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…
Many Hamiltonians Are Sparsifiable
Arpon Basu, Joshua Brakensiek, Aaron Putterman
We study the problem of Hamiltonian sparsification: given a parameter and an -qubit Hamiltonian which is the sum of -local positive semi-definite…
Multiplicative error set system sparsification: A simpler proof via chain length contraction
Joshua Brakensiek, Venkatesan Guruswami, Aaron Putterman
The chain length of a set family is the largest ascending sequence of sets in containment order in the union-closure of . In this work,…
Fault-Tolerant Distance Oracles Below the Barrier
Sanjeev Khanna, Christian Konrad, Aaron Putterman
Fault-tolerant spanners are fundamental objects that preserve distances in graphs even under edge failures. A long line of work culminating in Bodwin, Dinitz, Robelle (SODA 2022) g…
Classification of Non-redundancy of Boolean Predicates of Arity 4
Joshua Brakensiek, Venkatesan Guruswami, Aaron Putterman
Given a constraint satisfaction problem (CSP) predicate , the non-redundancy (NRD) of is maximum-sized instance on variables such that for every clause of…
Bounded-Independence Sampling of Edges for Combinatorial Graph Properties
Aaron Putterman, Salil Vadhan, Vadim Zaripov
Random subsampling of edges is a commonly employed technique in graph algorithms, underlying a vast array of modern algorithmic breakthroughs. Unfortunately, using this technique o…