Anindya De’s research investigates the mathematical foundations of computer science, seeking to understand how efficiently computers can learn, process information, and solve complex problems. His work spans computational complexity, learning theory, the analysis of Boolean functions, and applied probability. By connecting mathematical approaches based on logical decisions with those involving geometry and probability, De develops new ways to analyze complex computational problems. These connections help establish the fundamental capabilities and limitations of algorithms, revealing when seemingly difficult tasks can be simplified without sacrificing accuracy.
A key challenge in modern computing is determining how much information an algorithm truly needs to produce reliable results. De’s recent research explores methods for simplifying high-dimensional mathematical structures, demonstrating how a small number of representative elements can approximate the behavior of much more complex systems. His work in property testing develops techniques for identifying mathematical patterns and verifying specific characteristics of functions using relatively few observations, even when information is incomplete or affected by noise. These advances help establish when algorithms can efficiently evaluate complex datasets without examining every detail.
De also applies mathematical theory to problems involving uncertainty and limited resources. Through research in stochastic optimization, he investigates how algorithms can make effective decisions when outcomes are unpredictable, including situations involving scheduling and capacity constraints. His broader work examines the trade-offs between computational efficiency, statistical accuracy, and the amount of information needed to solve a problem. By uncovering these fundamental relationships, De aims to strengthen the theoretical foundations of machine learning, data analysis, and algorithm design, contributing to computing methods that are more efficient, reliable, and adaptable.