Bart Selman

Associate Professor
Ph.D. University of Toronto, 1991

I’m interested in the development of new formalisms and methods for artificial intelligence (AI) by combining a sound theoretical approach with a principled experimental component. I focus on compute-intensive

methods for AI. Traditionally, general search and reasoning is largely avoided in AI by explicitly incorporating large amounts of domain-specific knowledge. While such a knowledge-intensive approach has been successful in certain domains, such as automatic diagnosis, in other areas, such as planning or general reasoning, progress has been disappointing. However, recent advances in general search and reasoning methods combined with faster hardware and better implementations provide strong evidence that a compute-intensive approach is not only suitable for dealing with the combinatorial nature of many AI formalisms, but may also be required to supplement domain-specific knowledge, especially considering the knowledge-acquisition bottleneck in terms of encoding highly specific domain knowledge.

Part of my research is on fast general reasoning and search techniques, with an emphasis on stochastic methods. I also investigate the various sources of complexity in hard computational problems, using both theoretical and experimental methods. This work explores interesting connections between computer science, artificial intelligence, and statistical physics. In addition, I study issues in problem representation, including the robustness of encodings, abstraction, compilation, and approximation methods. These issues are critical to the successful application in realistic domains of reason ing and search methods. In terms of applications, I am particularly interested in challenge problems from planning, knowledge representation, machine learning, and data mining. Our planning system, BlackBox, developed jointly with Henry Kautz of AT&T Laboratories, is one of the fastest general purpose planning systems. I also pursue applications in areas outside AI, such as operations research and software/protocol verification.


Fellow: American Association for Artificial Intelligence.

Alfred P. Sloan Research Fellowship (1999-2001).

NSF Faculty Early Career Development Award (1998-2002).

University Activities

Member: Ph.D. Admissions Committee; Cognitive Studies Undergraduate Committee.

Coordinator: AI Seminar Series.

Chair: Bits On Our Mind Science Fair. Member: Field of Cognitive Studies.

Professional Activities

Member: Executive Council of the American Association for Intelligence (elected in ’99).

Member: DARPA Information Science and Technology Study Group on Probabilistic Methods in Computational Systems and Infrastructure; DARPA Information Science and Technology Study Group on Self-Configuring Wireless Sensor Networks.

Editorial Board Member: Constraints: An International Journal; Annals of Mathematics and Artificial Intelligence; special issue of Journal of Automated Reasoning.

Advisory Board Member: Journal of Artificial Intelligence Research (JAIR).

Guest Editor: Theoretical Computer Science.

Program Committee Member: The 17th National Conference on Artificial Intelligence (AAAI00); The 16th Conference on Uncertainty in Artificial Intelligence (UAI00); Computational Logic 2000; Symposium on Abstraction, Reformulation and Approximation (SARA 2000).

Referee/Reviewer: Artificial Intelligence Journal (AIJ); JACM; Constraints: An International Journal; Journal of Artificial Intelligence Research (JAIR); Journal of Automated Reasoning; Theoretical Computer Science; Science.


Insights from Statistical Physics into Computational Complexity. Lecture in honor of Nobel Laureate P.W. Anderson, Aspen Center for Physics, Aspen, CO, January 2000.

Satisfiability Testing: Recent Developments and Challenge Problems. Invited plenary talk. IEEE Symposium on Logic in Computer Science (LICS-2000), Santa Barbara, CA, June 2000.

Understanding Complexity: Recent Developments and Directions in Artificial Intelligence. Massachusetts Institute of Technology, November 1999.

—. Center for Applied Mathematics, Cornell University, December 1999.

—. Dept. of Computer Science, Cornell University, January 2000.

—. Distinguished Lecture Series. University of California, Dept. of Computer Science, San Diego, CA, February 2000.

—. Information Sciences Institute, University of Southern California ISI, March 2000.

—. Broad Area Colloquium for Artificial Intelligence, Geometry, Graphics, Robotics and Vision. Stanford University, March 2000.

—. Physics Colloquium, Syracuse University, Syracuse, NY, May 2000.

Understanding Problem Hardness. DARPA/ISAT study group, UC Berkeley, Berkeley, CA, April 2000.

Computational Complexity and Statistical Physics. Lectures at the Summer School on Statistical Physics and Probabilistic Methods in Computer Science.

International Centre for Theoretical Physics, Trieste, Italy, August 1999.


“Determining computational complexity from characteristic ‘phase transitions’.” Nature 400(8), (July 1999), 133-137 (with R. Monasson, S. Kirkpatrick, L. Troyansky, and R. Zecchina). Results featured in The New York Times, Science Section (July 13, 1999), and Science News (May 2000).

“Search strategies for hybrid search spaces.” Proc. of the International Conference on Tools for Artificial Intelligence (ICTAI-99) (1999), Chicago, 359-364 (with C. Gomes).

“Heavy-tailed phenomena in satisfiability and constraint satisfaction problems.” Journal of Automated Reasoning 24(1/2) (2000), 67-100 (with C. Gomes, N. Crato, and H. Kautz). Results featured in Science News (May 2000).

“Learning Declarative Control Rules for Constraint-Based Planning.” 17th International Conference on Machine Learning (ICML-2000) (2000), 415-422 (with Y. Huang and H. Kautz).

“Hybrid strategies for heterogeneous search spaces.” International Journal on Artificial Intelligence Tools (2000) (with C. Gomes).

“Generating satisfiable problem instances.” 12th National Conference on Artificial Intelligence (AAAI-2000) 2000, 256-301 (with D. Achlioptas, C. Gomes, and H. Kautz).

“Algorithm Portfolios.” Artificial Intelligence (2000) (with C. Gomes).

“Encoding Domain and Control Knowledge for Propositional Planning.” Logic-Based Artificial Intelligence (2000), Minker, J., (Ed.), Kluwer Academic Publishers, 355-362.

“Insights from Statistical Physics into Computational Complexity.” Lectures in honor of Nobel Laureate P.W. Anderson (2000), R.N. Bhatt and N. Phuan Ong (Eds.), Princeton University Press (with S. Kirkpatrick).