## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with M. Ghaffari, A. Steger and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Thursday, March 08, 2007, 12:15 pm

Duration: This information is not available in the database

Location: CAB G51

Speaker: Dominik Scheder

## Partial Satisfaction

In Partial Satisfaction, we aim for statements of the following types:

'In every CNF formula obeying certain constraints, we can satisfy at least a fraction r of all clauses'.

For example, in every 3-CNF formula, we can satisfy at least 7/8 of all clauses. A family of formulas intensively studied in this context is the family of k-satisfiable formulas. Call a CNF formula k-satisfiable if every subformula of at most k clauses is satisfiable. What fraction of clauses can one satisfy in every such formula? Call this fraction r_k. The values of r_k are known for small k, e.g. r_1 = 1/2, r_2 = 0.619 and r_3 = 2/3. We know that they converge to 3/4 as k grows. We will sketch the main ideas of the proof of this fact.

One can define the values r_k for weighted as well as for unweighted formulas (this notion will be made precise in the talk). As we will see, this makes a difference. If time allows, I will show some results about the unweighted case.

Information for students and suggested topics for student talks