Broad Area Colloquium For AI-Geometry-Graphics-Robotics-Vision

Heavy-Tail Phenomena in Computational Problems

Bart Selman
Deprtment of Computer Science
Cornell University

Wednesday, March 8, 2000
refreshments 4:05PM, talk begins 4:15PM
TCseq201, Lecture Hall B
http://robotics.stanford.edu/ba-colloquium/

Abstract

Two key approaches for solving computationally hard problems are local search and backtrack-style search. Local search methods, such as simulated annealing, generally involve a stochastic component, whereas most backtrack-style search methods are deterministic. We study the effect of randomizing backtrack-style search. We analyze the run time profiles of such search procedures applied to hard combinatorial problems, and show that the distributions are often characterized by ``heavy tails'' of the Pareto-Levy form with infinite mean and variance. Such highly non-standard distributions have recently been observed in areas as diverse as economics, statistical physics, geophysics, and WWW traffic, and are closely related to fractal phenomena. We discuss the implications of heavy tailed phenomena in terms of algorithm design. In particular, we show how one can boost the performance of search procedures --- often by several orders of magnitude --- by exploiting the heavy tailed distributions. The model also explains super-linear speedups on parallel compute clusters.

This is joint work with Carla Gome (Cornell University).

About the Speaker

Bart Selman is an Associate Professor of Computer Science at Cornell University. He previously was a principal scientist at AT&T Bell Laboratories. He holds a Ph.D. and M.Sc. in computer science from the University of Toronto, and a M.Sc. in physics from Delft University of Technology. His research has covered many areas in artificial intelligence and computer science, including tractable inference, knowledge representation, natural language understanding, stochastic search methods, theory approximation, knowledge compilation, planning, default reasoning, and the connections between computer science and physics (phase transition phenomena). He has received four best paper awards at the American and Canadian national artificial intelligence conferences, and at the International Conference on Knowledge Representation. He holds an NSF CAREER Award and is an Alfred P. Sloan Research Fellow.
bac-coordinators@cs.stanford.edu
Back to the Colloquium Page
Last modified: Fri Jan 7 11:23:04 PST 2000