Fernando Granha Jeronimo

STOC Conference 2025 Conference Paper

Explicit Codes Approaching Generalized Singleton Bound using Expanders

• Fernando Granha Jeronimo
• Tushant Mittal
• Shashank Srivastava
• Madhur Tulsiani

We construct a new family of explicit codes that are list decodable to capacity and achieve an optimal list size of O (1/є). In contrast to existing explicit constructions of codes achieving list decoding capacity, our arguments do not rely on algebraic structure but utilize simple combinatorial properties of expander graphs. Our construction is based on a celebrated distance amplification procedure due to Alon, Edmonds, and Luby [FOCS’95], which transforms any high-rate code into one with near-optimal rate-distance tradeoff. We generalize it to show that the same procedure can be used to transform any high-rate code into one that achieves list decoding capacity. Our proof can be interpreted as a ”local-to-global” phenomenon for (a slight strengthening of) the generalized Singleton bound. Using this construction, for every R , є ∈ (0,1) and k ∈ ℕ + , we obtain an explicit family of rate R codes C ⊆ Σ n that achieve the є-relaxed generalized Singleton bound. The alphabet size of these codes is a constant depending only on є and k , and they can be list decoded up to radius k −1/ k · (1− R −є), in time n O k ,є (1) with a list of size k −1. As a corollary of our result, we also obtain the first explicit construction of LDPC codes achieving list decoding capacity, and in fact arbitrarily close to the generalized Singleton bound.

FOCS Conference 2023 Conference Paper

List Decoding of Tanner and Expander Amplified Codes from Distance Certificates

• Fernando Granha Jeronimo
• Shashank Srivastava
• Madhur Tulsiani

We develop new list decoding algorithms for Tanner codes and distance-amplified codes based on bipartite spectral expanders. We show that proofs exhibiting lower bounds on the minimum distance of these codes can be used as certificates discoverable by relaxations in the Sum-of-Squares (SoS) semi-definite programming hierarchy. Combining these certificates with certain entropic proxies to ensure that the solutions to the relaxations cover the entire list, then leads to algorithms for list decoding several families of codes up to the Johnson bound. We prove the following results: - We show that the LDPC Tanner codes of Zémor [IEEE Trans. Inf. Theory 2001] with alphabet size q, block-length n and distance $\delta$, based on an expander graph with degree d, can be list-decoded up to distance $\mathcal{J}_{q}(\delta)-\varepsilon$ in time $n^{O_{d, q}\left(1 / \varepsilon^{4}\right)}$, where $\mathcal{J}_{q}(\delta)$ denotes the Johnson bound. - We show that the codes obtained via the expander-based distance amplification procedure of Alon, Edmonds and Luby [FOCS 1995] can be list-decoded close to the Johnson bound using the SoS hierarchy, by reducing the list decoding problem to unique decoding of the base code. In particular, starting from any base code unique-decodable up to distance $\delta$, one can obtain near-MDS codes with rate R and distance $1-R-\varepsilon$, list-decodable up to the Johnson bound in time $n^{O_{\varepsilon, \delta}(1)}$. - We show that the locally testable codes of Dinur et al. [STOC 2022] with alphabet size q, block-length n and distance $\delta$ based on a square Cayley complex with generator sets of size d, can be list-decoded up to distance $\mathcal{J}_{q}(\delta)-\varepsilon$ in time $n^{O_{d, q}\left(1 / \varepsilon^{4}\right)}$, where $\mathcal{J}_{q}(\delta)$ denotes the Johnson bound.

STOC Conference 2023 Conference Paper

The Power of Unentangled Quantum Proofs with Non-negative Amplitudes

• Fernando Granha Jeronimo
• Pei Wu

Quantum entanglement is a fundamental property of quantum mechanics and it serves as a basic resource in quantum computation and information. Despite its importance, the power and limitations of quantum entanglement are far from being fully understood. Here, we study entanglement via the lens of computational complexity. This is done by studying quantum generalizations of the class NP with multiple unentangled quantum proofs, the so-called QMA(2) and its variants. The complexity of QMA(2) is known to be closely connected to a variety of problems such as deciding if a state is entangled and several classical optimization problems. However, determining the complexity of QMA(2) is a longstanding open problem, and only the trivial complexity bounds ⊆ (2) ⊆ are known. In this work, we study the power of unentangled quantum proofs with non-negative amplitudes, a class which we denote QMA + (2). In this setting, we are able to design proof verification protocols for (increasingly) hard problems both using logarithmic size quantum proofs and having a constant probability gap in distinguishing yes from no instances. In particular, we design global protocols for small set expansion (SSE), unique games (UG), and PCP verification. As a consequence, we obtain NP ⊆ QMA log + (2) with a constant gap. By virtue of the new constant gap, we are able to “scale up” this result to QMA + (2), obtaining the full characterization QMA + (2)=NEXP by establishing stronger explicitness properties of the for . We believe that our protocols are interesting examples of proof verification and property testing in their own right. Moreover, each of our protocols has a single isolated property testing task relying on non-negative amplitudes which if generalized would allow transferring our results to QMA(2). One key novelty of these protocols is the manipulation of quantum proofs in a global and coherent way yielding constant gaps. Previous protocols (only available for general amplitudes) are either local having vanishingly small gaps or treating the quantum proofs as classical probability distributions requiring polynomially many proofs. In both cases, these known protocols do not imply non-trivial bounds on QMA(2).

