Graph neural networks (GNNs) have recently emerged as powerful tools for solving complex optimization problems, often being employed to approximate solution mappings. Empirical evidence shows that even shallow GNNs (with fewer than ten layers) can achieve strong performance in predicting optimal solutions to linear programming (LP) problems. This finding is somewhat counter-intuitive, as LPs are global optimization problems, while shallow GNNs predict based on local information. Although previous theoretical results suggest that GNNs have the expressive power to solve LPs, they require deep architectures whose depth grows at least polynomially with the problem size, and thus leave the underlying principle of this empirical phenomenon still unclear. In this paper, we examine this phenomenon through the lens of distributed computing and average-case analysis. We establish that the expressive power of GNNs for LPs is closely related to well-studied distributed algorithms for LPs. Specifically, we show that any $d$-round distributed LP algorithm can be simulated by a $d$-depth GNN, and vice versa. In particular, by designing a new distributed LP algorithm and then unrolling it, we prove that constant-depth, constant-width GNNs suffice to solve sparse binary LPs effectively. Here, in contrast with previous analyses focusing on worst-case scenarios, in which we show that GNN depth must increase with problem size by leveraging an impossibility result about distributed LP algorithms, our analysis shifts the focus to the average-case performance, and shows that constant GNN depth then becomes sufficient no matter how large the problem size is. Our theory is validated by numerical results.

Tanner codes are error-correcting codes built from a bipartite graphGand a short inner codeC0. Expander codes are a special type of Tanner code, where the graph is highly interconnected, ensuring stronger error correction capabilities. This paper is motivated by the following natural and fundamental problem in decoding expander codes: What are the sufficient and necessary conditions that δ ∈ [0, 1] andd0∈ N must satisfy, so thateverybipartite expanderGwith vertex expansion ratio δ andeverylinear inner codeC0with minimum distanced0together define an expander code that corrects Ω(n) errors inO(n) time? ForC0being the parity-check code, the landmark work of Sipser and Spielman (IEEE-TIT’96) showed that δ > 3/4 is sufficient; later, Viderman (ACM-TOCT’13) improved this to δ > 2/3 - Ω(1) and he also showed that δ > 1/2 is necessary. For general linear codeC0, the previously best-known result of Dowling and Gao (IEEE-TIT’18) showed thatd0= Ω(cδ-2) is sufficient, wherecis the left-degree ofG. We present a near-optimal solution to the above problem for generalC0by showing that δd0> 3 is sufficient and δd0> 1 is necessary, thereby significantly improving Dowling-Gao’s result. To prove the sufficient condition, we present two novel algorithms for decoding arbitrary expander codes withδd0> 3, where the first algorithm is deterministic, and the second one is randomized and has a larger decoding radius. To prove the necessary condition, we generalize the aforementioned necessary result of Viderman, and construct for every pair of δ,d0with δd0=1, an expander code with constant distance, that only corrects a constant number of errors.

