Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, October 30, 2008, 12:15 pm
Duration: This information is not available in the database
Location: CAB G51
Speaker: Heidi Gebauer
By (k,s)-CNF we denote the set of CNF-formulas where every clause has exactly k distinct literals and each variable occurs in at most s clauses. Kratochvil, Savicky and Tuza showed by using the Lovasz Local Lemma that every (k, 2^k/ (ek))-CNF formula is satisfiable. From the other side Hoory and Szeider established unsatisfiable (k, log(k) * 2^k/ k)-CNF formulas, implying that the bound of Kratochvil et al. is tight up to a logarithmic factor. We can show that the bound of Kratochvil is even asymptotically tight by constructing an unsatisfiable(k, 4 * 2^k/ k)-CNF formula. This construction will be presented in the talk.
Automatic MiSe System Software Version 1.4803M | admin login