FOCS Conference 2022 Conference Paper

Almost Ramanujan Expanders from Arbitrary Expanders via Operator Amplification

• Fernando Granha Jeronimo
• Tushant Mittal
• Sourya Roy
• Avi Wigderson

We give an efficient algorithm that transforms any bounded degree expander graph into another that achieves almost optimal (namely, near-quadratic, $d\leq 1/\lambda^{2+o(1)}$) trade-off between (any desired) spectral expansion $\lambda$ and degree d. Furthermore, the algorithm is local: every vertex can compute its new neighbors as a subset of its original neighborhood of radius $O(\log(1/\lambda))$. The optimal quadratic trade-off is known as the Ramanujan bound, so our construction gives almost Ramanujan expanders from arbitrary expanders. The locality of the transformation preserves structural properties of the original graph, and thus has many consequences. Applied to Cayley graphs, our transformation shows that any expanding finite group has almost Ramanujan expanding generators. Similarly, one can obtain almost optimal explicit constructions of quantum expanders, dimension expanders, monotone expanders, etc. , from existing (suboptimal) constructions of such objects. Another consequence is a “derandomized” random walk on the original (suboptimal) expander with almost optimal convergence rate. Our transformation also applies when the degree is not bounded or the expansion is not constant. We obtain our results by a generalization of Ta-Shma’s technique in his breakthrough paper [STOC 2017], used to obtain explicit almost optimal binary codes. Specifically, our spectral amplification extends Ta-Shma’s analysis of bias amplification from scalars to matrices of arbitrary dimension in a very natural way. Curiously, while Ta-Shma’s explicit bias amplification derandomizes a well-known probabilistic argument (underlying the Gilbert-Varshamov bound), there seems to be no known probabilistic (or other existential) way of achieving our explicit (high-dimensional”) spectral amplification.

STOC Conference 2021 Conference Paper

Near-linear time decoding of Ta-Shma's codes via splittable regularity

• Fernando Granha Jeronimo
• Shashank Srivastava
• Madhur Tulsiani

The Gilbert–Varshamov bound non-constructively establishes the existence of binary codes of distance 1/2−є/2 and rate Ω(є 2 ). In a breakthrough result, Ta-Shma [STOC 2017] constructed the first explicit family of nearly optimal binary codes with distance 1/2−є/2 and rate Ω(є 2+α ), where α → 0 as є → 0. Moreover, the codes in Ta-Shma’s construction are є-balanced, where the distance between distinct codewords is not only bounded from below by 1/2−є/2, but also from above by 1/2+є/2. Polynomial time decoding algorithms for (a slight modification of) Ta-Shma’s codes appeared in [FOCS 2020], and were based on the Sum-of-Squares (SoS) semidefinite programming hierarchy. The running times for these algorithms were of the form N O α (1) for unique decoding, and N O є,α (1) for the setting of “gentle list decoding”, with large exponents of N even when α is a fixed constant. We derive new algorithms for both these tasks, running in time Õ є ( N ). Our algorithms also apply to the general setting of decoding direct-sum codes. Our algorithms follow from new structural and algorithmic results for collections of k -tuples (ordered hypergraphs) possessing a “structured expansion” property, which we call splittability . This property was previously identified and used in the analysis of SoS-based decoding and constraint satisfaction algorithms, and is also known to be satisfied by Ta-Shma’s code construction. We obtain a new weak regularity decomposition for (possibly sparse) splittable collections W ⊆ [ n ] k , similar to the regularity decomposition for dense structures by Frieze and Kannan [FOCS 1996]. These decompositions are also computable in near-linear time Õ(| W |), and form a key component of our algorithmic results.

SODA Conference 2020 Conference Paper

List Decoding of Direct Sum Codes

• Vedat Levi Alev
• Fernando Granha Jeronimo
• Dylan Quintana
• Shashank Srivastava
• Madhur Tulsiani

FOCS Conference 2020 Conference Paper

Sum-of-Squares Lower Bounds for Sherrington-Kirkpatrick via Planted Affine Planes

