Computer Science/Discrete Mathematics Seminar II
Pseudo-deterministic algorithms
A pseudodeterministic algorithm for a search problem (introduced by Goldwasser and Gat) is a randomized algorithm that must output the *same* correct answer with high probability over all choices of randomness. In this talk I will give several motivating examples of search problems that illustrate the importance of the notion, and connections with other well-studied topics in TCS (i.e., explicit constructions of combinatorial objects known to exist by the probabilistic method, lower bounds for random kSAT, inapproximability lower bounds for SOS based algorithms, and random Resolution. After reviewing some known results, we will prove a Pseudodeterministic query lower bound for the (complete) problem of finding a "1" in a vector that is promised to have at least a constant fraction of 1's. Our proof uses Huang's Sensitivity Theorem as well as Nullstellensatz/SOS degree lower bounds and brings up a number of open problems. This work is joint with Shafi Goldwasser, Russell Impagliazzo and Rahul Santhanam.