Courses

Approximation Algorithms

Instructor: Nikhil Kumar (TIFR Mumbai)

Course Description

For many important optimisation problems, it is widely believed that they cannot be solved optimally using efficient algorithms. One way to address this challenge is to relax the requirement of exact optimality and instead seek near-optimal solutions. This motivates the study of approximation algorithms, which focus on designing efficient algorithms with provable guarantees on solution quality. In this course, we will cover core techniques for designing and analyzing approximation algorithms, including greedy methods, local search, and linear programming–based techniques.

Prerequisites

Basic discrete math, linear algebra and probability. Knowledge of basic algorithms will be useful, but is not required.

Optimization for Machine Learning

Instruction: Adarsh Barik (IIT Delhi)

Course Description

This course will introduce fundamental concepts for solving machine learning (ML) problems. We will see how ML models differentiate cats from dogs. Along the way, we will see how ML tasks can be framed as optimization problems and try to understand what makes them challenging to solve. We will also explore some algorithms that can provably solve these problems, and estimate how fast they can solve them. Finally, we will also see if ML algorithms can make educated guesses about the future, and whether these guesses can help with sequential decision-making under uncertainty.

Prerequisites

A working knowledge of linear algebra, calculus, and probability. The following topics will be particularly useful: vectors, matrices, and basic operations on these, including matrix calculus. Some ML knowledge is a plus, but not mandatory.

Error Correcting Codes

Instructor: Mrinal Kumar (TIFR Mumbai)

Course description

The problem of storing and transmitting data effectively in the presence of noise is a fundamental problem of interest at the intersection of computer science, engineering and mathematics. Ideally, we would like communication and storage schemes that allow us to efficiently recover the original information even if a part of the data is corrupted, for instance, if your DVD has some scratches, or if some of the packets are dropped while being transmitted over the internet.

Error correcting codes are mathematical objects designed to solve precisely these problems. The foundations of the theory of error correcting codes (or simply coding theory) emerged from the beautiful and profound works of Shannon and Hamming in the 1940’s. This course will be a gentle introduction to this world of error correcting codes. We will discuss what these objects are, why they are of interest, and talk about some examples of codes and their properties.

Prerequisites

Basic linear algebra, discrete probability and undergraduate algorithms.

Game theory

Instructor: Umang Bhaskar (TIFR Mumbai)

Course description

The course will be a mathematical introduction to the theory of games. We’ll look at different kinds of ‘real life’ games, including voting in elections and selling items via auction. We’ll also look at the role algorithms play in games, and how wrong incentives can lead to suboptimal outcomes in these games.

Prerequisites

Basic linear algebra, probability, discrete math. The following topics will be particularly useful: vectors, matrices, and basic operations on these, matrix rank, basic probability distributions, random variables and expectation. Knowledge of graphs, including matchings and flows, may also be useful but is not required.