Shuai Shao
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Shuai Shao has a total of 13 co-authors. Here are the top co-authors by number of shared publications:
- Jin-Yi Cai
University of Wisconsin-Madison, Madison, USA
6 shared publications - Zhiguo Fu
Northeast Normal University
4 shared publications - Austen Z. Fan
University of Wisconsin-Madison, Madison, WI, USA
2 shared publications Jin-Yi Cai
Department of Computer Sciences University of Wisconsin
2 shared publications- Stanislav Živný
University of Oxford, Oxford, United Kingdom
2 shared publications - Yuxin Sun
Department of Computer Sciences University of Wisconsin-Madison
2 shared publications
Latest Publications
- Open Access
- 28 September 2026
- Published by Springer Nature in Mathematical Programming
- p. 1
Correction to: Real-weighted general factors on subcubic graphs
- 28 September 2026
- Published by Springer Nature in Mathematical Programming
- p. 1
Open AccessCorrection to: Real-weighted general factors on subcubic graphs
- Open Access
- 14 September 2026
- Published by Springer Nature in Mathematical Programming
- p. 1-44
Real-weighted general factors on subcubic graphs
General factors generalize the concept of graph matchings and have been extensively studied in combinatorial optimization. Given a graph G where each vertex v is assigned a set $$\pi (v)$$ of feasible degrees (called a degree constraint), the general factor problem seeks a (spanning) subgraph F of G such that $$\deg _F(v) \in \pi (v)$$ for all v of G . When all degree constraints are symmetric $$\Delta $$ -matroids, the problem is solvable in polynomial-time. The weighted general factor problem further extends this by incorporating edge weights, and the goal is to find a general factor that maximizes the total weight in an edge-weighted graph. In this paper, we propose a strongly polynomial-time algorithm for the real-weighted general factor problem on subcubic graphs by establishing a refined structural result that ensures the optimality of weighted graph factors. As an application of our result, we obtain a strongly polynomial-time algorithm for the terminal backup problem, a variant of the Steiner tree problem. Furthermore, we provide a characterization theorem for matching-gadget realizable degree constraints.- 14 September 2026
- Published by Springer Nature in Mathematical Programming
- p. 1-44
Open AccessReal-weighted general factors on subcubic graphs
General factors generalize the concept of graph matchings and have been extensively studied in combinatorial optimization. Given a graph G where each vertex v is assigned a set $$\pi (v)$$ of feasible degrees (called a degree constraint), the general factor problem seeks a (spanning) subgraph F of G such that $$\deg _F(v) \in \pi (v)$$ for all v of G . When all degree constraints are symmetric $$\Delta $$ -matroids, the problem is solvable in polynomial-time. The weighted general factor problem further extends this by incorporating edge weights, and the goal is to find a general factor that maximizes the total weight in an edge-weighted graph. In this paper, we propose a strongly polynomial-time algorithm for the real-weighted general factor problem on subcubic graphs by establishing a refined structural result that ensures the optimality of weighted graph factors. As an application of our result, we obtain a strongly polynomial-time algorithm for the terminal backup problem, a variant of the Steiner tree problem. Furthermore, we provide a characterization theorem for matching-gadget realizable degree constraints. - Open Access
- 28 June 2026
- Published by Elsevier in Information and Computation
- Vol. 312
Eulerian orientations and Hadamard codes: A novel connection via counting
- 28 June 2026
- Published by Elsevier in Information and Computation
- Vol. 312
Open AccessEulerian orientations and Hadamard codes: A novel connection via counting
- Open Access
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 967-978
New Planar Algorithms and a Full Complexity Classification of the Eight-Vertex Model
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 967-978
Open AccessNew Planar Algorithms and a Full Complexity Classification of the Eight-Vertex Model
- Open Access
New Planar Algorithms and a Full Complexity Classification of the Eight-Vertex Model
We prove a complete complexity classification theorem for the planar eight-vertex model. For every parameter setting in ${\mathbb C}$ for the eight-vertex model, the partition function is either (1) computable in P-time for every graph, or (2) \#P-hard for general graphs but computable in P-time for planar graphs, or (3) \#P-hard even for planar graphs. The classification has an explicit criterion. In (2), we discover new P-time computable eight-vertex models on planar graphs beyond Kasteleyn's algorithm for counting planar perfect matchings. They are obtained by a combinatorial transformation to the planar {\sc Even Coloring} problem followed by a holographic transformation to the tractable cases in the planar six-vertex model. In the process, we also encounter non-local connections between the planar eight vertex model and the bipartite Ising model, conformal lattice interpolation and Möbius transformation from complex analysis. The proof also makes use of cyclotomic fields.Open AccessNew Planar Algorithms and a Full Complexity Classification of the Eight-Vertex Model
We prove a complete complexity classification theorem for the planar eight-vertex model. For every parameter setting in ${\mathbb C}$ for the eight-vertex model, the partition function is either (1) computable in P-time for every graph, or (2) \#P-hard for general graphs but computable in P-time for planar graphs, or (3) \#P-hard even for planar graphs. The classification has an explicit criterion. In (2), we discover new P-time computable eight-vertex models on planar graphs beyond Kasteleyn's algorithm for counting planar perfect matchings. They are obtained by a combinatorial transformation to the planar {\sc Even Coloring} problem followed by a holographic transformation to the tractable cases in the planar six-vertex model. In the process, we also encounter non-local connections between the planar eight vertex model and the bipartite Ising model, conformal lattice interpolation and Möbius transformation from complex analysis. The proof also makes use of cyclotomic fields. - Open Access
Beyond AME: A Novel Connection between Quantum Secret Sharing Schemes and $k$-Uniform States
We study the connection between quantum secret sharing (QSS) schemes and $k$-uniform states of qubits beyond the equivalence between threshold QSS schemes and AME states. Specifically, we focus on homogeneous access structures and show that $3$-uniformity is a necessary but not sufficient condition for constructing a $3$-homogeneous QSS scheme using states of qubits. This gives a novel connection between non-threshold QSS schemes and $k$-uniform states. As an application of our result, we classify QSS schemes for up to 7 players and provide explicit characterizations of their existence. Our results offer new insights into the role of $k$-uniform states in the design of QSS schemes (not necessarily threshold) and provide a foundation for future classifications of QSS schemes with more complex structures.
Open AccessBeyond AME: A Novel Connection between Quantum Secret Sharing Schemes and $k$-Uniform States
We study the connection between quantum secret sharing (QSS) schemes and $k$-uniform states of qubits beyond the equivalence between threshold QSS schemes and AME states. Specifically, we focus on homogeneous access structures and show that $3$-uniformity is a necessary but not sufficient condition for constructing a $3$-homogeneous QSS scheme using states of qubits. This gives a novel connection between non-threshold QSS schemes and $k$-uniform states. As an application of our result, we classify QSS schemes for up to 7 players and provide explicit characterizations of their existence. Our results offer new insights into the role of $k$-uniform states in the design of QSS schemes (not necessarily threshold) and provide a foundation for future classifications of QSS schemes with more complex structures.
- Open Access
Zero-Freeness is All You Need: A Weitz-Type FPTAS for the Entire Lee-Yang Zero-Free Region
We present a Weitz-type FPTAS for the ferromagnetic Ising model across the entire Lee-Yang zero-free region, without relying on the strong spatial mixing (SSM) property. Our algorithm is Weitz-type for two reasons. First, it expresses the partition function as a telescoping product of ratios, with the key being to approximate each ratio. Second, it uses Weitz's self-avoiding walk tree, and truncates it at logarithmic depth to give a good and efficient approximation. The key difference from the standard Weitz algorithm is that we approximate a carefully designed edge-deletion ratio instead of the marginal probability of a vertex's spin, ensuring our algorithm does not require SSM. Furthermore, by establishing local dependence of coefficients (LDC), we indeed prove a novel form of SSM for these edge-deletion ratios, which, in turn, implies the standard SSM for the random cluster model. This is the first SSM result for the random cluster model on general graphs, beyond lattices. We prove LDC using a new division relation, and remarkably, such relations hold quite universally. As a result, we establish LDC for a variety of models. Combined with existing zero-freeness results for these models, we derive new SSM results for them. Our work suggests that both Weitz-type FPTASes and SSM can be derived from zero-freeness, while zero-freeness alone suffices for Weitz-type FPTASes, SSM additionally requires LDC, a combinatorial property independent of zero-freeness.
Open AccessZero-Freeness is All You Need: A Weitz-Type FPTAS for the Entire Lee-Yang Zero-Free Region
We present a Weitz-type FPTAS for the ferromagnetic Ising model across the entire Lee-Yang zero-free region, without relying on the strong spatial mixing (SSM) property. Our algorithm is Weitz-type for two reasons. First, it expresses the partition function as a telescoping product of ratios, with the key being to approximate each ratio. Second, it uses Weitz's self-avoiding walk tree, and truncates it at logarithmic depth to give a good and efficient approximation. The key difference from the standard Weitz algorithm is that we approximate a carefully designed edge-deletion ratio instead of the marginal probability of a vertex's spin, ensuring our algorithm does not require SSM. Furthermore, by establishing local dependence of coefficients (LDC), we indeed prove a novel form of SSM for these edge-deletion ratios, which, in turn, implies the standard SSM for the random cluster model. This is the first SSM result for the random cluster model on general graphs, beyond lattices. We prove LDC using a new division relation, and remarkably, such relations hold quite universally. As a result, we establish LDC for a variety of models. Combined with existing zero-freeness results for these models, we derive new SSM results for them. Our work suggests that both Weitz-type FPTASes and SSM can be derived from zero-freeness, while zero-freeness alone suffices for Weitz-type FPTASes, SSM additionally requires LDC, a combinatorial property independent of zero-freeness.
- Open Access
- 26 October 2021
- Published by Springer Nature in Journal of Statistical Physics
- Vol. 185 (2) , 1-25
Contraction: A Unified Perspective of Correlation Decay and Zero-Freeness of 2-Spin Systems
We study the connection between the correlation decay property (more precisely, strong spatial mixing) and the zero-freeness of the partition function of 2-spin systems on graphs of bounded degree. We show that for 2-spin systems on an entire family of graphs of a given bounded degree, the contraction property that ensures correlation decay exists for certain real parameters implies the zero-freeness of the partition function and the existence of correlation decay for some corresponding complex neighborhoods. Based on this connection, we are able to extend any real parameter of which the 2-spin system on graphs of bounded degree exhibits correlation decay to its complex neighborhood where the partition function is zero-free and correlation decay still exists. We give new zero-free regions in which the edge interaction parameters and the uniform external field are all complex-valued, and we show the existence of correlation decay for such complex regions. As a consequence, we obtain approximation algorithms for computing the partition function of 2-spin systems on graphs of bounded degree for these complex parameter settings.
- 26 October 2021
- Published by Springer Nature in Journal of Statistical Physics
- Vol. 185 (2) , 1-25
Open AccessContraction: A Unified Perspective of Correlation Decay and Zero-Freeness of 2-Spin Systems
We study the connection between the correlation decay property (more precisely, strong spatial mixing) and the zero-freeness of the partition function of 2-spin systems on graphs of bounded degree. We show that for 2-spin systems on an entire family of graphs of a given bounded degree, the contraction property that ensures correlation decay exists for certain real parameters implies the zero-freeness of the partition function and the existence of correlation decay for some corresponding complex neighborhoods. Based on this connection, we are able to extend any real parameter of which the 2-spin system on graphs of bounded degree exhibits correlation decay to its complex neighborhood where the partition function is zero-free and correlation decay still exists. We give new zero-free regions in which the edge interaction parameters and the uniform external field are all complex-valued, and we show the existence of correlation decay for such complex regions. As a consequence, we obtain approximation algorithms for computing the partition function of 2-spin systems on graphs of bounded degree for these complex parameter settings.
- Open Access
New Planar P-time Computable Six-Vertex Models and a Complete Complexity Classification
We discover new P-time computable six-vertex models on planar graphs beyond Kasteleyn's algorithm for counting planar perfect matchings. We further prove that there are no more: Together, they exhaust all P-time computable six-vertex models on planar graphs, assuming #P is not P. This leads to the following exact complexity classification: For every parameter setting in ${\mathbb C}$ for the six-vertex model, the partition function is either (1) computable in P-time for every graph, or (2) #P-hard for general graphs but computable in P-time for planar graphs, or (3) #P-hard even for planar graphs. The classification has an explicit criterion. The new P-time cases in (2) provably cannot be subsumed by Kasteleyn's algorithm. They are obtained by a non-local connection to #CSP, defined in terms of a "loop space". This is the first substantive advance toward a planar Holant classification with not necessarily symmetric constraints. We introduce M\"obius transformation on ${\mathbb C}$ as a powerful new tool in hardness proofs for counting problems.Open AccessNew Planar P-time Computable Six-Vertex Models and a Complete Complexity Classification
We discover new P-time computable six-vertex models on planar graphs beyond Kasteleyn's algorithm for counting planar perfect matchings. We further prove that there are no more: Together, they exhaust all P-time computable six-vertex models on planar graphs, assuming #P is not P. This leads to the following exact complexity classification: For every parameter setting in ${\mathbb C}$ for the six-vertex model, the partition function is either (1) computable in P-time for every graph, or (2) #P-hard for general graphs but computable in P-time for planar graphs, or (3) #P-hard even for planar graphs. The classification has an explicit criterion. The new P-time cases in (2) provably cannot be subsumed by Kasteleyn's algorithm. They are obtained by a non-local connection to #CSP, defined in terms of a "loop space". This is the first substantive advance toward a planar Holant classification with not necessarily symmetric constraints. We introduce M\"obius transformation on ${\mathbb C}$ as a powerful new tool in hardness proofs for counting problems. - 1 December 2020
- Published by Elsevier in Information and Computation
- Vol. 275
Beyond #CSP: A dichotomy for counting weighted Eulerian orientations with ARS
- 1 December 2020
- Published by Elsevier in Information and Computation
- Vol. 275
Beyond #CSP: A dichotomy for counting weighted Eulerian orientations with ARS