Research Projects

The modern age has seen a proliferation of large datasets, such as social network graphs, genomes, stock prices, and satellite images, which contribute significantly to our understanding of health, economy, climate, and society. However, processing these massive datasets can be computationally expensive. Sublinear algorithms, which use time or space sublinear in the size of the input, are designed to address this challenge. They can be broadly classified into sublinear-time algorithms that make queries to the input data and sublinear-space algorithms that operate on data streams. The authors propose to investigate the design of efficient sublinear algorithms that are resilient to input corruptions, which are two fundamental types of input corruption. They have modelled erasures made offline before an algorithm starts querying the input and adversarial erasures made in response to queries made by an algorithm. One of the main computational problems considered is testing properties of input objects, where the goal is to distinguish between inputs that satisfy a property and those far from every input satisfying the property. The authors show that erasure-resilience is easier to achieve than error-resilience for properties of inputs having functional representations. They aim to further advance the understanding of erasure-resilient and error-resilient sublinear-time computation, design faster algorithms for fundamental problems, investigate the relative difficulty of error-resilient and erasure-resilient testing for properties of inputs with nonfunctional representations, and extend the study of corruption-resilience to the streaming setting.