A&C Seminar: Bipartite Perfect matching in Pseudo-deterministic NC

Wednesday, September 21, 2016 - 4:00pm to 5:00pm
Location: 
32-G575
Speaker: 
Ofer Grossman
Biography: 
MIT
Pseudo-deterministic algorithms are randomized search algorithms that on different executions on the same input, output the same solution with high probability.
 
We will discuss how pseudo-deterministic algorithms bridge the gap between randomized search and decision problems for problems in P and in NC. Next, we will show a pseudo-deterministic NC algorithm for bipartite matching. Finally, we will show how pseudo-determinism can be used to save on random bits used by classical randomized algorithms.
 
Joint work with Shafi Goldwasser.