# Current Schedule

### 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 | |

20 Mar 2018 | Break 🎉 | |

27 Mar 2018 | TBD | |

03 Apr 2018 | TBD | |

10 Apr 2018 | TBD | |

17 Apr 2018 | TBD | |

24 Apr 2018 | TBD | |

01 May 2018T | TBD |

### 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 |

# Archived Schedules

### 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 |