5 papers
Unique Decoding of Explicit -balanced Codes Near the Gilbert-Varshamov Bound
Fernando Granha Jeronimo, Dylan Quintana, Shashank Srivastava +1
The Gilbert-Varshamov bound (non-constructively) establishes the existence of binary codes of distance and rate (where an upper bound of is know…
List Decoding of Direct Sum Codes
Vedat Levi Alev, Fernando Granha Jeronimo, Dylan Quintana +2
We consider families of codes obtained by "lifting" a base code through operations such as -XOR applied to "local views" of codewords of , according t…
Sum-of-Squares Lower Bounds for Sherrington-Kirkpatrick via Planted Affine Planes
Mrinalkanti Ghosh, Fernando Granha Jeronimo, Chris Jones +2
The Sum-of-Squares (SoS) hierarchy is a semi-definite programming meta-algorithm that captures state-of-the-art polynomial time guarantees for many optimization problems such as Ma…
Tighter Bounds on the Independence Number of the Birkhoff Graph
Leonardo Nagami Coregliano, Fernando Granha Jeronimo
The Birkhoff graph is the Cayley graph of the symmetric group , where two permutations are adjacent if they differ by a single cycle. Our main result is a tigh…
Approximating Constraint Satisfaction Problems on High-Dimensional Expanders
Vedat Levi Alev, Fernando Granha Jeronimo, Madhur Tulsiani
We consider the problem of approximately solving constraint satisfaction problems with arity (-CSPs) on instances satisfying certain expansion properties, when viewed as…