Topics in Algorithms and Complexity (M. Tech. CS 2 Year, 2020)

Instructor Arijit Ghosh

Description In this course we will cover various topics in Algorithms and Complexity.

Prerequisites Mathematical maturity of a finishing undergraduate student in mathematical sciences.

Class timings Tuesday, Thursday, and Saturday 15:30 - 16:30 hrs.

Syllabus

  • Randomized Algorithm

  • The Probabilistic Method

  • NP, NP-completeness, Reduction

  • Approximation Algorithms

References

  • [AB09] Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009.

  • [AS16] Noga Alon and Joel Spencer, The Probabilistic Method, 4th Edition, Wiley, 2016.

  • [BV04] Stephen Boyd and Lieven Vandenberghe, Convex Optimization, Cambridge University Press, 2004.

  • [B15] Sébastien Bubeck, Convex Optimization: Algorithms and Complexity, Foundations and Trends in Machine Learning, 2015.

  • [F99] Ehud Friedgut, Sharp thresholds of graph properties and the k-SAT problem, Journal of the American Mathematical Society, 12 (4): 1017–1054, 1999.

  • [FS11] Jacob Fox and Benny Sudakov, Dependent Random Choice, Random Structures & Algorithms, 38(1-2): 68–99, 2011.

  • [K06] Vladlen Koltun, Advanced Geometric Algorithms, Lecture Notes, Stanford University, 2006.

  • [MG07] Jiří Matoušek and Bernd Gärtner, Understanding and Using Linear Programming, Springer, 2007.

  • [KT06] Jon Kleinberg and Éva Tardos, Algorithm Design, Pearson, 2006.

  • [MR95] Rajeev Motwani and Prabhakar Raghavan, Randomized Algorithms, Cambridge University Press, 1995.

  • [MU17] Michael Mitzenmacher and Eli Upfal, Probability and Computing, Second Edition, Cambridge University Press, 2017.

  • [R19] Thomas Rothvoss, Probabilistic Combinatorics, Graduate Topics Course in Mathematics, UW Seattle, Winter 2019.

  • [V03] Vijay Vazirani, Approximation Algorithms, Springer, 2003.

  • [WS11] David P. Williamson and David B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press, 2011.

  • [HP11] Sariel Har-Peled, Geometric Approximation Algorithms, AMS, 2011. (Preliminary version)

  • [HP18] Sariel Har-Peled, Randomized Algorithms, Lecture notes, UIUC, 2018.

  • [SB14] Shai Shalev-Shwartz and Shai Ben-David, Understanding Machine Learning: From Theory to Algorithms, Cambridge University Press, 2014. (Free copy)

Lecture details

Topics covered in Lecture 1

  • Discussed the outline of the course.

Topics covered in Lectures 2 and 3

  • Recalled basic results from probability theory

  • Random variables

  • Indicator random variables

  • Proving Markov's inequality using indicator random variables

  • Estimating size of maximum cuts in a graph (using linearity of expectation and indicator random variables)

  • Max-SAT problem (using linearity of expectation and indicator random variables)

  • A randomized algorithm for computing a minimum cut in graphs (using the chain rule of conditional probability)

  • References:

      • Sections 1.1, 1.2, and 1.3 from Chapter 1 in [MU17]

      • Section 2.1 from Chapter 2 in [MU17]

      • Section 3.1 from Chapter 3 in [MU17]

      • Section 6.2 from Chapter 6 in [MU17]

Topics covered in Lectures 4 and 5

  • Karger's minimum cut algorithm through the lens of Kruskal's algorithm

  • Faster implementation of Karger's randomized minimum cut algorithm

  • References:

      • Section 10.2 from Chapter 10 in [MR95]

      • Section 2 from Karger's original paper

Topics covered in Lectures 6 and 7

  • Galton-Watson process and minimum cut

  • Verifying matrix multiplications

  • Simple properties of Bernoulli, Binomial and Geometric distributions

  • Introduction to occupancy and coupon collector problems

  • References:

      • Section 1.3 from Chapter 1 in [MU17]

      • Sections 2.1, 2.2, 2.3, and 2.4 from Chapter 2 in [MU17]

      • Section 3.2 from Chapter 3 in [MU17]

      • Section 2.1 from Chapter 2 in [HP18]

      • Chapter 3 in [HP18]

Topics covered in Lectures 8 and 9

  • Balls and bins

  • Birthday paradox via balls and bins

  • Bounding maximum load of a bin using combinatorial techniques

  • Coupon collector problem

  • Analysis of coupon collector problem using geometric random variable and Chebyshev's inequality

  • Better bound on the upper tail for the coupon collector problem

  • Expected number of comparisons in Quicksort algorithm (both random pivot case and random permutation case)

  • References:

      • Analysis of Quicksort algorithm from Chapter 1 (before Section 1.1) in [MR95]

      • Section 1.3 from Chapter 1 in [HP18]

      • Chapters 4 and 5 in [HP18]

      • Sections 2.4 and 2.5 from Chapter 2 in [MU17]

      • Section 3.6 from Chapter 3 in [MR95]

      • Sections 5.1 and 5.2 from Chapter 5 in [MU17]

Topics covered in Lectures 10, 11 and 12

  • A randomized algorithm for computing the median

  • Binary space partition and random permutation

  • Lower tail of the coupon collector problem via moment generating function

  • References:

      • Section 3.5 from Chapter 3 in [MU17]

      • Section 3.3 from Chapter 3 in [MR95]

      • Section 1.4 from Chapter 1 in [HP18]

