Research

Computer Sciences and Information Technology

Title :

Fast Corruption-Resilient Sublinear Algorithms

Area of research :

Computer Sciences and Information Technology

Principal Investigator :

Dr. Nithin Varma, Chennai Mathematical Institute, Tamil Nadu

Timeline Start Year :

2022

Timeline End Year :

2024

Contact info :

Equipments :

Details

Executive Summary :

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.

Total Budget (INR):

15,09,816

Organizations involved