Reading Group on Discrete and Distributed Algorithms

In our reading group, we read and discuss recent papers whose topic revolves around discrete and distributed algorithms, broadly interpreted. The format is informal and interactive presentations on a white board. Our goal is to get an in-depth understanding of one paper per meeting (with a top-down approach, starting from the high-level picture but also going down to some of the proof details, as much as the time admits). Our meetings are (usually) on Fridays 1 to 4 pm, in CAB G34. Everyone is welcome to join.

Suggestions: We welcome suggestions. If you know of a paper that might be of interest to us (your work or that of others), please let us know by filling out this form. If you happen to be in Zurich and would be interested in explaining the paper yourself, even better! Please indicate that in the form, or by sending an email to Mohsen, and we'll try to find a time slot for your presentation, as soon as possible.

Upcoming

...

Past

07/12/2019 Christoph Grunau (ETH): Local Computation Algorithms for Spanners (ITCS'19)


06/21/2019 Vaclav Rozhon (ETH): Expander Decomposition and Pruning: Faster, Stronger, and Simpler (SODA'19)


06/12/2019 Sebastian Brandt (ETH): Towards the Locality of Vizing's Theorem (STOC'19)


06/07/2019 Manuela Fischer (ETH): Distributed Local Approximation Algorithms for Maximum Matching in Graphs and Hypergraphs (FOCS'19)


05/24/2019 Julian Portmann (ETH): Thorup-Zwick Emulators as Hopsets (IPL'18) and Linear-Size Hopsets with Small Hopbound, and Constant-Hopbound Hopsets in RNC (SPAA'19)


05/23/2019 Davin Choo (ETH): Dynamic Algorithms for the Massively Parallel Computation Model (SPAA'19)


03/15/2019 Manuela Fischer (ETH): Distributed k-center via sublinear Coresets


03/01/2019 Julian Portmann (ETH): Improved Network Decompositions using Small Messages with Applications on MIS, Neighborhood Covers, and Beyond


01/25/2019 Sebastian Brandt (ETH): Lower bounds for maximal matchings and maximal independent sets (FOCS'19)


01/18/2019 Vaclav Rozhon (ETH): Approximating Edit Distance Within Constant Factor in Truly Sub-Quadratic Time (FOCS'18)


12/14/2018 David Wajc (CMU): The Greedy Algorithm is *Not* Optimal for Online Edge Coloring (FOCS'19)


12/07/2018 Krzystof Nowicki (U. Wroclaw): Computing exact minimum cuts without knowing the graph (ITCS'18)


11/30/2018 Yi-Jun Chang (U. Michigan): Distributed Triangle Detection via Expander Decomposition (SODA'19)


11/15/2018 Manuela Fischer (ETH): Sublinear Algorithms for (Delta+1) Vertex Coloring (SODA'19)


11/09/2018 Sebastian Brandt (ETH): An Automatic Speedup Theorem for Distributed Problems (PODC'19)


11/05/2018 Barbara Geissmann (ETH): Parallel Minimum Cuts in Near-linear Work and Low Depth (SPAA'18)


10/11/2018 Yitong Yin (Nanjing University): Local Distributed Sampling (PODC'18)


09/28/2018 Morteza Zadimoghaddam (Google Reserach, Zurich): Submodular Maximization with Optimal Approximation, Adaptivity and Query Complexity (SODA'19)


08/24/2018 Giorgi Nadiradze (ETH & IST Austria): Relaxed Schedulers Can Efficiently Parallelize Sequential Algorithms (PODC'18)


08/13/2018 Shahbaz Khan (U. Vienna): Simple Dynamic Algorithms for Maximal Independent Set and Other Problems


08/10/2018 Mohsen Ghaffari (ETH): Sparsifying Distributed Algorithms with Ramifications in Massively Parallel Computation and Centralized Local Computation (SODA'19)


08/03/2018 Michal Dory (Technion): Distributed Approximation of Minimum $k$-edge-connected Spanning Subgraphs (PODC'18)


07/30/2018 Przemysław Uznański (ETH): A Framework for Searching in Graphs in the Presence of Errors (SOSA'19)


07/27/2018 Slobodan Mitrovic (ETH): Fractional Set Cover in the Streaming Model (APPROX/RANDOM'17)


06/08/2018 Jara Uitto (ETH): Parallel Graph Connectivity in Log Diameter Rounds (FOCS'18)


06/01/2018 Przemysław Uznański (ETH): Population Protocols Are Fast


04/16/2018 Danupon Nanongkai (KTH): Distributed Exact Weighted All-Pairs Shortest Paths in O(n^{5/4}) Rounds (FOCS'17)


03/23/2018 Manuela Fischer (ETH): Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs (SODA'19)


03/16/2018 Sebastian Brandt (ETH): New Classes of Distributed Time Complexity (STOC'18)


12/22/2017 Krzysztof Nowicki (U. Wraclaw): MST in O(1) Rounds of the Congested Clique (SODA'18)


12/15/2017 Slobodan Mitrovic (EPFL): Round Compression for Parallel Matching Algorithms (STOC'18)


12/13/2017 Michael Elkin (Ben Gurion U.): Locally-Iterative Coloring below Szegedy-Vishwanathan's Barrier (PODC'18)


12/08/2017 Mohsen Ghaffari (ETH): On Derandomizing Local Distributed Algorithms (FOCS'18)


12/01/2017 Manuela Fischer (ETH): An Optimal Distributed (Delta+1)-Coloring Algorithm? (STOC'18)


11/24/2017 Manuela Fischer (ETH): Distributed (Delta+1)-Coloring in Sublogarithmic Rounds (STOC'16)


11/09/2017 Omri Ben-Eliezer (Tel-Aviv U.): Testing Hereditary Graph Properties (FOCS'05)


11/03/2017 No meeting because of the STOC'18 Deadline

.
10/27/2017 Ralph Keusch (ETH): A new upper bound on the game chromatic index of graphs (J. Combinatorics'18)


10/20/2017 No meeting because of FOCS'17/DISC'17

.
10/12/2017 Sebastian Brandt (ETH): A Lower Bound for the Distributed Lovasz Local Lemma (STOC'16)


10/06/2017 Omri Ben-Eliezer (Tel-Aviv U.): Testing Patterns in Multi-Dimensional Arrays (ICALP'17)


09/29/2017 Jakub Tarnawski (EPFL): The Matching Problem in General Graphs is in Quasi-NC (FOCS'17)


09/22/2017 Jara Uitto (ETH): A Time Hierarchy Theorem for the LOCAL Model (FOCS'17)


09/15/2017 Nina Kamcev (ETH Math): On the Erdos-Szekeres Convex Polygon Problem (J. American Math Society'17)


09/04/2017 Przemysław Uznański (ETH): All Pairs Shortest Paths using Bridging Sets and Rectangular Matrix Multiplication (FOCS'98)


09/01/2017 Manuela Fischer (ETH): What can be sampled locally? (PODC'17)


08/29/2017 Frederik Mallmann-Trenn (MIT): Ignore or Comply? On Breaking Symmetry in Consensus (PODC'17) and On coalescence time in graphs--When is coalescing as fast as meeting? (SODA'19)


08/22/2017 Giorgi Nadiradze (ETH & IST Austria): The Power of Choice in Priority Scheduling (PODC'17)


08/18/2017 Jason Li (CMU): Distributed Exact Weighted All-Pairs Shortest Paths in $\tilde O(n^{5/4})$ Rounds (FOCS'17)


08/10/2017 Christiana Lymouri (ETH): Simple and Near-Optimal Distributed Coloring of Sparse Graphs (DISC'17)


08/07/2017 Przemysław Uznański (ETH): Fast Space Optimal Leader Election in Population Protocols (SODA'18)


08/04/2017 Peter Davies (Warwick U.): Exploiting Spontaneous Transmissions for Broadcasting and Leader Election in Radio Networks (PODC'17)


07/31/2017 Ahad Zehmakan (ETH): Majority Model: Random Regular Graphs (LATIN'18)


07/21/2017 Pascal Su (ETH): Perfect Matchings in $O(n)$ Time in Random and Pseudorandom Graphs


07/20/2017 Manuela Fischer (ETH): Tight Analysis of Randomized Greedy MIS (SODA'18)


07/07/2017 Johannes Lengler (ETH): Explosion and Distances in Scale-free Percolation


06/30/2017 Christiana Lymouri (ETH): LCL problems on Grids (PODC'17)


06/29/2017 Jason Li (CMU): Distributed Exact Shortest Paths in Sublinear Time (STOC'17)


06/12/2017 Jara Uitto (ETH): A Simple Deterministic Distributed MST Algorithm, with Near-Optimal Time and Message Complexities (PODC'17) and Time- and Message-Optimal Distributed Algorithm for Minimum Spanning Trees (STOC'17)


06/05/2017 Mohsen Ghaffari (ETH): Sublogarithmic Distributed Algorithms for Lovasz Local lemma, and the Complexity Hierarchy (DISC'17)


06/02/2017 Paolo Penna (ETH): LOCAL Distributed Algorithms for Selfish Agents


05/26/2017 Mohsen Ghaffari (ETH): Deterministic Distributed ($\Delta + o(\Delta)$)-Edge-Coloring, and Vertex-Coloring of Graphs with Bounded Diversity (PODC'17)


04/20/2017 Manuela Fischer (ETH): A Constructive Proof of the General Lovasz Local Lemma (JACM'10)


04/07/2017 Christiana Lymouri (ETH): Local Conflict Coloring (FOCS'16)


03/24/2017 Jara Uitto (ETH): Three Colors Suffice: Conflict-Free Coloring of Planar Graphs (SODA'17)


03/17/2017 Mohsen Ghaffari (ETH): Optimal Dynamic Distributed MIS (PODC'16) and Greedy Sequential Maximal Independent Set and Matching are Parallel on Average (SPAA'12)