Papers by Bart Selman
Note: Our most recent work on reasoning technology is
supported by Darpa's
Real-World Reasoning program
(Tom Wagner , PM;
Sri Kumar , former PM).
Can get satisfaction
Carla P. Gomes and Bart Selman
Nature
Vol. 435, June 9, 2005, 751--752. News & Views article,
accompanying
Achlioptas, Naor, and Peres.
The Achilles' Heel of QBF
Carlos Ansotegui, Carla Gomes, and Bart Selman.
Proc. AAAI-05.
Regular Random k-SAT: Properties of balanced formulas
Yacine Boufkhad, Olivier Dubois, Yannet Interian, and Bart Selman.
Journal of Automated Reasoning, 2005.
A New Approach to Model Counting
Wei Wei and Bart Selman.
Proc. SAT-05.
Planning CNFs with small DPLL proofs
Technical report version.
The State of SAT
Henry Kautz and Bart Selman
Discrete and Applied Math, to appear.
Statistical Regimes Across Constrainedness Regions
Carla P. Gomes, Cesar Fernandez, Bart Selman, and Chistian Bessiere
Proc. 10th Intl. Conf. on Principles and Practice of Constraint
Programming (CP-04).
Toronto, Ont., 2004.
Distinguished Paper Award.
Towards Efficient Sampling: Exploiting Random Walk Strategies
Wei Wei, Jordan Erenrich, and Bart Selman
Proc. AAAI-04.
San Jose, CA, 2004.
We introduce algorithm SampleSat to sample approximately uniformly
from the set of satisfying truth assignments of a Boolean formula.
Talk.
Tracking evolving communities in large linked networks
John Hopcroft, Brian Kulis, Omar Khan, and Bart Selman
Proc. Natl. Acad. of Sci.
(PNAS), Febr., 2004.
NSF overview article.
Natural communities in large linked networks
John Hopcroft, Brian Kulis, Omar Khan, and Bart Selman
Proc. KDD,
August, 2003.
Backdoors To Typical Case Complexity
Ryan Williams,
Carla Gomes,
and Bart Selman
Proc. IJCAI-03
Acapulco, Mexico, 2003.
We introduce the notion of a "backdoor" variable of a SAT problem
instance to explain some of the remarkable efficiency of current
SAT solvers on very large instances. The bottom line is that many
real-world instances reduce to a tractable form once a small group
of variables (the "backdoor") is set correctly. Heuristics and
restarts in current solvers are effective at identifying such variables.
Talk. Note: the latest
results on this line of research were presented
at AAAS-05 (Washington, DC).
Introductory remarks for
Nils
Nilsson's Research Excellence award presentation at IJCAI-03.
Animation derived from Nils's teleoreactive
environment.
Communication and computation in distributed CSP algorithms.
Cesar Fernandez, Ramon Bejar, Bhaskar Krishnamachari, Carla Gomes,
and Bart Selman.
In Distributed Sensor Networks, A Multiagent
Perspective. V. Lesser, C.L. Ortiz, Jr., and M. Tambe (Eds.)
Kluwer Academic Publishers, 2003.
A principled study of the design tradeoffs for autonomous trading agents.
Ioannis A. Vetsikas and Bart Selman.
Second International Joint Conference on Autonomous Agents and
Multi-Agent Systems,
Melbourne, 2003. Describes ``Whitebear'' trading agent, winner of the
Trading Agent competition '02 (TAC-02).
See for TAC overview.
Satisfied with Physics
Gomes, Carla and Selman, Bart.
Science,
Vol. 297, Aug. 2, 2002, 784--785. (Perspectives article.)
Accompanying Mezard, Parisi, and
Zecchina.
Accelerating Random Walks.
Wei, Wei and Selman, Bart.
Proceedings of 8th Intl. Conference on the Principles and Practice
of Constraint Programming (CP-2002),
2002.
Dynamic Restart Policies.
Kautz, Henry, Horvitz, Eric, Ruan, Yongshao,
Gomes, Carla, and Selman, Bart.
Proceedings of the Eighteenth National Conference
on Artificial Intelligence (AAAI-02)
Edmonton, Alberta, Canada, 2002, 674--682.
Hill Climbing Search.
Gomes, Carla; and Selman Bart.
Nature Encyclopedia of Cognition,
Nature Publ., 2002.
Algorithm Portfolios
Gomes, Carla and Selman, Bart.
Artificial Intelligence,
Vol. 126 (2001) 43--62.
Formal Models of Heavy-tailed Behavior in Combinatorial Search
Chen, Hubie; Gomes, Carla; and Selman, Bart.
Proceedings of 7th Intl. Conference on the Principles and Practice
of Constraint Programming (CP-2001),
Lecture Notes in Computer Science, Vol. 2239, Springer-Verlag,
2001, 408--422.
A Bayesian Approach to Tackling Hard Computational Problems.
Horvitz, Eric; Ruan, Yonshao; Gomes, Carla; Kautz, Henry; Selman, Bart;
and Chickering, Mark.
Proceedings 17th Conf. on Uncertainty and Artificial
Intelligence (UAI-2001),
Seattle, 2001.
Balance and Filtering in Structured Satisfiable Problems.
Kautz, Henry; Ruan, Yongshoa; Achlioptas, Dimitris; Gomes, Carla;
Selman, Bart; and Stickel, Mark.
Proceedings of the 17th International Conference on Artificial
Intelligence (IJCAI-2001),
Seattle, 2001.
Statistical Physics and Computational Complexity.
Kirkpatrick, Scott and Selman, Bart.
In More is different --- Fifty years of condensed matter physics.
Essays in honor of Nobel Laureate Philip W. Anderson,
Princeton Series in Physics, edited by N. Ong and R. Bhatt, 2001, 331--339.
Note: Research reported in papers from 1998 through 2002, are based
on work supported by a CAREER Award from
the National Science Foundation under Grant No. 9734128.
Any opinions, findings, and conclusions or recommendations expressed in this
material are those of the author(s) and do not necessarily reflect the views
of the National Science Foundation.
Compute-Intensive Methods in Artificial Intelligence
Selman, Bart.
Annals of Mathematics and Artificial Intelligence,
Vol. 28 (2000), 35--41.
Learning Declarative Control Rules for Constraint-Based Planning
Huang, Yi-Cheng; Selman, Bart; and Kautz, Henry.
Proc. ICML-00,
2000.
Heavy-tailed phenomena in satisfiability and constraint satisfaction problems
Gomes, Carla; Selman, Bart; Crato, Nuno; and Kautz, Henry.
J. of Automated Reasoning,
Vol. 24(1/2), 2000, 67-100.
Generating Satisfiable Instances.
Achlioptas, Dimitris; Gomes, Carla; Kautz, Henry; and Selman, Bart.
Proceedings of the Seventeenth National Conference
on Artificial Intelligence (AAAI-00),
Austin, TX, 2000.
Analysis of Random Walk and Random Noise Algorithms for Satisfiability Testing.
Krishnamachari, Bhaskar; Xie, Xi; Selman, Bart; and Wicker, Stephen.
Proceedings of 6th Intl. Conference on the Principles and Practice
of Constraint Programming (CP-2000).
Lecture Notes in Computer Science, Vol. 1894, Springer-Verlag, 2000.
Determining computational complexity from characteristic `phase transitions'.
Monasson, Remi; Zecchina, Riccardo; Kirkpatrick, Scott; Selman, Bart; and
Troyansky, Lidror.
Nature,
Vol. 400(8), 1999, 133--137.
Accompanied by Nature news article
Solving problems in finite time by Philip Anderson.
2+P-SAT: Relation of typical-case complexity to the nature of the
phase transition
Monasson, Remi; Zecchina, Riccardo; Kirkpatrick, Scott; Selman, Bart; and
Troyansky, Lidror.
Random Structures,
1999, 414--435.
Heavy-tailed Distributions in Computational Methods.
Gomes, Carla P. and Selman, Bart.
Proceedings Application of Heavy Tailed Distribution in Economics,
Engineering and Statistics (TAILS-99),
Washington, DC, 1999.
Control knowledge in planning: benefits and tradeoffs.
Huang, Yi-Cheng; Selman, Bart; and Kautz, Henry.
Proc. of the 16th Natl. Conf.
on Artificial Intelligence (AAAI-99),
1999.
Unifying SAT-based and graph-based planners.
Kautz, Henry and Selman, Bart.
Proc. of the 15th Intl. Joint Conf. on Artificial
Intelligence (IJCAI-99).
Greedy local search
Selman, Bart.
In {\em MIT Encyclopedia of the Cognitive Sciences (MITECS)},
Robert A.\ Wilson and Frank C.\ Keil (Eds.)
Cambridge: MIT Press, 1999, 357--359.
Boosting Combinatorial Search Through Randomization
Carla P. Gomes, Bart Selman, and Henry Kautz.
Proc. AAAI-98
, Madison, WI, July 1998.
Randomization in Backtrack Search: Exploiting Heavy-Tailed Profiles
for Solving Hard Scheduling Problems.
Carla P. Gomes, Bart Selman, Ken McAloon, and Carol Tretkoff
Proc. AIPS-98 , Pittsburgh, PA, June 1998.
The Role of Domain-Specific Knowledge in the Planning
as Satisfiability Framework.
Figs. are in separate
.pdf
Henry Kautz and Bart Selman.
Proc. AIPS-98 , Pittsburgh, PA, June 1998.
Problem Structure in the Presence of Perturbations .
Carla P. Gomes and Bart Selman.
Proc. AAAI-97 , Providence, RI., 1997.
Algorithm Portfolio Design: Theory vs. Practice.
Carla P. Gomes and Bart Selman.
Proc. of the Thirteenth Conference On Uncertainty in
Artificial Intelligence (UAI-97) , Providence, RI, 1997./
Stochastic Search
Bart Selman.
Appears in the MIT Encyclopedia of Cognitive Science , forthcoming.
Ten Challenges in Propositional Reasoning and Search
Bart Selman, Henry Kautz, and David McAllester.
Proc. IJCAI-97 , Nagoya, Aichi, Japan, 1997.
Exploiting Variable Dependency in Local Search.
Henry Kautz, David McAllester, and Bart Selman. (draft)
Abstract appears in Abstracts of the Poster Sessions of IJCAI-97 ,
Nagoya, Japan,
1997.
The Hidden Web
Henry Kautz, Bart Selman, and Mehul Shah.
The
AI Magazine , vol. 18, no. 2, Summer 1997, pages 27 - 36.
Evidence for Invariants in Local Search.
David McAllester, Bart Selman, and Henry Kautz.
Proc. AAAI-97 , Providence, RI, 1997.
ReferralWeb: Combining Social Networks and Collaborative Filtering.
Henry Kautz, Bart Selman, and Mehul Shah.
Comm. ACM , vol. 30 no. 3, March 1997.
Local Search Strategies for Satisfiability Testing
Bart Selman and Henry Kautz,
DIMACS Series in Discrete Mathematics. (to appear)
Encoding Plans in Propositional Logic.
Henry Kautz, David McAllester, and Bart Selman.
Proc. KR-96.
Generating Hard Satisfiability Problems.
Selman, Bart; Mitchell, David; and Levesque, Hector.
Artificial Intelligence, Vol. 81, 1996, 17--29.
Pushing the Envelope: Planning, Propositional Logic, and Stochastic Search.
Henry Kautz and Bart Selman,
Proc. AAAI-96.
The Comparative Linguistics of Knowledge Representation.
Goran Gogic, Henry Kautz, Christos Papadimitriou, and Bart Selman,
Proc. IJCAI-95.
Agent Amplified Communication.
Henry Kautz and Bart Selman,
Proc. AAAI-96 (earlier version, AAAI-95 Spring Symposium).
Knowledge Compilation and Theory Approximation.
Bart Selman and Henry Kautzr,
Journal of the ACM , 43(2):193-224, March 1996.
Critical Behavior in the Computational Cost of Satisfiability Testing
Bart Selman and Scott Kirkpatrick,
Artificial Intelligence , 81:273-295, 1996.
Solving Problems with Hard and Soft Constraints Using A Stochastic
Algorithm for MAX-SAT
Yueyun Jiang, Henry Kautz, and Bart Selman,
1st International Joint Workshop on Artificial
Intelligence and Operations Research, 1995.
Horn Approximations of Empirical Data.
Henry Kautz, Michael Kearns, and Bart Selman.
Draft
(near-final) version. Final version appears in
Artificial Intelligence , 74/1 (pp. 129-145) 30 March 1995.
Critical Behavior in the Satisfiability of Random Boolean Expressions.
Scott Kirkpatrick and Bart Selman,
Science , Vol. 264, 1994, 1297--1301.
With Science News
article by Barry Cipra entitled "Pinning
down the Treacherous Border in Logical Statements" .
Noise Strategies for Improving Local Search.
Bart Selman and Henry Kautz,
Proc. AAAI-94.
An Experiment in the Design of Software Agents.
Henry Kautz, Bart Selman, Michael Coen, Steven Ketchpel, and Chris Ramming,
Proc. AAAI-94.
An Empirical Evaluation of Knowledge Compilation.
Henry Kautz and Bart Selman,
Proc. AAAI-94. (Extended version).
GSAT User's Guide.
Henry Kautz and Bart Selman.
Local Search Strategies for Satisfiability Testing.
Bart Selman and Henry Kautz,
Draft.
Domain-Independent Extensions to GSAT: Solving Large
Structured Satisfiability Problems.
Bart Selman and Henry Kautz,
Proc. IJCAI-93.
Reasoning With Characteristic Models.
Henry Kautz, Michael Kearn, Bart Selman,
Proc. AAAI-93.
An Empirical Study of Greedy Local Search for Satisfiability Testing.
Bart Selman and Henry Kautz,
Proc. AAAI-93.
Planning as Satisfiability.
Henry Kautz and Bart Selman,
Proceedings ECAI-92.
Forming Concepts for Fast Inferencer.
Henry Kautz and Bart Selman,
Proceedings AAAI-92.
A General Framework for Knowledge Compilation.
Henry Kautz and Bart Selman,
PDK-91, WOCFAI-91.
Knowledge Compilation Using Horn Approximations.
Bart Selman and Henry Kautz,
Proceedings AAAI-91.
Hard and Easy Distribution of SAT Problems.
David Mitchell, Bart Selman, and Hector Levesque,
Proceedings AAAI-92.
A New Method for Solving Hard Satisfiability Problems.
Bart Selman, Hector Levesque and David Mitchell,
Proceedings AAAI-92.
The free Adobe Acrobat reader for all platforms can be obtained from
Adobe home page .
Back to my personal home page page.
Fri., Febr. 21, 2003.
selman@cs.cornell.edu
