Basic Information

Objectives

The performance of an algorithm is typically characterized by its worst-case behavior. However, several examples suggest that worst-case analysis does not give a satisfactory explanation of the behavior of an algorithm in a real-world scenario. This course aims to introduce the student to other paradigms for analyzing algorithms, such as probabilistic and smoothed analysis

Syllabus

Basic Probability Theory and Concentration bounds: : Definitions. Useful Distributions: Gaussian, exponential, etc. Martingales and Azuma’s inequality. Talagrand’s isoperimetry.
Probabilistic Analysis (Introduction): Notion of average-case complexity. Historical perspectives on average-case analysis. Motivating examples. Average-case analysis under various distributions - introduction to probabilistic analysis. Probabilistic Models for real-world inputs.
Probabilistic Analysis (Geometric problems): Euclidean optimization problems. Subbadditive and Superaddtive functionals. Limit Theorems. Concentration bounds. Applications of Talagrand’s isoperimetry. Rhee’s isoperimetric inequality. Algorithmic applications: Karp’s partitioning algorithm.
Probabilistic Analysis (Discrete problems): The Erdos-Renyi model for random graphs. Basic properties of random graphs. Algorithms on random graphs. Other models for random graphs. First passage percolation. Algorithms on first passage percolation.
Smoothed Analysis: Introduction to Smoothed analysis. Examples of smoothed analysis for problems such as Knapsack, Integer Programming, and TSP: 2-OPT. Smoothed number of Pareto optimal solutions. Other local search algorithms. Partitioning algorithm.
Average Case and Smoothed Complexity Theory: Introduction to Levin’s theory of average-case complexity. The class DistNP. The notion of DistNP completeness. Average-case vs. worst-case hardness. Introduction to Smoothed Complexity Theory. Discussion on Challenges in Developing a Complexity Theory for Smoothed Analysis.

Evaluation Scheme

Problem Sets (30%): We plan to have 3 problem sets with equal weightage. They will be posted (on the course emailing list). Please see the Activities section for more details.

End Sem Exam (20%): In hall exam. Duration 2 hours. Will be scheduled as per the Institute's academic calendar.

Project (Reading a research paper: evaluation based on an interim meeting + a Presentation of 30 min duration + Report) 20%

Analysis of a Test Case (A detailed analysis of an example algorithm. ) (15%)

Scribing Notes 15 %