QTW Workshop on Beyond Worst Case Analysis

About the Series

The Quarterly Theory Workshop brings in several theoretical computer science experts present their perspective and research on a common theme.  Chicago area researchers with interest in theoretical computer science are invited to attend.  The technical program is in the morning and includes coffee and lunch.  The afternoon of the workshop will allow for continued discussion between attendees and the speakers.


This Quarterly Theory Workshop is on the theme of  Beyond Worst-Case Analysis. The speakers will discuss various natural models of real-life instances, present new algorithms for these models, and talk about the limitations of  these models. The speakers are Yury Makarychev, Ankur Moitra, and Tim Roughgarden.


  • Location: ITW Lecture Hall (1st floor), Ford Motor Company Engineering Design Center (map), Northwestern U, 2133 Sheridan Rd, Evanston, IL 60208.
  • Transit: Noyes St. Purple Line (map).
  • Parking: Validation for North Campus Parking Garage (map) available at workshop.


Registration is free. Please register at https://goo.gl/forms/OBh61KORT8hryksw1 if you plan to attend.


Wednesday, May 24
9:00 am –  9:30 am: Breakfast
9:30 am – 10:15 am: Tim Roughgarden — How Hard is Inference for Structured Prediction?
10:15 am – 11:30 am: Break
10:30 am – 11:15 am: Ankur Moitra – How Robust are Reconstruction Thresholds for Community Detection?
11:15 am – 11:30 am: Break
11:30 am –  12:15pm: Yury Makarychev –  Algorithms for Stable and Perturbation-Resilient Problems
12:15 pm – 2:00 pm: Lunch
The videos from the talks can be found here.

Titles and Abstracts

Speaker: Tim Roughgarden
Title: How Hard Is Inference for Structured Prediction? 
Abstract: Structured prediction tasks in machine learning involve the simultaneous prediction of multiple labels. This is often done by maximizing a score function on the space of labels, which decomposes as a sum of pairwise elements, each depending on two specific labels. The goal of this work is to develop a theoretical explanation of the empirical effectiveness of heuristic inference algorithms for solving such structured prediction problems. We study the minimum-achievable expected Hamming error in such problems, highlighting the case of 2D grid graphs, which are common in machine vision applications. Our main theorems provide tight upper and lower bounds on this error, as well as a polynomial-time algorithm that achieves the bound.
Joint work with Amir Globerson, David Sontag, and Cafer Yildirim.

Speaker: Ankur Moitra
Title: How Robust are Reconstruction Thresholds for Community Detection?
Abstract: The stochastic block model is one of the oldest and most ubiquitous models for studying clustering and community detection. Here we revisit it from the perspective of semirandom models where we allow an adversary to make `helpful’ changes that strengthen ties within each community and break ties between them. We show a surprising result that these `helpful’ changes can shift the information-theoretic threshold, making the community detection problem strictly harder.

Conceptually, any algorithm meeting the exact information-theoretic threshold in the average-case model must exploit the precise structure of the noise. These results point to an interesting new direction: Can semirandom (and related) models help explain why some algorithms are preferred to others in practice, in spite of gaps in their average-case performance?

Speaker: Yury Makarychev
Title: Algorithms for Stable and Perturbation-Resilient Problems
Abstract: We study the notion of stability and perturbation resilience introduced by Bilu and Linial (2010) and Awasthi, Blum, and Sheffet (2012). A combinatorial optimization problem is α-stable or α-perturbation-resilient if the optimal solution does not change when we perturb all parameters of the problem by a factor of at most α. We present improved algorithms for stable instances of various clustering and optimization problems, including k-means, k-median, Max Cut, and Minimum Multiway Cut. We also show several hardness results.
The talk is based on joint papers with Haris Angelidakis, Konstantin Makarychev, and Aravindan Vijayaraghavan.