Leveraging Probability and Uncertainty in Computation
AAAI-2000 Workshop
July 31, 2000
Austin, Texas
American Association for Artificial Intelligence

Recently there has been an increasing interest in approaches based on randomization, probability, and uncertainty to speed up computation and to model resources more realisticly. (1) Given that in real world problems computational resources are limited, and the environment is very dynamic, it is important to use flexible, incremental methods that trade off resources for value of information. (2) Probabilistic analysis and empirical studies of the runtime distributions of algorithms have recently been adopted as a better way to characterize algorithm performance. Such studies have improved algorithm design, leading to anytime strategies, and, more generally, methods that combine algorithms into portfolios. (3) There has been considerable success in developing stochastic local search algorithms as well as randomized systematic search methods for solving hard combinatorial problems. 


This workshop will bring together researchers from different areas of AI and Operations Research in order to discuss various topics in randomization, stochastic search techniques, probability analysis of algorithms, flexible computation, and uncertainty. Topics include: 

Utility perspective on computation and information

Flexible anytime computation based on utility measures

Probabilistic analysis and evaluation of stochastic algorithms

Randomization to improve algorithmic efficiency and robustness

Design and implementation of randomized algorithms

Stochastic local search vs. randomized systematic search methods,

other stochastic search strategies

Portfolios of algorithms

Theoretical results on stochastic algorithms


The workshop runs for one day (July 31, 2000) and will include technical paper presentations, invited talks, and panel discussions.


The workshop will be limited to about 40 invited participants. Persons interested in attending the workshop should submit either full papers (up to 10 pages) or statement of interest (up to 2 pages). Paper submissions of two kinds are invited: technical papers or position papers that describe opportunities and challenges.


Submissions should be in postscript, pdf, or ascii (only for statement of interest). Submit your contribution by emailing the URL where the submission can be retrieved (preferred method) or by emailing the submission itself to gomes@cs.cornell.edu or hoos@cs.ubc.ca. Submissions will be acknowledged by March 15th.

Important Dates

Submission deadline: March 10, 200
Notification of acceptance: March 24, 2000
Camera-ready copy deadline:April 26 2000 
Workshop: July 31,  2000 



Dimitris Achiloptas, Microsoft Research
Roberto Bayardo, IBM Research
Tom Dean, Brown Univ.
Ian Gent, U. St. Andrews, UK
Joseph Halpern, Cornell University
Adele Howe, Colorado State Univ.
Henry Kautz, AT&T Research
Eric Horvitz, Microsoft Research
rina Rish, IBM Research
Stuart Russell, UC Berkeley
Gene Santos, University of Connecticut
Bart Selman, Cornell University
Toby Walsh, University of York, UK.