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.

I’ve been interested in algorithms but didn’t have a chance to learn more than what courses can offer. Through SuperUROP, I hope to dive deeper into sublinear algorithms and contribute to this area.