Title: Inapproximability of Truthful Mechanisms via Generalizations of the VC Dimension Speaker: Gal Shahaf Affiliation: The Hebrew University of Jerusalem Abstract: Algorithmic mechanism design (AMD) studies the delicate interplay between computational efficiency, truthfulness, and economic[...]

SPEAKER: Ilya Razenshteyn (MIT) TITLE: Sketching and Embedding are Equivalent for Norms ABSTRACT: Imagine the following communication task. Alice and Bob each have a point from a metric space. They want to transmit a few[...]

Approximating Low-Stretch Spanners abstract: Despite significant recent progress on approximating graph spanners (subgraphs which approximately preserve distances), there are still several large gaps in our understanding. We give new results for two of them: approximating[...]