Mittagsseminar (in cooperation with J. Lengler, A. Steger, and D. Steurer)

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

Duration: This information is not available in the database

Location: OAT S15/S16/S17

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.

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

Previous talks by year:   2024  2023  2022  2021  2020  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