[Colloquium] Alan Selman Talk at TTI

[Katherine Cumming]

TOYOTA TECHNOLOGICAL INSTITUTE TALK 

Speaker:  Alan Selman
  SUNY at Buffalo

Speaker's homepage: http://www.cse.buffalo.edu/faculty/selman/

Time:  2:00 PM
Date:   Monday, November 15th
Place:   TTI-C
(Refreshments provided) 

Title:   Disjoint NP-Pairs

Abstract: 
A disjoint NP-pair is a pair (A, B) of nonempty, disjoint sets such that
both A and B belong to NP. Given a disjoint NP-pair, we are interested
in whether there is a set S in P that separates them: S separates (A, B)
if A is a subset of S and B is a subset of the complement of S. The
existence of disjoint pairs that are not separated by any set in P is
closely connected to the existence of public-key cryptosystems, and
disjoint NP-pairs arise naturally in the study of propositional proof
systems. This talk will focus primarily on connections with disjoint
NP-pairs and propositional proofs systems. I will survey results and
open questions.
 
If you have questions, or would like to meet the speaker, please contact
Katherine at 834-1994 or kcumming at tti-c.org
 
For information on future TTI-C talks or events, please go to the TTI-C
Events 
page: http://www.tti-c.org/events.shtml
 
 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20041108/7d5ef434/attachment.htm