Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, February 28, 2017, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Jerri Nummenpalo
Let F be a k-CNF formula over n variables with the promise that at least a c-fraction of all the 2^n assignments are satisfying for some given c = c(n). The trivial sampling algorithm needs in expectation 1/c many samples before finding a satisfying assignment for F. We consider it as a benchmark as we consider algorithms for both finding a satisfying assignment and sampling one uniformly at random among all satisfying assignments. This is joint work with Jean Cardinal, Jozsef Solymosi and Emo Welzl.
Automatic MiSe System Software Version 1.4803M | admin login