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

Date and Time: Tuesday, November 18, 2008, 12:15 pm

Duration: This information is not available in the database

Location: OAT S15/S16/S17

Speaker: Robin Künzler

The Power of Interactive Proofs, IP = PSPACE

When we talk about proving, we naturally think of proofs that can be written down on a sheet of paper. Someone who wants to verify such a proof then looks at it and decides whether it is valid or not. This idea is closely related to the complexity class NP, which contains exactly the languages for which efficiently verifiable proofs of membership exist.

Tomorrow we want to investigate a more general notion of a proof. Namely, we now consider a prover that is allowed to interact with the (efficient and probabilistic) verifier in order to convince him that a claim is true. Are these interactive proofs stronger than the "usual proofs"? Quite surprisingly, they seem to be a lot stronger: Namely, Shamir showed that any language in PSPACE has interactive proofs!

We first discuss an interactive protocol for proving that a Boolean formula is unsatisfiable and then look at the proof of IP = PSPACE.

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