Theory Coffee

Theory coffee is an informal seminar on theoretical computer science, with presentations by PhD students, postdocs and faculty. If you would like to give talk, please write to Michael Kapralov (michael dot kapralov at epfl dot ch).

Time and place: Fridays at 3.15pm on zoom

Mailing list and calendar: There is a mailing list where the announcements of upcoming talks as well as other theory-related information appear. To subscribe to this list, send an email (can be empty) to theory-announce-subscribe@listes.epfl.ch.

Upcoming talks:

Friday, March 5th, Paritosh Garg, Robust Algorithms against Adversarial Injections
I will present a new model that we study that is sandwiched somewhere between adversarial-order streams and random-order streams with the motivation of designing robust algorithms. Then, I will present results on two problems namely maximum matching and submodular maximization in this model. Eventually, I will discuss some interesting open problems that arise.
This is a joint work with Sagar Kale, Lars Rohwedder and Ola Svensson.

Friday, March 12th, Jakab Tardos

Friday, March 19th, Xinrui Jia

Friday, March 26th, Akash Kumar

Friday, April 9th, Jan Hazla

Past talks:

Friday, February 26th, Navid Nouri, Graph Spanners by Sketching in Dynamic Streams and the Simultaneous Communication Model
Graph sketching is a powerful technique in dynamic graph streams that has enjoyed considerable attention in the literature in recent years, and has led to near optimal dynamic streaming algorithms for many fundamental problems such as connectivity, cut and spectral sparsifiers. In the first part of this talk, we are going to talk about the first algorithm that achieves sub-linear stretch in a single pass, using almost linear space. Then, we are going to discuss the space-stretch trade-offs when more space is allowed. Finally, we will talk about the simultaneous communication model and propose and analyze the guarantees of our protocol, where each player can communicate small messages.
Joint work with Arnold Filtser and Michael Kapralov

Friday, February 19th, Lars Rohwedder, A (2 + epsilon)-approximation algorithm for preemptive weighted flow time on a single machine
In a recent breakthrough in scheduling, Batra, Garg, and Kumar gave the first constant approximation algorithm for minimizing the sum of weighted flow times. Wiese and I (STOC'21) managed to improve this large unspecified constant to 2 + epsilon. I will give a very graphic presentation of the algorithmic techniques behind this.

Friday, February 12th, Aida Mousavifar, Spectral Clustering Oracles in Sublinear Time
Given a graph G that can be partitioned into k disjoint expanders with outer conductance upper bounded by eps, can we efficiently construct a small space data structure that allows quickly classifying vertices of G according to the expander (cluster) they belong to? Formally, we would like an efficient local computation algorithm that misclassifies at most an O(eps) fraction of vertices in every expander. We refer to such a data structure as a spectral clustering oracle. In this talk, first I will explain how to design a sublinear time oracle that provides dot product access to the spectral embedding of G. Then I will show how to design a spectral clustering oracle with sublinear time using the dot product oracle.

Friday, February 5th, at 1.15pm (note unusual time) Siddhartha Jain, Unambiguous DNFs from Hex
I'll be talking about my work for my semester project supervised by Mika Göös, in collaboration with Shalev Ben-David & Robin Kothari. We exhibit an unambiguous k-DNF formula that requires CNF width \tOmega(k^{1.5}). Our construction is inspired by the board game Hex and it is vastly simpler than previous ones, which achieved at best an exponent of 1.22. Our result is known to imply several other improved separations in query and communication complexity.