DIMACS Theoretical Computer Science Seminar

Title: Disjoint NP-pairs and Propositional Proof Systems

Speaker: Alan Selman, University of Buffalo

Date: Wednesday, November 5, 2014 11:00-12:00pm

Location: CoRE Bldg, Room 301A, Rutgers University, Busch Campus, Piscataway, NJ


This talk surveys results on disjoint NP-pairs, propositional proof systems, function classes, and promise classes - including results that demonstrate close connections that bind these topics together. We illustrate important links between the questions of whether these classes have complete objects and whether optimal proof systems may exist.

See: http://www.math.rutgers.edu/~sk1233/theory-seminar/S14/