*A New Approach to Model Counting*

Wei Wei and Bart Selman

*Eighth International Conference on Theory and Applications of Satisfiability Testing*, St. Andrews, Scotland, 2005

We introduce ApproxCount, an algorithm that approximate the number of satisfying assignment of a Boolean formula. Many AI tasks, such as reasoning in Bayesian belief networks, can be reduced to this problem. Our algorithm produces estimates of model counts of formulas much larger than those can be handled by existing algorithms.

*Towards Efficient Sampling: Exploiting Random Walk Strategies*

Wei Wei, Jordan Erenrich, and Bart Selman

*The Nineteenth National Conference on Artificial Intelligence*, San Jose, CA, 2004

We show that random walk style procedures provide a promising technique for sampling from the set of satisfying assignments. Moreover, we demonstrate by combining random walk and Monte Carlo Markov Chain methods how one can get approximately uniform sampling in a number of domains.

*Learn to Speed Up Search*

Bart Selman and Wei Wei

*AAAI 2002 Workshop on Probabilistic Approaches in Search*, Edmonton, Alberta, Canada, 2002

We survey several promising approaches of integrating machine learning techniques into search algorithms. The general methodology of these approaches is to use learning techniques to uncover the hidden structure of the search space, and then use this information to speed up search.

*Accelerating Random Walks*

Wei Wei and Bart Selman

*Eighth International Conference on Principles and Practice of Constraint Programming*, Ithaca, NY, 2002

The algorithm proposed in this paper identifies long distance dependencies among variables in the underlying problem instance. By adding new problem constraints, we made these dependencies explicit, and literally speed up random walk style search in the structured domains.

*Learn to Speed Up Search*, AAAI 2002 Workshop on Probabilistic Approaches in Search, Edmonton, Alberta, Canada, 2002

*Accelerating Random Walks*, Eighth International Conference on Principles and Practice of Constraint Programming, Ithaca, New York, USA, 2002

*Sampling Combinatorial Space Using Biased Random Walks*, Eighteenth International Joint Conference on Artificial Intelligence, Acapulco, Mexico, 2003*Learn to Walk Faster*, AI seminar, Cornell University, 2003

*Towards Efficient Sampling: Exploiting Random Walk Strategies*, The Nineteenth National Conference on Artificial Intelligence, San Jose, California, USA, 2004*Sampling, Counting, and probabilistic inference*, AI seminar, Cornell University, 2005

- ApproxCount

ApproxCount estimates the number of satisfying assignment of a Boolean formula. The algorithm is based on near-uniform sampling of the solution space of the Boolean formula. - SampleSat

SampleSat samples the solution space of a Boolean formula near uniformly. The code is coming soon.

4142 Upson Hall

Cornell University

Ithaca, NY 14853

O: 607-255-1146

H: 607-233-4282

Email : weiwei@cs.cornell.edu

*Last modified: 4/19/05*