Shuai Shao,邵帅 (中文主页)

I am a faculty member in the School of Computer Science and Technology at the University of Science and Technology of China (USTC, my Alma Mater). Prior to that, I was a postdoc in the group of Prof. Heng Guo at Edinburgh, and a postdoc in the group of Prof. Standa Živný and junior research fellow in Wolfson College at Oxford.

I got my Ph.D. degree from the University of Wisconsin at Madison, where I was fortunate to be supervised by Prof. Jin-Yi Cai. I also got an M.A. degree in mathematics and an M.Sc degree in computer sciences from UW-Madison. I got my B.Sc. degree in the HUA Loo-Keng talent program in mathematics (honors program) from the School of the Gifted Young, USTC.

Research Interests

My research interests lie in theoretical computer science. Currently, I focus on the complexity classification of counting/decision/optimization problems in the Holant (also known as the edge-CSP) framework. I am thrilled to explore the connections between Holant problems and quantum theory. I am also interested in approximate counting algorithms and their connections with the phenomenon of phase transitions in statistical physics.

I am glad to work with self-motivated students with strong background in theoretical computer science, statistical physics, quantum theory, and/or any fields of mathematics. Send me an email if you are interested in doing an undergraduate project (国创/大研) or a master/PhD thesis with me.


  • Combinatorics     Spring 24, Fall 23, Fall 22

  • Discrete Mathematics     Fall 23

  • Foundations of Algorithms     Spring 23 (with Xue Chen)

Research Articles

Invited Talks

  • Weitz's Algorithm Revisted via Barvinok's Interpolation Method
         IJTCS 2023, University of Macau           Aug. 2023   

  • A Strongly Polynomial-Time Algorithm for Weighted General Factors
         CCF NCTCS, Northeast Normal University           July. 2022   

  • A Dichotomy for Real Boolean Holant Problems
         TCS+ Talk                                                             Nov. 2020
         SIGMA Seminar, Institute of Computing Technology, CAS           Oct. 2020
  • On the Complexity of Holant Problems
         Theory Seminar, Institute of Software, CAS        Jan. 2020      

  • Complexity Classification of Six-Vertex Models
         China Theory Week, Tsinghua University           Sept. 2018   


Email: shao10 AT