**About the Series**

**Synopsis**

**Logistics **

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

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

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