SSShuai Shao

Shuai Shao

*This is an algorithmically generated author record based on publicly available information.

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


Shuai Shao has a total of 13 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Real-weighted general factors on subcubic graphs

    by Shuai Shao, Stanislav Zivný

    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)$$ π ( 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)$$ deg F ( v ) ∈ π ( 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

    New Planar Algorithms and a Full Complexity Classification of the Eight-Vertex Model

    by Austen Fan, Jin-Yi Cai, Shuai Shao, Zhuxiao Tang

    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

    by Xuhong Liu, Shuai Shao

    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

    by Shuai Shao, Ke Shi

    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

    Contraction: A Unified Perspective of Correlation Decay and Zero-Freeness of 2-Spin Systems

    by Shuai Shao, Yuxin Sun

    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

    by Jin-Yi Cai, Zhiguo Fu, Shuai Shao

    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.