# Schedule

### Spring 2019

Meetings: Every Tuesday from 11am to 12pm in 3401 SC

We are covering Cygan et al.’s Parameterized algorithms.

Date | Speaker | Content |
---|---|---|

19 Feb 2019 | Qizheng He | Introduction and some kernels (1-2.2) |

26 Feb 2019 | Pooja Kulkarni | More kernels and crown decomposition (2.2-2.3) |

05 March 2019 | No reading group due to qualification exams | |

12 March 2019 | Forest Yang | Crown decomposition (2.3) |

19 March 2019 | Spring break 🌻 | |

26 March 2019 | Rucha Kulkarni | Bounded search trees (3.1-3.4) |

2 April 2019 | Bolton Bailey | Randomized methods (5.1-5.3) |

9 April 2019 | Meghan Shanks | Randomized methods continued (5.5-5.6) |

16 April 2019 | Ian Ludden | Introduction to treewidth (7.1-7.2) |

23 April 2019 | Robert Andrews | Dynamic programming & treewidth (7.3) |

30 April 2019 | Mitchell Jones | Courcelle’s theorem (7.4) |

# Archived Schedules

### Fall 2018

Meetings: Every Tuesday from 15:30 to 16:30 in 3401 SC

We are covering Moitra’s Algorithmic Aspects of Machine Learning

Date | Speaker | Content |
---|---|---|

11 Sep 2018 | Meghan Shanks | Introduction and Overview |

18 Sep 2018 | Forest Yang | SVD and Intro to Nonegative Matrix Factorization (Sections 2.1 and 2.2) |

25 Sep 2018 | Pooja Kulkarni | Stability and Separability (Section 2.3) |

2 Oct 2018 | Calvin Beideman | Topic Models (Section 2.4) |

9 Oct 2018 | Qizheng He | Sparse Recovery: Introduction and Incoherence (Sections 5.1 and 5.2) |

16 Oct 2018 | Meghan Shanks | Pursuit Algorithms and Prony’s Method (Sections 5.3 and 5.4) |

23 Oct 2018 | Kent Quanrud | Prony’s Method and Compressed Sensing (Sections 5.4 and 5.5) |

30 Oct 2018 | Qizheng He | Sparse Coding: Introduction and the Undercomplete Case (Sections 6.1 and 6.2) |

6 Nov 2018 | Pooja Kulkarni | Gradient Descent (Section 6.3) |

13 Nov 2018 | Bolton Bailey | The Overcomplete Case (Section 6.4) |

20 Nov 2018 | No Meeting 🦃 | |

27 Nov 2018 | Forest Yang | TBD |

4 Dec 2018 | TBD | TBD |

### Summer 2018

Meetings: Every Wednesday from 13.00 to 14.30 in 3102 SC

We are covering favorite papers and theorems.

Date | Speaker | Content |
---|---|---|

23 May 2018 | Zander Kelley | Sparsest Cut and Tension Applications (1, 2) |

30 May 2018 | Mitchell Jones | Counting Spanning Trees |

06 Jun 2018 | Rucha Kulkarni | Smooth Complexity of Local Max Cut |

13 Jun 2018 | Robert Andrews | Hitting Set Derandomization of BPP |

20 Jun 2018 | Meghan Shanks | Quantum Algorithms Intro and Simon’s Algorithm |

27 Jun 2018 | No Meeting ✈️✈️ | |

04 Jul 2018 | No Meeting 🎉🇺🇸 | |

11 Jul 2018 | Ian Ludden | Doubly Balanced Connected Graph Partitioning (conference version) |

18 Jul 2018 | Bolton Bailey | Polynomial Upper Confidence Trees |

### Spring 2018

Meetings: Every Tuesday from 16.00 to 17.30 in 3401 SC

We are going through the set of lectures notes on Hardness of Approximation.

Date | Speaker | Content |
---|---|---|

23 Jan 2018 | Zander Kelley | Lecture 1 & 2: Introduction and the PCP theorem. |

30 Jan 2018 | Meghan Shanks | Lecture 2 & 3: Expanders |

06 Feb 2018 | Robert Andrews | Lecture 3 & 4: Expanders and Degree Reduction. |

13 Feb 2018 | Rucha Kulkarni | Lecture 4 & 5: Expanderization and Gap Amplification |

20 Feb 2018 | Bolton Bailey | Lecture 5 & 6: Gap Amplification |

27 Feb 2018 | Vasilis Livanos | Lecture 6 & 7: Amplification and Alphabet Reduction |

06 Mar 2018 | No Meeting (Quals) | |

13 Mar 2018 | Zander Kelley | Lecture 8 & 9: Finishing the proof of the PCP theorem |

20 Mar 2018 | Break 🎉 | |

27 Mar 2018 | Sahand Mozaffari | Lecture 10 & 11: Hardness of Approximation and Label Cover |

03 Apr 2018 | Mitchell Jones | Lecture 12 & 13: Confuse/Match Games (see Feige-Kilian paper for full proof) |

