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

Date and Time: Tuesday, September 18, 2012, 12:15 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Robin Künzler

Does SAT have a Checker?

Suppose some efficient algorithm A solves SAT correctly on most inputs. A weak checker for SAT is an efficient algorithm that uses A to solve SAT correctly on *any* input with high probability. Unfortunately, for a broad class of weak checkers it is known that they do not work for SAT (unless the polynomial hierarchy collapses). These results have interesting connections to the following two problems:

1) Timon claims he found an efficient algorithm that solves SAT. Unfortunately, he does not (yet) have a proof for this claim. Is it possible to find an efficient program checker that checks the correctness of his algorithm on any given instance?

2) If one-way functions were proved to exist, cryptographers would be very happy as one could securely sign, encrypt, and so on. Showing the existence of one-way functions seems difficult, as it implies P not equal NP. But is it possible to show that P not equal NP implies that one-way functions exist?

In my talk I will explain these two problems and discuss how they are related to the weak checkability of SAT.

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

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