48 citations · 103 across the 33 of their papers we have counts for
4 papers · 1 filter
Tight approximability of MAX 2-SAT and relatives, under UGC
Joshua Brakensiek, Neng Huang, Uri Zwick
Austrin showed that the approximation ratio obtained by the MAX 2-SAT approximation algorithm of Lewin, Livnat and Zwick (LLZ) is optimal modulo the Unique Ga…
AG Codes Achieve List-decoding Capacity over Constant-sized Fields
Joshua Brakensiek, Manik Dhar, Sivakanth Gopi +1
The recently-emerging field of higher order MDS codes has sought to unify a number of concepts in coding theory. Such areas captured by higher order MDS codes include maximally rec…
Generalized GM-MDS: Polynomial Codes are Higher Order MDS
Joshua Brakensiek, Manik Dhar, Sivakanth Gopi
The GM-MDS theorem, conjectured by Dau-Song-Dong-Yuen and proved by Lovett and Yildiz-Hassibi, shows that the generator matrices of Reed-Solomon codes can attain every possible con…
Kapranov degrees
Joshua Brakensiek, Christopher Eur, Matt Larson +1
The moduli space of stable rational curves with marked points has two distinguished families of maps: the forgetful maps, given by forgetting some of the markings, and the Kapranov…