10 Apr 2018 | Xilin Yu | Lecture 14 & 15: Hardness of Set Cover |

17 Apr 2018 | Meghan Shanks | Lecture 15 & 16: Long Codes & Håstad’s 3-query PCP |

24 Apr 2018 | Robert Andrews | Lecture 18 & 19: UGC and Max-Cut |

### Fall 2017

Meetings: Every Tuesday from 15.00 to 16.30 in 3124 SC

We are going through Scalable Algorithms for Data and Network Analysis. A free PDF is available from the publisher when on university internet.

Date | Speaker | Content |
---|---|---|

05 Sep 2017 | Xilin Yu | Chapter 1/2: Overview of Problems and Techniques |

12 Sep 2017 | Robert Andrews | Chapter 5.1, 5.2: Centerpoints and Scalable Algorithms for Centerpoints |

19 Sep 2017 | Rucha Kulkarni | Chapter 5.2, 5.3: Radon Evolution and Geometric Separators |

26 Sep 2017 | Manuel Torres | Chapter 5.3, 5.4: Analysis of Sphere Separators, Johnson-Lindenstrauss |

03 Oct 2017 | Ian Ludden | Chapter 5.5, 5.6: Scalable Geometric Divide and Conquer, Vertex and Edge separators |

10 Oct 2017 | Meghan Shanks | Chapter 6.1, 6.2: Spectrally Similar Networks & basic properties |

17 Oct 2017 | Vasilis Livanos | Chapter 6.4: Graph Inequalities and Low-Stretch spanning trees |

24 Oct 2017 | Bolton Bailey | Chapter 6.5: Spectral Approximation and Edge Sampling |

31 Oct 2017 🎃 | Ross Vasko | Chapter 4.1: Local Algorithms for Network Analysis |

7 Nov 2017 | Zander Kelley | Chapter 4.2: Local Clustering and Random Walks |

14 Nov 2017 | Mitchell Jones | Solving Maxcut using SDP (see Chapter 1 in the Gartner and Matousek book) |

21 Nov 2017 🦃 | Break | |

28 Nov 2017 | Xilin Yu | Primal-Dual Method and applications in min-cost perfect matching |

5 Dec 2017 | Patrick Lin | Boolean Halfspace Learning via Fourier Analysis (see [KKMS]) |

12 Dec 2017 | Sahand Mozaffari | Streaming algorithms |

### Spring 2017

In Fall 2016 and Spring 2017, we went through Jonathan Kelner’s Algorithmist’s Toolkit.

Meeting time: Mondays from 3:30 to 5:00 in 3102

DATE | SPEAKER | CONTENT |
---|---|---|

01/30/17 | Shant | Lecture 8: PageRank algorithm (and non-blocking flows) — Room 4405 |

02/06/17 | Sahand | Lecture 9 : Spectral Sparsification |

02/13/17 | Ziwei | Lectures 10, 11 &12 : Introduction to Convex Geometry |

02/20/17 | Ziwei / Mitchell | Lecture 12 : Fritz John’s Theorem, Introduction to Brunn-Minkowski |

03/01/17 | Mitchell | Lecture 13: Isoperimetric Inequality and Grunbaum’s Theorem |

03/08/17 | Shweta | Lectures 14 & 15: Approximating the Volume of a Convex Body |

03/13/17 | Kent | Lecture 16: Concentration of Measure |

03/20/17 | Spring break | |

03/27/17 | Sahand | Lecture 17: Johnson-Lindenstrauss theorem |

04/03/17 | Sahand, Mitchell | Lecture 17: Dvoretsky’s theorem & \(\varepsilon\)-nets |

04/10/17 | Xilin | Lecture 18: Introduction to lattices, Minkowski’s Theorem and Dirichlet’s Approximation Theorem |

04/17/17 | Muhammed | Lecture 19 & 20: Shortest vector problem and the LLL algorithm |

04/24/17 | Mitchell | Lecture 21: Iterative methods, steepest descent |

05/1/17 | Shant | Lecture 22: Analysis of steepest descent, conjugate gradients |

### Fall 2016

Meetings: Every Thursday from 3:30 to 5:00 in 3102

Date | Speaker | Content |
---|---|---|

10/29/16 | Shant Boodaghians | Sessions 1 and 2: Introduction to Spectral Graph Theory |

11/03/16 | Mitchell Jones | Session 3: Courant-Fischer formula, Rayleigh quotients and Cheerger’s inequality |

11/10/16 | Alli Niles | Sessions 4 and 5: Random Walks, Convergence and Monte-Carlo Methods |

11/17/16 | Muhammad Khan | Sessions 5: Approximating the Matrix Permanent |

11/24/16 | Thanksgiving | |

12/01/16 | Xilin Yu | Session 6: Expander Graphs |

12/08/16 | Ziwei Ji | Session 7: Fast Clustering, Lovasz-Simonovits Theorem |