48 citations · 103 across the 33 of their papers we have counts for
11 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.…
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…
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…
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…
Tight Bounds for Sparsifying Random CSPs
Joshua Brakensiek, Venkatesan Guruswami, Aaron Putterman
The problem of CSP sparsification asks: for a given CSP instance, what is the sparsest possible reweighting such that for every possible assignment to the instance, the number of s…
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 linear…
SDPs and Robust Satisfiability of Promise CSP
Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep
For a constraint satisfaction problem (CSP), a robust satisfaction algorithm is one that outputs an assignment satisfying most of the constraints on instances that are near-satisfi…
A Simple Sublinear Algorithm for Gap Edit Distance
Joshua Brakensiek, Moses Charikar, Aviad Rubinstein
We study the problem of estimating the edit distance between two -character strings. While exact computation in the worst case is believed to require near-quadratic time, previo…
The Power of the Combined Basic LP and Affine Relaxation for Promise CSPs
Joshua Brakensiek, Venkatesan Guruswami, Marcin Wrochna +1
In the field of constraint satisfaction problems (CSP), promise CSPs are an exciting new direction of study. In a promise CSP, each constraint comes in two forms: "strict" and "wea…
Bridging between 0/1 and Linear Programming via Random Walks
Joshua Brakensiek, Venkatesan Guruswami
Under the Strong Exponential Time Hypothesis, an integer linear program with Boolean-valued variables and equations cannot be solved in time for any constant .…
Constant-factor approximation of near-linear edit distance in near-linear time
Joshua Brakensiek, Aviad Rubinstein
We show that the edit distance between two strings of length can be computed within a factor of in time as long as the edit distance is at least for…