# CSCI5160 Approximation Algorithms — Spring 2020

This is the webpage for a previous offering of the course in 2020; latest offering available here

Siu On CHAN Office hours Tuesday 4:30-6:30pm SHB 911

Teaching assistant

- Sing Hei Ray LI shli@cse Office hours Wednesday 1:30-2:30pm SHB 117

## News

- Apr 27: Please submit your project report by May 20 23:59.
- Apr 27: Homework 2 is now available below.
- Mar 9: Homework 1 has been updated to fix typos in Q3.
- Mar 2: Homework 1 is now available below.
- Feb 17: Starting from Feb 17, classes are conducted online at the usual time slots via Zoom. Details are announced on Piazza.

## Information

- Lectures
- Mon 2:30-4:15pm (ERB 405) Tue 3:30-4:15pm (LSB C5)
- Prerequisites
- Linear algebra, Probability, Discrete Math, algorithm design and analysis
- References
- [BV]
*Convex Optimization*, Stephen Boyd and Lieven Vandenberghe (available online) - [WS]
*The Design of Approximation Algorithms*, David P. Williamson and David B. Shmoys (available online) - [G]
*Foundations of Optimization*, Osman Güler (accessible online at university library webpage) - [GM]
*Approximation Algorithms and Semidefinite Programming*, Bernd Gärtner and Jiri Matousek (accessible online at university library webpage)

- [BV]
- Forum
- Please sign up on Piazza
- Grading
- 50% homeworks, 50% project

## Topics

This course will study the design and analysis approximation algorithms for various optimization problems. We will cover spectral algorithms, semidefinite programs, and related convex programs. Here are tentative topics:

- Semidefinite programs
- SDP duality
- Multiplicative weight update
- Graph spectrum
- Eigenvalue interlacing
- Cheeger–Alon–Milman inequality
- Random walks
- Local graph partitioning
- Expanders
- Laplacian solver
- Effective resistance
- Sparsification
- Matrix scaling
- Abstract simplicial complex
- Random spanning trees

## Lectures

Date | Topic | Readings | Notes | ||
---|---|---|---|---|---|

1 | Jan 6 | Semidefinite programs and positive semidefinite matrices | [GM] Ch. 2 | Notes 01 | |

2 | Jan 7 | SDP vs LP and Goemans–Williamson | [GM] Ch. 1 | Notes 02 | |

3 | Jan 13 | Separation theorem, Polar set | [BV] §2.5.1 | Notes 03 | |

4 | Jan 14 | Conjugate function | [BV] §3.3 | Notes 04 | |

5 | Jan 20 | Dual program | [BV] §4.1.1,§4.2,§5.1 | Notes 05 | |

6 | Jan 21 | Strong duality | [BV] §5.1, §5.2, §5.3 | Notes 06 | |

Jan 27 | Lunar New Year Holiday | ||||

Jan 28 | Lunar New Year Holiday | ||||

Feb 3 | Quarantine week | ||||

Feb 4 | Quarantine week | ||||

Feb 10 | Quarantine week | ||||

Feb 11 | Quarantine week | ||||

7 | Feb 17 | Complementary slackness; KKT conditions | [BV] §5.4, §5.5 | Notes 07 | |

8 | Feb 18 | Multiplicative Weight Update | [AHK] §2, §3.3, §3.4 | Notes 08 | |

9 | Feb 24 | Graph spectrum and Laplacian | Notes 09 | ||

10 | Feb 25 | Conductance, expansion, normalized Laplacian | Lau’s lecture | Notes 10 | |

11 | Mar 2 | Cheeger–Alon–Milman inequality | Lau’s or Spielman’s | Notes 11 | |

12 | Mar 3 | Random walk | Lau’s lecture | Notes 12 | |

13 | Mar 9 | Local graph partitioning | Lau’s lecture | Notes 13 | |

14 | Mar 10 | Local graph partitioning (continued) | Lau’s lecture | Notes 13 | |

15 | Mar 16 | Expander | Spielman’s or Lau’s | Notes 15 | |

16 | Mar 17 | Electrical flow and Laplace equation | Spielman’s lecture | Notes 16 | |

17 | Mar 23 | Effective resistance |
Spielman’s or Lau’s | Notes 17 | |

18 | Mar 24 | Effective resistance (continued) | Spielman’s or Lau’s | Notes 17 | |

19 | Mar 30 | Graph sparsification | Lau’s or Spielman’s | Notes 19 | |

20 | Mar 31 | Sampling spanning trees by random walk | Lau’s lecture | Notes 20 | |

21 | Apr 6 | Sampling spanning trees by random walk (continued) | Lau’s lecture | Notes 20 | |

22 | Apr 7 | High dimensional expander | Lau’s lecture | Notes 22 | |

Apr 13 | Easter Monday | ||||

23 | Apr 14 | High dimensional expander (continued) | Lau’s lecture | Notes 22 | |

24 | Apr 20 | High dimensional expander (continued) | Lau’s lecture | Notes 22 | |

25 | Apr 21 | Largest simplex | Nikolov | Notes 25 | |

26 | Apr 27 | Largest simplex (continued) | Nikolov | Notes 25 | |

27 | Apr 28 | John ellipsoid | Lau’s lecture | Notes 27 |

Date | Topic | Readings | Notes | ||
---|---|---|---|---|---|

1 | Jan 6 | Positive semidefinite matrices | [GM] Ch. 2 | ||

2 | Jan 7 | Semidefinite programs and Goemans–Williamson | [GM] Ch. 1 | ||

