Shih-Yu Wang

abstract:Randomized algorithms are an important research area in theoretical computer science because they run faster than deterministic algorithms by allowing a small chance of failure. In particular, a pseudo-deterministic algorithm can solve search problem and gives the same solution with high probability. Although pseudo-deterministic algorithms have received much attention recently, there has been no work on pseudo-deterministic algorithms in the context of sublinear time algorithms. In my SuperUROP research project, I will study pseudo-deterministic algorithms for classical problems in parallel and sublinear time models of computation.