Algorithms & Theory Research Projects

A Hybrid Approach to Automatic Programming

Prateek SAXENA

The project introduces an innovative approach that combines traditional program analysis, neural machine translation, and human guidance to enhance accuracy and generalization in automated programming tasks, thereby making coding accessible to non-experts.

Safety and Reliability in Black-Box Optimization

Jonathan SCARLETT

This project seeks to enhance safety, reliability, and robustness in black-box optimization, exploring new function structures and addressing limitations. This includes extending decision-making frameworks to grey-box settings and multi-agent learning, utilizing a methodology blending theoretical analyses and algorithm development.

• Optimisation

Fault-tolerant Graph Structures: Efficient Constructions and Optimality

Diptarka CHAKRABORTY

This project aims to enhance graph problem solutions in the presence of network failures by developing fault-tolerant constructions and optimized graph structures. Through novel approaches, it contributes to algorithmic understanding, graph theory, and real-life applications.

You See the Whole Picture When the Puzzle Pieces Match

YU Haifeng

Massively Parallel Aggregation in Dynamic Networks

YU Haifeng

Rank Aggregation: Fairness and Computational Challenges

Diptarka CHAKRABORTY

• Combinatorial Algorithms, Optimisation

Handling Massive Data under the Edit Metric: Clustering, Finding Median and Computational Hardness

Diptarka CHAKRABORTY

• Combinatorial Algorithms, Optimisation

Computational Hardness Assumptions and the Foundations of Cryptography

Prashant Nalini VASUDEVAN

This program seeks to broaden and diversify the foundations of cryptography by identifying new plausible computational hardness assumptions that can be used to construct cryptosystems. Our current approach is to study and construct "fine-grained" cryptographic primitives based on the conjectured hardness of various well-studied algorithmic problems.

• 
• Complexity Theory, Cryptography

Algorithmic Solutions for Fair Resource Allocation

Warut SUKSOMPONG

Computational Methods for Tournament Selection

Warut SUKSOMPONG

Algorithmic fairness in machine learning

Reza SHOKRI

Auditing data privacy (in machine learning)

Reza SHOKRI

Theoretical foundations of data privacy in machine learning

Reza SHOKRI

Robustness and security in machine learning

Reza SHOKRI

Model explanations and interpretable machine learning

Reza SHOKRI

Theory and algorithms for Bayesian optimization

Jonathan SCARLETT

Bayesian optimization has emerged as a versatile tool for optimizing black-box functions, with particular success in automating machine learning algorithms (e.g., in the famous AlphaGo program). This project seeks to advance the state-of-the-art theory and algorithms, with an emphasis on practical variations that remain lesser-understood, including adversarial corruptions and high dimensionality.

• Learning Theory, Optimisation

Modern methods for high-dimensional estimation and learning

Jonathan SCARLETT

Extensive research has led to a variety of powerful techniques for high-dimensional learning, with the prevailing approaches assuming low-dimensional structure such as sparsity and low-rankness. This project pursues a paradigm shift towards data-driven techniques, including the replacement of explicit modeling assumptions by implicit generative models based on deep neural networks.

• Learning Theory

Theory and algorithms for group testing

Jonathan SCARLETT

Group testing is a classical sparse estimation problem that seeks to identify "defective" items by testing groups of items in pools, with applications including database systems, communication protocols, and COVID-19 testing. This project seeks to push recent advances further towards settings that better account for crucial practical phenomena, including noisy outcomes and prior information.

• Combinatorial Algorithms, Information Theory & Coding, Learning Theory

Information-theoretic limits of statistical inference and learning problems

Jonathan SCARLETT

The field of information theory was introduced to understand the fundamental limits of data compression and transmission, and has shaped the design of practical communication systems for decades. This project pursues the emerging perspective that information theory is not only a theory of communication, but a far-reaching theory of data benefiting diverse inference and learning problems.

• Information Theory & Coding, Learning Theory

Robustness considerations in machine learning

Jonathan SCARLETT

Robustness requirements pose many of the most important unsolved challenges in modern machine learning, arising from sources of uncertainty such as mismatched models, corrupted data, and adversaries. This project seeks to better understand some of the most practically pertinent sources of uncertainty and develop new algorithms that are robust in the face of this uncertainty.

• Learning Theory