Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

Date and Time: Thursday, July 28, 2011, 12:15 pm

Duration: 30 minutes

Location: ML J37.1

Speaker: Dominik Scheder

A very different algorithm for k-SAT

In 2010, Ryan Williams showed how to solve the satisfiability problem of ACC circuits in time 2^n / superpolynomial(n). Bjorklund showed that when one distills this algorithm down to CNF formulas, one obtains an algorithm whose running is in some way comparable to that of Schoening or PPSZ. Although being slower than these, it is an interesting algorithm, because it is very different from other SAT algorithms. In the talk, I will present this algorithm together with an analysis of its success probability and running time. The algorithm has not been published so far. I learned of this algorithm from Mohan Paturi, who is currently writing it up together with William Matthews and Daniel Lokshtanov.

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

Previous talks by year:   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