Theory Reading Group

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

Archived Schedules

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

 

Student-run site for the Theory & Algorithms Group in the CS Department at UIUC