2 citations · 9 across the 28 of their papers we have counts for
46 papers
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…
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…
Quantum Cut Sparsifiers
Arpon Basu, Joshua Brakensiek, Pravesh K. Kothari +1
In this paper, we continue a line of research initiated by Basu, Brakensiek, and Putterman [2026] studying the sparsifiability of Hamiltonians. We focus particularly on the sparsif…
Super-linear Lower Bounds for CSP Non-Redundancy via Shrinking Instances
Joshua Brakensiek, Venkatesan Guruswami, Bart M. P. Jansen +2
We say that an instance of a constraint satisfaction problem (CSP) is non-redundant if the satisfaction of each clause cannot be implied by the satisfaction of the other clauses in…