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

Prof. Emo Welzl and Prof. Bernd Gärtner

Mittagsseminar Talk Information |

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

**Duration**: 30 minutes

**Location**: OAT S15/S16/S17

**Speaker**: Robin Künzler

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: 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