48 citations · 103 across the 33 of their papers we have counts for
16 papers · 1 filter
Improved lower bounds on the approximability of Multiway Cut using Sherali-Adams relaxations
Joshua Brakensiek, Neng Huang, Aaron Potechin +1
The Multiway Cut problem is among the most well-studied problems in the area of combinatorial approximation algorithms. The currently best approximation ratio for the problem is 1.…
Upper Bounds for CSP Non-redundancy via Locally Decodable Codes
Joshua Brakensiek, David Conlon, Venkatesan Guruswami +4
In the study of constraint satisfaction problems (CSPs), the non-redundancy of a relation measures the maximum number of clauses in a CSP instance which can be logically independen…
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…
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…
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,…
Improved Approximation Algorithms for Multiway Cut by Large Mixtures of New and Old Rounding Schemes
Joshua Brakensiek, Neng Huang, Aaron Potechin +1
The input to the Multiway Cut problem is a weighted undirected graph, with nonnegative edge weights, and designated terminals. The goal is to partition the vertices of the grap…
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…
Maximal Recoverability: A Nexus of Coding Theory
Joshua Brakensiek, Venkatesan Guruswami
In the modern era of large-scale computing systems, a crucial use of error correcting codes is to judiciously introduce redundancy to ensure recoverability from failure. To get the…
New Algorithms and Hardness Results for Robust Satisfiability of (Promise) CSPs
Joshua Brakensiek, Lorenzo Ciardo, Venkatesan Guruswami +2
In this paper, we continue the study of robust satisfiability of promise CSPs (PCSPs), initiated in (Brakensiek, Guruswami, Sandeep, STOC 2023 / Discrete Analysis 2025), and obtain…