From: Paul Beame (beame@cs.washington.edu)
Date: Wed Feb 04 2004 - 09:24:29 PST
CSE Theory Seminar
TIME: Friday, Feb 6, 2:30-3:20 PM
PLACE: CSE 403
SPEAKER: Cristopher Moore
Computer Science Department
University of New Mexico
TITLE: How independent are the branches of a search tree?
ABSTRACT:
The physicist Remi Monasson and his coauthors have recently estimated
the running time of Davis-Putnam backtracking algorithms for problems
like 3-SAT and Graph k-Coloring. They do this by assuming that the
branches of the search tree are statistically independent; this
"dynamic annealing" assumption is false, but their estimates are
surprisingly good. Just how correlated are the branches of a search
tree?
For graphs of low degree, they are very highly correlated. Even when
the mean degree is so small that linear-time heuristics often succeed
in coloring the graph with no backtracking at all, small "culprits" can
occur in a partially-colored graph, killing off an entire subtree and
forcing an exponential amount of backtracking. This helps explain the
well-known phenomenon that the amount of backtracking follows a
heavy-tailed probability distribution.
On the other hand, when the degree of the graph is large, for at least
some Davis-Putnam algorithms we can prove upper bounds on the running
time whose scaling matches Monasson's prediction exactly. This
suggests that in the limit of large degree, the correlations between
branches of the search tree may become unimportant, making the "dynamic
annealing" assumption effectively true.
This is joint work with Paul Beame and Haixia Jia.
_______________________________________________
Theory-talks mailing list
Theory-talks@cs.washington.edu
http://mailman.cs.washington.edu/mailman/listinfo/theory-talks
_______________________________________________
Theory-group mailing list
Theory-group@cs.washington.edu
http://mailman.cs.washington.edu/mailman/listinfo/theory-group
_______________________________________________
Theory-talks mailing list
Theory-talks@cs.washington.edu
http://mailman.cs.washington.edu/mailman/listinfo/theory-talks
_______________________________________________
Theory-group mailing list
Theory-group@cs.washington.edu
http://mailman.cs.washington.edu/mailman/listinfo/theory-group
This archive was generated by hypermail 2.1.6 : Wed Feb 04 2004 - 09:24:51 PST