Tanner codes are graph-based linear codes whose parity-check matrices can be characterized by a bipartite graph $G$ together with a linear inner code $C_0$. Expander codes are Tanner codes whose defining bipartite graph $G$ has good expansion property. This paper is motivated by the following natural and fundamental problem in decoding expander codes: What are the sufficient and necessary conditions that $δ$ and $d_0$ must satisfy, so that \textit{every} bipartite expander $G$ with vertex expansion ratio $δ$ and \textit{every} linear inner code $C_0$ with minimum distance $d_0$ together define an expander code that corrects $Ω(n)$ errors in $O(n)$ time? For $C_0$ being the parity-check code, the landmark work of Sipser and Spielman (IEEE-TIT'96) showed that $δ>3/4$ is sufficient; later Viderman (ACM-TOCT'13) improved this to $δ>2/3-Ω(1)$ and he also showed that $δ>1/2$ is necessary. For general linear code $C_0$, the previously best-known result of Dowling and Gao (IEEE-TIT'18) showed that $d_0=Ω(cδ^{-2})$ is sufficient, where $c$ is the left-degree of $G$. In this paper, we give a near-optimal solution to the above question for general $C_0$ by showing that $δd_0>3$ is sufficient and $δd_0>1$ is necessary, thereby also significantly improving Dowling-Gao's result. We present two novel algorithms for decoding expander codes, where the first algorithm is deterministic, and the second one is randomized and has a larger decoding radius.

This paper presents a distributed algorithm in the CONGEST model that achieves a $(1+ε)$-approximation for row-sparse fractional covering problems (RS-FCP) and the dual column-sparse fraction packing problems (CS-FPP). Compared with the best-known $(1+ε)$-approximation CONGEST algorithm for RS-FCP/CS-FPP developed by Kuhn, Moscibroda, and Wattenhofer (SODA'06), our algorithm is not only much simpler but also significantly improves the dependency on $ε$.

Graph neural networks (GNNs) have recently emerged as powerful tools for addressing complex optimization problems. It has been theoretically demonstrated that GNNs can universally approximate the solution mapping functions of linear programming (LP) problems. However, these theoretical results typically require GNNs to have large parameter sizes. Conversely, empirical experiments have shown that relatively small GNNs can solve LPs effectively, revealing a significant discrepancy between theoretical predictions and practical observations. In this work, we aim to bridge this gap by providing a theoretical foundation for the effectiveness of small-size GNNs. We prove that polylogarithmic-depth, constant-width GNNs are sufficient to solve packing and covering LPs, two widely used classes of LPs. Our proof leverages the capability of GNNs to simulate a variant of the gradient descent algorithm on a carefully selected potential function. Additionally, we introduce a new GNN architecture, termed GD-Net. Experimental results demonstrate that GD-Net significantly outperforms conventional GNN structures while using fewer parameters.

We study the classical expander codes, introduced by Sipser and Spielman, (1996). Given any constants$0 < \alpha, \varepsilon < 1/2$, and an arbitrary bipartite graph with$N$vertices on the left,$M < N$vertices on the right, and left degree$D$such that any left subset$S$of size at most$\alpha N$has at least$(1- \varepsilon)|S|D$neighbors, we show that the corresponding linear code given by parity checks on the right has distance at least roughly$\frac {\alpha N}{2 \varepsilon }$. This is strictly better than the best known previous result of$2(1- \varepsilon) \alpha N$Sudan, (2000), Viderman, (2013) whenever$\varepsilon < 1/2$, and improves the previous result significantly when$\varepsilon $is small. Furthermore, we show that this distance is tight in general, thus providing a complete characterization of the distance of general expander codes. Next, we provide several efficient decoding algorithms, which vastly improve previous results in terms of the fraction of errors corrected, whenever$\varepsilon < \frac {1}{4}$. Finally, we also give a bound on the list-decoding radius of general expander codes, which beats the classical Johnson bound in certain situations (e.g., when the graph is almost regular and the code has a high rate). Our techniques exploit novel combinatorial properties of bipartite expander graphs. In particular, we establish a new size-expansion tradeoff, which may be of independent interests.

We study the classical expander codes, introduced by Sipser and Spielman \cite{SS96}. Given any constants $0< α, \varepsilon < 1/2$, and an arbitrary bipartite graph with $N$ vertices on the left, $M < N$ vertices on the right, and left degree $D$ such that any left subset $S$ of size at most $αN$ has at least $(1-\varepsilon)|S|D$ neighbors, we show that the corresponding linear code given by parity checks on the right has distance at least roughly $\frac{αN}{2 \varepsilon }$. This is strictly better than the best known previous result of $2(1-\varepsilon ) αN$ \cite{Sudan2000note, Viderman13b} whenever $\varepsilon < 1/2$, and improves the previous result significantly when $\varepsilon $ is small. Furthermore, we show that this distance is tight in general, thus providing a complete characterization of the distance of general expander codes. Next, we provide several efficient decoding algorithms, which vastly improve previous results in terms of the fraction of errors corrected, whenever $\varepsilon < \frac{1}{4}$. Finally, we also give a bound on the list-decoding radius of general expander codes, which beats the classical Johnson bound in certain situations (e.g., when the graph is almost regular and the code has a high rate). Our techniques exploit novel combinatorial properties of bipartite expander graphs. In particular, we establish a new size-expansion tradeoff, which may be of independent interests.