Department of Computer Science | Institute of Theoretical Computer Science | CADMO

Prof. Emo Welzl and Prof. Bernd Gärtner

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

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.

Upcoming talks | All previous talks | Talks by speaker | Upcoming talks in iCal format (beta version!)

Previous talks by year: 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M | admin login