Algorithms Reading Group (ARG)

We meet every Friday from 10:30-noon in B13 MLH. We discuss recent research papers in Algorithms, Computational Geometry, Distributed Computing, etc. Generally, we pick papers from conferences like (but not limited to) PODC, ICALP, SoCG, SODA, DISC, FOCS, etc. Below is the schedule for the Spring 2018 session. Fall 2017, Spring 2017, Fall 2016, Spring 2016 and Fall 2015 schedules follow.

SPRING 2018 Schedule

Date Presenter Paper/Topic
1/26 Shreyas Pai

Fooling Views: A New Lower Bound Technique for Distributed Computations under Congestion

2/16 Tanmay Inamdar Algorithms for Facility Location Problems with Outliers

FALL 2017 Schedule

Date Presenter Paper/Topic
9/1 Tanmay Inamdar Randomized Composable Coresets for Matching and Vertex Cover
9/29 Shreyas Pai Randomized Composable Core-sets for Distributed Submodular Maximization
10/27 Sikder Huq Locally Self-Adjusting Skip Graphs

SPRING 2017 Schedule

Date Presenter Paper/Topic
2/24 Talal Riaz

Omega(sqrt(n)) lower bound for distributed Minimum Spanning Tree construction in the CONGEST model (B11 MLH)

FALL 2016 Schedule

Date Presenter Paper/Topic
9/2 Shreyas Pai

A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization (B11 MLH)

9/9 No meeting  
9/16 Sayan Bandyapadhyay

New epsilon-net Constructions

9/23 No meeting  
9/30 Tanmay Inamdar The Capacitated K-Center Problem


SPRING 2016 Schedule

Date Presenter Paper/Topic
2/5 Sayan Bandyapadhyay

On Variants of k-means Clustering

2/12 Tanmay Inamdar Improved Deterministic Algorithms for Linear Programming in Low Dimensions
2/19 Talal Riaz

An Improved Distributed MIS Algorithm

2/26 No meeting  
3/4 Santanu Bhowmick LP-Based Algorithms for Capacitated Facility Location
3/11 Vivek Sardeshmukh Almost Optimal Distributed Algorithms for Large-Scale Graph Problems
3/18 Spring break  No meeting
3/25 Sriram Pemmaraju

Communication and Information complexity, Ref. [1], [2]

4/1 No meeting


4/8 No meeting  

Sriram Pemmaraju

 Communication and Information complexity continued.., Ref. [1], [2]

Thamer Alsulaiman

Byzantine General problem, clocks synchronization with byzantine clocks

4/29 Talal Riaz

A Distributed (2 + ε)-Approximation for Vertex Cover in O ( log ∆ / (ε log log ∆)) Rounds

5/6 No meeting  


FALL 2015 Schedule




9/4 Kasturi Varadarajan

Sherali-Adams and Lasserre LP/SDP hierarchies notes


No meeting due to CS Colloquium talk by Huy Ngueyen (TTIC)

Distributed Machine Learning


Sriram Pemmaraju Proof of the Power of Two Choices
9/25 No meeting


10/2 No meeting                                  ------
10/9 Sanvesh Srivastava Variable Selection in Bayesian Statistics - Part 1
10/16 Sanvesh Srivastava Variable Selection in Bayesian Statistics - Part 2
10/23 Sayan Bandyapadhyay

Smaller Coresets for k-median and k-means Clustering

10/30 Vivek Sardeshmukh A unifying framework for L_0-sampling algorithms
11/6 No meeting due to 2015 Grad Research Symp.                                  ------
11/13 No meeting                                  ------
11/20 No meeting                                  ------
11/27 No meeting - Thanksgiving                                  ------