22 papers
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…
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
The non-redundancy (NRD) of a constraint satisfaction problem (CSP) is a combinatorial quantity closely tied to the behavior of CSPs in various computational models including their…
Redundancy Is All You Need (for CSP Sparsification)
Joshua Brakensiek, Venkatesan Guruswami
The seminal work of Benczúr and Karger demonstrated cut sparsifiers of near-linear size. Subsequent extensions have yielded sparsifiers for hypergraph cuts and more recently linea…
Unique Decoding of Reed-Solomon and Related Codes for Semi-Adversarial Errors
Joshua Brakensiek, Yeyuan Chen, Manik Dhar +1
Motivated by recent developments in coding theory, particular in list-decoding, we introduce a new error model which we call semi-adversarial errors. This error model bridges betwe…
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…