Problem Seminar on Spectral Methods

Organizers
Damian Straszak and Nisheeth K. Vishnoi. In case of any questions, contact one of us by e-mail: name.surname@epfl.ch.

Goal
The main goal of this seminar is to discuss recent interesting results and open problems related to spectral methods in TCS.

Format and Topics
The format of the seminar will typically be a ~2h long presentation of a given paper (or multiple papers) which should also include stating research problems related to it. Topics of interest are: spectral graph theory, fast algorithms via analytic methods, applications of linear algebra and probability to combinatorial problems.

Schedule
The schedule is quite flexible and can be adjusted depending on the availability of participants. During the first seminar we will discuss possible dates.

Date	Venue	Speaker	Topic
04.10.2016	INF 211	Alon Gonen	"Escaping From Saddle Points" based on the paper by Rong Ge, Furong Huang, Chi Jin, Yang Yuan.

List of Papers
A tentative list of papers to be discussed during the seminar follows. If you are interesting in giving a talk and providing interesting open problems contact one of the organizers.

Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time by Yin Tat Lee, He Sun.
Pipage Rounding, Pessimistic Estimators and Matrix Concentration by Nicholas J. A. Harvey, Neil Olver.

Past Talks

Date	Venue	Speaker	Topic
28.09.2016, 15:00-17:00	INF 211	Ebrahimi Boroojeni Javad	"An Algorithm for Koml´os Conjecture Matching Banaszczyk’s Bound" based on the paper by Nikhil Bansal, Daniel Dadush, Shashwat Garg.

18.07.2016, 14:00-16:00	INF 211	Vaggelis Chatziafratis	"Generalized Preconditioning and Network Flow Problems" based on the paper by Jonah Sherman.

15.06.2016, 14:00-16:00	INF 211	Damian Straszak	"Expanders via Local Edge Flips" based on the paper by Zeyuan Allen-Zhu, Aditya Bhaskara, Silvio Lattanzi, Vahab Mirrokni, Lorenzo Orecchia

11.05.2016, 14:00-16:00	INF 211	Damian Straszak	"Interlacing Families IV: Bipartite Ramanujan Graphs of All Sizes" based on the paper by Adam W. Marcus, Nikhil Srivastava, Daniel A. Spielman.

17.05.2016, 14:00-16:00	INF 211	Damian Straszak	"Lifts, Discrepancy and Nearly Optimal Spectral Gap" based on the paper by Yonatan Bilu and Nathan Linial.

Back to my homepage.