Probability and Uncertainty in Computation
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 firstname.lastname@example.org or email@example.com. Submissions will be acknowledged by March 15th.
|Carla P. Gomes
Dept. of Computer Science
Ithaca, NY 14853
Dept. of Computer Science
University of British Columbia
Vancouver, BC, V6T 1Z4
|Dimitris Achiloptas, Microsoft
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
Irina Rish, IBM Research
Stuart Russell, UC Berkeley
Gene Santos, University of Connecticut
Bart Selman, Cornell University
Toby Walsh, University of York, UK.