Research Interests
My research interests lie in theoretical computer science. Currently, I am working on the complexity classification of counting/decision/optimization problems in the Holant (also known as edge-CSP) framework. In particular, 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.
Research Articles
- Contraction:
A Unified Perspective of Correlation Decay and
Zero-Freeness of 2-Spin Systems
with Yuxin Sun
Journal: Journal of Statistical Physics, vol. 185:12, 2021, (DOI).
Conference: International Colloquium on Automata, Languages and Programming (ICALP) 2020, (DOI).
- New
Planar P-time Computable Six-Vertex Models and a
Complete Complexity Classification
with Jin-Yi Cai and Zhiguo Fu
Conference: ACM-SIAM Symposium on Discrete Algorithms (SODA) 2021, (DOI).
- A
Dichotomy for Real Boolean Holant Problems
with Jin-Yi Cai
Conference: IEEE Symposium on Foundations of Computer Science (FOCS) 2020, (DOI).
-
Beyond
#CSP: A Dichotomy for Counting Weighted Eulerian
Orientations with ARS,
with Jin-Yi Cai and Zhiguo Fu
Journal: Information and Computation, vol. 275: 104589, 2020, (DOI).
-
From Holant to Quantum Entanglement and
Back
with Jin-Yi Cai and Zhiguo Fu
Conference: International Colloquium on Automata, Languages and Programming (ICALP) 2020, (DOI).
-
On the Dual of the Coulter-Matthews Bent
Functions
Honggang Hu, Qingsheng Zhang and Shuai Shao3
Journal: IEEE Transactions on Information Theory, vol. 63, pp. 2454 - 2463, 2017, (DOI).
-
The Proof of Lin's Conjecture via the
Decimation Hadamard Transform
Honggang Hu, Shuai Shao2, Guang Gong and Tor Helleseth
Journal: IEEE Transactions on Information Theory, vol. 60, pp. 5054 - 5064, 2014, (DOI).
Conference: IEEE International Symposium on Information Theory (ISIT) 2014, (DOI).
Invited Talks
- A
Dichotomy for Real Boolean Holant Problems
TCS+ Talk Nov. 2020
SIGMA Seminar 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