Topics covered in Lectures 13 and 14

  • Moment generating function and it's basic properties

  • Chernoff bounds

  • Better concentration bound for +1/-1 case

  • Balancing vectors problems

  • Hoeffding’s inequality

  • References:

      • Sections 4.1, 4.2, 4.3, 4.4 and 4.5 from Chapter 4 in [MU17]

      • Chapter 7 in [HP18]

      • Section 4.1 from Chapter 4 in [MR95]

Topics covered in Lecture 15

  • First moment method

  • Max 3-SAT and maximum cut in graphs via the first moment method

  • Alteration method

  • Large independent sets in graphs using alteration

  • Improving independent set lower bound via random permutation and first moment method

  • References:

      • Sections 6.2, and 6.4 from Chapter 6 in [MU17]

      • Section 3.2 from Chapter 3 in [AS16]

      • Turan's Theorem (The Probabilistic Lens, pages 100-101) from [AS16]

  • Additional references (non-examinable):

      • Shearer's result on independent sets in triangle-free graphs

      • See also the following paper by Shearer

Topics covered in Lecture 16

  • Random Erdős–Rényi random graphs

  • Graphs with large girth via random graphs and alteration method

  • Second moment method

  • Threshold behavior in random graphs

  • References:

      • Sections 6.4 and 6.5 from Chapter 6 in [MU17]

      • Sections 4.1, 4.3, and 4.4 from Chapter 4 in [AS16]

  • Additional references (non-examinable):

      • Friedgut's sharp thresholds of graph properties [F99]

Topics covered in Lecture 17

  • Lovász local lemma (LLL)

  • Applications of LLL

  • References:

      • Sections 6.7 and 6.9 from Chapter 6 in [MU17]

      • Section 5.1 from Chapter 5 in [AS16]

      • Chapter 3 (excluding Section 3.2) in [R19]

  • Additional references:

      • Chapter 5 in [AS16]

      • Sections 6.8 and 6.10 from Chapter 6 in [MU17]

      • Section 3.2 from Chapter 3 in [R19]

Topics covered in Lectures 18 and 19

  • Introduction to Turán numbers of graphs

  • Turán numbers of bipartite graphs

  • Dependent random choice

  • References:

      • Pages 317–319 in [AS16]

      • Chapter 7 in [R19]

  • Additional references:

      • Fox-Sudakov's paper [FS11] on dependent random choice

Topics covered in Lectures 20 and 21

  • Optimization and decision versions of vertex cover and independent set problems.

  • Set cover and packing problems

  • Polynomial-time reductions

  • Difference between finding and verifying solutions

  • Efficient certification

  • NP, NP-completeness, and NP-hardness

  • NP-completeness proof of Independent set problem in graphs via 3-SAT

  • NP-completeness proof of Vertex cover problem via Independent set problem

  • P vs. NP problem

  • References:

      • Sections 8.1, 8.2, 8.3, and 8.4 from Chapter 8 in [KT06]

Topics covered in Lecture 22

  • Circuit satisfiability problem

  • Cook-Levin Theorem

  • Revisiting 7/8-approximation to Max-3-SAT problem

  • Max-SAT and maximum cut

  • 2-approximation of Vertex cover problem via maximal matching

  • References:

      • Section 8.4 from Chapter 8 in [KT06]

      • Section 1.1 from Chapter 1 in [V03]

      • Section 5.1 from Chapter 5 in [WS11]

Topics covered in Lecture 23

  • Approximation algorithm paradigm: Greedy algorithms and local search

  • Metric k-center problem and Travelling salesman problem

  • 2-factor approximation for Metric k-center problem via Farthest point insertion heuristic

  • Hardness of approximation for Metric k-center problem via a reduction from dominating set

  • References:

      • Chapter 5 in [V03]

      • Section 2.2 from Chapter 2 in [WS11]

      • Gonzalez's paper on farthest point insertion heuristic

Topics covered in Lectures 24 and 25

  • NP-completeness proof of Dominating Set problem via Vertex Cover problem

  • Traveling salesman problem (TSP)

  • Hardness of approximation for the general TSP

  • 2-factor approximation for Metric TSP by modifying Prim's Minimum Spanning Tree algorithm

  • 2-factor approximation for Metric TSP using Eulerian graph and double-tree algorithm

  • Christofides' 3/2-factor approximation algorithm for Metric TSP problem

  • References:

      • Section 2.4 from Chapter 2 in [WS11]

      • Section 3.2 from Chapter 3 in [V03]

Topics covered in Lectures 26, 27, 28 and 29

  • Introduction to Integer Linear Programming (ILP) and Linear Programming (LP)

  • NP-hardness of ILP

  • Deterministic rounding algorithm for Vertex Cover and Set Cover problems

  • Randomized rounding algorithm for Set Cover problem

  • 3/4-factor approximation algorithm for Max-SAT problem via randomized rounding

  • 3/4-factor approximation algorithm for Max-SAT problem via non-linear randomized rounding

  • Derandomization

  • References:

      • Sections 1.2, 1.3 and 1.7 from Chapter 1 in [WS11]

      • Chapters 12, 13, 14, and 16 in [V03]

      • Sections 5.1, 5.2, 5.3, 5.4, 5.5, and 5.6 from Chapter 5 in [WS11]