Schedule

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

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

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

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

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

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

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

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