Title: Towards Model-Agnostic Algorithm Design

Abstract:

Over the past decades, progress in the field of fine-grained algorithms has primarily been driven by the interplay between two factors: 

(i) The study of certain "canonical" computational problems, such as matching, graph coloring, maxflow, mincut, shortest path and clustering, among others. The quest for improving the state-of-the-art on these problems has led to the discovery of powerful new techniques for algorithm design.

(ii) The introduction of a range of "computational models", such as dynamic, sublinear, distributed, online and streaming settings, among others. These models are motivated by the challenges faced in real-world applications, and they capture: how the input data is revealed, how the output data is returned, and the computational resources an algorithm has access to, whose cost of usage we wish to minimize. 

In this talk, I will outline the following research vision: To develop, exploit, and understand the limitations of "model-agnostic algorithms". These are algorithms which lead to near-optimal guarantees for some canonical problem, simultaneously across a number of different computational models. I will showcase some exciting advances towards this research vision, by presenting my recent work on some canonical computational problems (maximum matching and edge coloring) and textbook algorithm design paradigms (greedy and linear programming).