[Colloquium] Theory Seminars at Computer Science

[Donna Brooms]

*REMINDER*

The University of Chicago
THEORY SEMINAR
 
Tuesday, November 11, 2014
Ryerson 251 at 3:00 p.m.
 
Edward A. Hirsch
Steklov Institute of Math @ St. Petersburg
Logic.pdm.ras.ru/~hirsch/
 
Title: “Distributional proving problems, and beyond”
 
Abstract: A distributional proving problem consists of a language L of ``theorems'' and a polynomial-time samplable distribution D on``non-theorems'' (for example, one can think about Boolean tautologies and the planted SAT distribution). A heuristic acceptor is an algorithm that accepts all theorems and possibly a small (w.r.t. D) amount of non-theorems. An optimal acceptor is the fastest possible
acceptor (that is, for every theorem, it outperforms any other acceptor w.r.t. the running time up to a polynomial).
 
We prove that for every r.e. language (in particular, for every L in coNP) there exists an optimal randomized heuristic acceptor. This is in contrast to the situation in classical complexity, where the existence of an optimal acceptor for Boolean tautologies is unknown and is equivalent to the existence of a p-optimal proof system [Krajicek, Pudlak, 90s].
 
We also discuss some cases where it is possible to derandomize our result (the image of an injective function) or eliminate heuristic errors (graph non isomorphism).
 
Host: Prof. Alexander Razborov
 
*Refreshments will be served in Ryerson 255 at 2:30pm*
 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20141111/449408ef/attachment-0001.htm