48 citations · 103 across the 33 of their papers we have counts for
7 papers · 1 filter
MAX BISECTION might be harder to approximate than MAX CUT
Joshua Brakensiek, Neng Huang, Aaron Potechin +1
The MAX BISECTION problem seeks a maximum-size cut that evenly divides the vertices of a given undirected graph. An open problem raised by Austrin, Benabbas, and Georgiou is whethe…
From Random to Explicit via Subspace Designs With Applications to Local Properties and Matroids
Joshua Brakensiek, Yeyuan Chen, Manik Dhar +1
In coding theory, a common question is to understand the threshold rates of various local properties of codes, such as their list decodability and list recoverability. A recent wor…
Combinatorial Bounds for List Recovery via Discrete Brascamp--Lieb Inequalities
Joshua Brakensiek, Yeyuan Chen, Manik Dhar +1
In coding theory, the problem of list recovery asks one to find all codewords of a given code which such that at least fraction of the symbols of lie in some pred…
Improved Constructions and Lower Bounds for Maximally Recoverable Grid Codes
Joshua Brakensiek, Manik Dhar, Sivakanth Gopi
In this paper, we continue the study of Maximally Recoverable (MR) Grid Codes initiated by Gopalan et al. [SODA 2017]. More precisely, we study codes over an grid topo…
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…
The Richness of CSP Non-redundancy
Joshua Brakensiek, Venkatesan Guruswami, Bart M. P. Jansen +2
In the field of constraint satisfaction problems (CSP), a clause is called redundant if its satisfaction is implied by satisfying all other clauses. An instance of CSP is call…
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…