Sixue Liu
Institute for Interdisciplinary Information Sciences

Address: Institute for Theoretical Computer Science, Tsinghua University

This page was out-dated since 2017 March.


I'll be a Ph.D student in Princeton CS, please visit my new homepage.

Research Interests

I'm particularly interested in formal methods and computational complexity. Specifically, I care about SAT including its random satisfiablity, hard generating models, worst-case upper bounds and practical solvers. I'm also interested in SMT solving and derandomization of probabilistic algorithms.


1. Sixue Liu, Gerard de Melo: Should Algorithms for Random SAT and MaxSAT be Different? 31th AAAI Conference on Artificial Intelligence (AAAI 2017)pdfOral Presentation.

2. Sixue Liu, Periklis A. Papakonstantinou: Local Search for Hard SAT Formulas: the Strength of the Polynomial Law. 30th AAAI Conference on Artificial Intelligence (AAAI 2016)pdf.



1. Sixue Liu: Solving 3- Satisfiability in O*(1.328^n) Steps. pdf.

2. Sixue Liu, Yulong Ceng, Gerard de Melo: A Probability Distribution Strategy with Efficient Clause Selection for Hard Max-SAT Formulas. pdf.

3. Sixue Liu : An Efficient Implementation for WalkSAT. pdf. github.



1. Gordon Y.S. Wu Fellowship in Engineering. Princeton University, 2017

2. 4th and 5th places in random track. SAT Competition, 2016

3. Meritorious Prize in the USA Mathematical Contest in Modeling (top 11% teams). 2012

4. Bronze Medal in ACM International Collegiate Programming Contest. 2011

5. Top 30 in Baidu Astar Programming Contest (top 30/40,000) . 2011



1. I started an internship in Microsoft Research, Redmond in December 2016, working with Nikolaj Bjorner.

2. In SAT Competition 2016, my solvers PolyPower1.0 and PolyPower2.0 (based on our AAAI'16 paper) placed 4th and 5th in random track respectively.