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). Before that, I was a postdoc at the University of Edinburgh, and a postdoc and junior research fellow at the University of Oxford.

I got my Ph.D., an M.A. in Math, and an M.Sc in CS from the University of Wisconsin at Madison, where I was fortunate to be supervised by Prof. Jin-Yi Cai. 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.

Teaching

  •     Combinatorics     Spring 24, Fall 23, Fall 22
  •     Discrete Mathematics     Fall 24, Fall 23
  •     Foundations of Algorithms     Spring 23 (with Xue Chen)

Students

  •     Yuan Chen,    since 2024.
  •     Jincheng Guan,     since 2024.
  •     Ji Huang,    since 2023.
  •     Ke Shi,    since 2023.
  •     Bohan Wang,    since 2024.
  •     Zhuxiao Tang,    BSc 2024 (毕设校优) -> PhD student@UW-Madison.
  •     Xiaowei Ye,    BSc 2023 (ICBS best poster award) -> graduate@École Polytechnique.

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   

Contact

Email: shao10 AT ustc.edu.cn