3 | Jan 13 | Duality | [GM] Ch. 4 | ||

4 | Jan 14 | Duality | |||

5 | Jan 20 | Duality | |||

6 | Jan 21 | Multiplicative weights and minimizing regrets | Arora–Hazan–Kale | ||

Jan 27 | Lunar New Year Holiday | ||||

Jan 28 | Lunar New Year Holiday | ||||

7 | Feb 3 | Graph spectrum and Laplacian | Lau’s lecture | ||

8 | Feb 4 | Cheeger–Alon–Milman inequality | Lau’s lecture | ||

9 | Feb 10 | Spectral embedding | Spielman’s lecture | ||

10 | Feb 11 | Random walks | Lau’s lecture | ||

11 | Feb 17 | Random walks | |||

12 | Feb 18 | Expanders | Lau’s lecture | ||

13 | Feb 24 | Local graph partitioning | Lau’s lecture | ||

14 | Feb 25 | Effective resistance | Spielman’s lectures 7 & 8 | ||

15 | Mar 2 | Laplacian solver | Lau’s lecture Spielman’s lecture |
||

16 | Mar 3 | Laplacian solver | Lau’s lecture Spielman’s lecture |
||

17 | Mar 9 | Random walk and abstract simplicial complexes | |||

18 | Mar 10 | Random walk and abstract simplicial complexes | |||

19 | Mar 16 | John ellipsoid | Lau’s lecture | ||

20 | Mar 17 | John ellipsoid | |||

21 | Mar 23 | Largest simplex | Nikolov | ||

22 | Mar 24 | Matrix scaling | |||

23 | Mar 30 | Matrix scaling | |||

24 | Mar 31 | Discrepancy minimization | |||

25 | Apr 6 | Discrepancy minimization | |||

26 | Apr 7 | TBD | |||

Apr 13 | Easter Monday | ||||

27 | Apr 14 | TBD |

## Homeworks

There will be two to three homeworks.

Collaboration on homework and consulting references is encouraged, but you must write up your own solutions in your own words, and list your collaborators and your references on the solution sheet.

Please submit your homework online as a single PDF file at elearn.cuhk.edu.hk

Homework 1 due Sun Mar 15 23:59 (updated on Mar 9 to fix typos in Q3: 4/n is now corrected as n/4)

Homework 2 due Sun May 10 at 23:59.

## Project

The course project involves writing a short report (5-10 pages) related to approximation algorithms in an area of your interest. The report may be your exposition of a paper from the list below (or any similar paper), or a summary of your new follow-up results. You are encouraged include in your report any illustrative, concrete examples that help you understand the papers you read.

Please submit your project report online as a single PDF file at elearn.cuhk.edu.hk by May 20 23:59

If your report is a summary of a paper you read, it should highlight the following:

- What is the main result? A typical paper contains one main result and several corollaries or extensions. Focus on the main result in your report, unless you find a particular extension interesting.
- If the main result is very general, can you illustrate it with interesting special cases?
- What are the key new ideas? Can you illustrate them with concrete examples? How did the authors come up with these ideas?
- What have you learned? How might the key ideas or new results be useful in your own research?
- Are key inequalities in the papers tight (perhaps up to constant factors)? If so, can you come up with tight examples? If not, what do you think are the correct bounds?

Write your summary as if you are explaining the main result and its key ideas to other students in this class, or to any graduate student with a solid background in math.

Explain in your own words and in simple language as much as possible. The more you can do so, the better you understand the papers.

Paper suggestions:

- Sparse approximation
- The Paulsen Problem Made Simple, Linus Hamilton, Ankur Moitra
- Algorithms and Hardness for Robust Subspace Recovery, Moritz Hardt, Ankur Moitra

- Multiplicative weight
- Faster Approximation Algorithms for Geometric Set Cover, Timothy M. Chan, Qizheng He

- Conductance and spectrum
- Cheeger Inequalities for Submodular Transformations, Yuichi Yoshida

- Spectral sparsification/statistical learning
- Covariance estimation for distributions with 2+ε moments, Nikhil Srivastava, Roman Vershynin

- Spectral sparsification
- Dynamic Streaming Spectral Sparsification in Nearly Linear Time and Space, Michael Kapralov, Navid Nouri, Aaron Sidford, Jakab Tardos

- Laplace solver
- Packing LPs are Hard to Solve Accurately, Assuming Linear Equations are Hard, Rasmus Kyng, Di Wang, Peng Zhang

- High dimensional expander
- Improved Analysis of Higher Order Random Walks and Applications, Vedat Levi Alev, Lap Chi Lau

- Permanant
- A Tight Analysis of Bethe Approximation for Permanent, Nima Anari, Alireza Rezaei

- Hypothesis testing/matrix norms
- Testing Matrix Rank, Optimally, Maria-Florina Balcan, Yi Li, David P. Woodruff, Hongyang Zhang

- Hypothesis testing
- Testing Halfspaces over Rotation-Invariant Distributions, Nathaniel Harms

- Online algorithms
- The Online Submodular Cover Problem, Anupam Gupta, Roie Levin

- Semidefinite programs
- The Threshold for SDP-Refutation of Random Regular NAE-3SAT, Yash Deshpande, Andrea Montanari, Ryan O’Donnell, Tselil Schramm, Subhabrata Sen

- Minimizing discrepancy
- Sticky Brownian Rounding and its Applications to Constraint Satisfaction Problems, Sepehr Abbasi-Zadeh, Nikhil Bansal, Guru Guruganesh, Aleksandar Nikolov, Roy Schwartz, Mohit Singh