• Mrinalkanti Ghosh
• Fernando Granha Jeronimo
• Chris Jones
• Aaron Potechin
• Goutham Rajendran

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 Max- $k$ -CSPs and Tensor PCA. On the flip side, a SoS lower bound provides evidence of hardness, which is particularly relevant to average-case problems for which NP-hardness may not be available. In this paper, we consider the following average case problem, which we call the Planted Affine Planes (PAP) problem: Given $m$ random vectors $d_{1}, \ldots, d_{m}$ in $\mathrm{I}\! \mathrm{R}^{n}$, can we prove that there is no vector $v \in \mathrm{I}\! \mathrm{R}^{n}$ such that for all $u\in[m], \ \langle v, d_{u}\rangle^{2}= 1$? In other words, can we prove that $m$ random vectors are not all contained in two parallel hyperplanes at equal distance from the origin? We prove that for $m\leq n^{3/ 2-\varepsilon}$, with high probability, degree- $n^{\Omega(\varepsilon)}$ SoS fails to refute the existence of such a vector $v$. When the vectors $d_{1}, \ldots, d_{m}$ are chosen from the multivariate normal distribution, the PAP problem is equivalent to the problem of proving that a random $n$ -dimensional subspace of $\mathrm{I}\! \mathrm{R}^{m}$ does not contain a boolean vector. As shown by Mohanty–Raghavendra–Xu [STOC 2020], a lower bound for this problem implies a lower bound for the problem of certifying energy upper bounds on the Sherrington-Kirkpatrick Hamiltonian, and so our lower bound implies a degree- $n^{\Omega(\varepsilon)}$ SoS lower bound for the certification version of the Sherrington-Kirkpatrick problem. The full version of the paper is available at http: //arxiv. org/abs/2009. 01874.

FOCS Conference 2020 Conference Paper

Unique Decoding of Explicit $\varepsilon$-balanced Codes Near the Gilbert-Varshamov Bound

• Fernando Granha Jeronimo
• Dylan Quintana
• Shashank Srivastava
• Madhur Tulsiani

The Gilbert-Varshamov bound (non-constructively) establishes the existence of binary codes of distance $1/2-\varepsilon$ and rate $\Omega(\varepsilon^{2})$ (where an upper bound of $O(\varepsilon^{2}\log(1/\varepsilon))$ is known). Ta-Shma [STOC 2017] gave an explicit construction of $\varepsilon$ -balanced binary codes, where any two distinct codewords are at a distance between $1/2-\varepsilon/2$ and $1/2+\varepsilon/2$, achieving a near optimal rate of $\Omega(\varepsilon^{2+\beta})$, where $\beta\rightarrow 0$ as $\varepsilon\rightarrow 0$. We develop unique and list decoding algorithms for (a slight modification of) the family of codes constructed by Ta-Shma, in the adversarial error model. We prove the following results for $\varepsilon$ -balanced codes with block length $N$ and rate $\Omega(\varepsilon^{2+\beta})$ in this family: –For all $\varepsilon, \beta > 0$, there are explicit codes which can be uniquely decoded up to an error of half the minimum distance in time $N^{O_{\varepsilon, \beta}(1)}$. –For any fixed constant $\beta$ independent of $\varepsilon$, there is an explicit construction of codes which can be uniquely decoded up to an error of half the minimum distance in time $(\log(1/\varepsilon))^{O(1)}\cdot N^{O_{\beta}(1)}$. –For any $\varepsilon > 0$, there are explicit $\varepsilon$ -balanced codes with rate $\Omega(\varepsilon^{2+\beta})$ which can be list decoded up to error $1/2-\varepsilon^{\prime}$ in time $N^{\mathrm{O}_{\varepsilon, \varepsilon^{\prime}, \beta}(1)}$, where $\varepsilon^{\prime}, \beta\rightarrow 0$ as $\varepsilon\rightarrow 0$. The starting point of our algorithms is the framework for list decoding direct-sum codes develop in Alev et al. [SODA 2020], which uses the Sum-of-Squares SDP hierarchy. The rates obtained there were quasipolynomial in $\varepsilon$. Here, we show how to overcome the far from optimal rates of this framework obtaining unique decoding algorithms for explicit binary codes of near optimal rate. These codes are based on simple modifications of Ta-Shma's construction.

FOCS Conference 2019 Conference Paper

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 k > 2 (kCSPs) on instances satisfying certain expansion properties, when viewed as hypergraphs. Random instances of k-CSPs, which are also highly expanding, are well-known to be hard to approximate using known algorithmic techniques (and are widely believed to be hard to approximate in polynomial time). However, we show that this is not necessarily the case for instances where the hypergraph is a high-dimensional expander. We consider the spectral definition of highdimensional expansion used by Dinur and Kaufman [FOCS 2017] to construct certain primitives related to PCPs. They measure the expansion in terms of a parameter γ which is the analogue of the second singular value for expanding graphs. Extending the results by Barak, Raghavendra and Steurer [FOCS 2011] for 2-CSPs, we show that if an instance of MAX k-CSP over alphabet [q] is a high-dimensional expander with parameter γ, then it is possible to approximate the maximum fraction of satisfiable constraints up to an additive error ε using q O(k) · (k/ε) O(1) levels of the sum-of-squares SDP hierarchy, provided γ ≤ ε O(1) · (1/(kq)) O(k). Based on our analysis, we also suggest a notion of threshold-rank for hypergraphs, which can be used to extend the results for approximating 2-CSPs on low threshold-rank graphs. We show that if an instance of MAX k-CSP has threshold rank r for a threshold τ = (ε/k) O(1) · (1/q) O(k), then it is possible to approximately solve the instance up to additive error ε, using r · q O(k) · (k/ε) O(1) levels of the sum-of-squares hierarchy. As in the case of graphs, high-dimensional expanders (with sufficiently small γ) have threshold rank 1 according to our definition.