Pseudo deterministic algorithms and proofs

Federated Logic Conference (FLoC) 2018 by Oxford University

In this talk I will describe what is known about pseudo-deterministic algorithms in the sequential, sub-linear and parallel setting. Probabilistic algorithms for both decision and search problems can offer significant co...View more