48 citations · 103 across the 33 of their papers we have counts for
5 papers · 1 filter
Improved Field Size Bounds for Higher Order MDS Codes
Joshua Brakensiek, Manik Dhar, Sivakanth Gopi
Higher order MDS codes are an interesting generalization of MDS codes recently introduced by Brakensiek, Gopi and Makam (IEEE Trans. Inf. Theory 2022). In later works, they were sh…
Separating MAX 2-AND, MAX DI-CUT and MAX CUT
Joshua Brakensiek, Neng Huang, Aaron Potechin +1
Assuming the Unique Games Conjecture (UGC), the best approximation ratio that can be obtained in polynomial time for the MAX CUT problem is , obtained…
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…
Robust Factorizations and Colorings of Tensor Graphs
Joshua Brakensiek, Sami Davies
Since the seminal result of Karger, Motwani, and Sudan, algorithms for approximate 3-coloring have primarily centered around SDP-based rounding. However, it is likely that importan…
Generic Reed-Solomon Codes Achieve List-decoding Capacity
Joshua Brakensiek, Sivakanth Gopi, Visu Makam
In a recent paper, Brakensiek, Gopi and Makam introduced higher order MDS codes as a generalization of MDS codes. An order- MDS code, denoted by , h…