Ke Xu

Professor of Computer Science
National Laboratory of Software Development Environment
Department of Computer Science and Engineering
Beihang University (Beijing University of Aeronautics and Astronautics)
Beijing, 100083, P. R. China

Email: kexu AT buaa.edu.cn / kexu999 AT gmail.com

Research Interests

Aircraft Design and Structural Analysis (previously)
Design and Analysis of Algorithms
Phase Transitions in NP-Complete Problems
Constraint Satisfaction Problem (CSP)
The Satisfiability Problem (SAT)
Logic and Complexity
Logic Programming
Data Mining
Combinatorics and Random Graphs
Cryptography Based on NP-hard Problems
Network Measurement, Modeling and Analysis

Selected Papers about Model RB

Ke Xu and Wei Li. Exact Phase Transitions in Random Constraint Satisfaction Problems. Journal of Artificial Intelligence Research, 12(2000):93-103.

Ke Xu and Wei Li. Many Hard Examples in Exact Phase Transitions. Theoretical Computer Science, 355(2006):291-302. Earlier version: CoRR Report cs.CC/0302001, Feb. 2003.

Ke Xu, Frederic Boussemart, Fred Hemery and Christophe Lecoutre. Random Constraint Satisfaction: Easy Generation of Hard (Satisfiable) Instances. Artificial Intelligence, 171(2007):514-534. Earlier version appeared in Proc. of 19th IJCAI, pp.337-342, Scotland, 2005.

Ke Xu and Guangyan Zhou. SAT Requires Exhaustive Search. Frontiers of Computer Science, Volume 19, article number 1912405, (2025).

Ke Xu and Guangyan Zhou. Self-reference as key to proving extreme hardness——Reply to the comment by Allender and Williams.

Benchmarks Based on Model RB

Several benchmark collections developed by Ke Xu:

Games Based on Model RB

A Game of Numbers Based on Model RB
An Online Java Game Based on Model RB
An Android Game Based on Model RB