Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, October 30, 2007, 12:15 pm
Duration: This information is not available in the database
Location: CAB G51
Speaker: Patrick Traxler
Constraint systems with domain size d and maximum constraint size k are a generalization of k-cnfs. The n variables can take values from a domain of size d which may be larger than 2. Let s be the number of solutions of a constraint system C. We show that the currently provable fastest algorithm of Feder & Motwani for deciding satisfiability of a constraint system with k = 2 is sensible to s. It has expected running time O(d!^(n-log_d(s))/d). We also treat derandomization issues for constraint systems without any constraint size restriction. We show that if either s = 0 or s/d^n >= 1 - r/|\C| for r > 1 then a deterministic algorithm of running time O(|C|^(r+2)) exists for deciding satisfiability.
Automatic MiSe System Software Version 1.4803M | admin login