Research Projects

The study aims to design algorithms that can efficiently interact with large datasets, such as Facebook and Twitter, and compute useful statistics quickly. These algorithms should be practical and implementable in practice, requiring only a fraction of input data and reasonable estimates for desired quantities. sublinear algorithms, which only look at a fraction of input data, are known for producing accurate, high-probability estimates. However, no known sublinear algorithm can work very fast for many problems of interest, and there is no lower bound result that rules out their existence. The study will systematically study the various aspects of problems that make the existence or design of sublinear algorithms difficult. It will also examine the powers and limitations of various access models and understand their practicality for various problems of interest. The goal is to develop techniques to design robust sublinear algorithms that work even when assumptions are only partially satisfied. Designing robust sublinear algorithms and proving their guarantees is a relevant and timely task. The goal is to make the algorithms simple and efficiently implementable, allowing them to be deployed in practice.