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.
These meetings, which happen once a week amortized, are typically in the format of informal and interactive presentations on a white board
(and occasionally morph into conversations while walking up Uetliberg ).
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---and
does not already appear on our reading list (see below), 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
Other Papers on Our Tentative Reading List
A Rounds vs. Communication Tradeoff for Multi-Party Set Disjointness
Deterministic Distributed Edge Coloring via Hypergraph Maximal Matching
Symmetry Breaking in the Congest Model: Time- and Message-Efficient Algorithms for Ruling Sets
Three Notes on Distributed Property Testing
Improved Distributed Degree Splitting and Edge Coloring
Quadratic and Near-Quadratic Lower Bounds for the CONGEST Model
Near Optimal Approximate Shortest Paths and Transshipment
Derandomizing Local Distributed Algorithms under Bandwidth Restrictions
Improved Deterministic Distributed Construction of Spanners
Fast Plurality Consensus on Regular Expanders
Dynamic Analysis of the Arrow Distributed Directory Protocol in General Networks
A Distributed Learning Dynamics in Social Groups
Triangle Finding and Listing in CONGEST networks
Broadcasting in Noisy Radio Networks
The Power of Choice in Priority Scheduling
Communication Primitives in Cognitive Radio Networks
Greedy Routing and the Algorithmic Small-World Phenomenon
Clocked population protocols
Optimal Distance Labeling Schemes for Trees
Distributed Approximation of Maximum Independent Set and Maximum Matching
Distributed MST and Routing in Almost Mixing Time
Distributed MIS via All-to-All Communication
Testable Bounded Degree Graph Properties Are Random Order Streamable
Efficient Construction of Probabilistic Tree Embeddings
Deterministic Graph Exploration with Advice
Streaming Communication Protocols
Randomized Load Balancing on Networks with Stochastic Inputs
Preserving Distances in Very Faulty Graphs
Hardness of computing and approximating predicates and functions with leaderless population protocols
Bipartite Perfect Matching in Pseudo-Deterministic NC
Distributed Cycle Detection
Bicriteria Submodular Maximization in a few rounds
Composable coresets for matching and vertex cover
Almost optimal streaming algorithms for coverage problems
Online and Dynamic Algorithms for Set Cover
Efficient Massively Parallel Methods for Dynamic Programming
On the Complexity of Local Distributed Graph Problems
Uniform sampling through the Lovasz local lemma
How Well Do Local Algorithms Solve Semidefinite Programs?
Fully-Dynamic Minimum Spanning Forest with Improved Worst-Case Update Time
Dynamic Spanning Forest with Worst-Case Update Time
A ($2 + epsilon$)-Approximation for Maximum Weight Matching in the Semi-Streaming Model
Deterministic Parallel Algorithms for Fooling Polylogarithmic Juntas and the Lovasz Local Lemma
Find Your Place: Simple Distributed Algorithms for Community Detection
Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in $O(log^3 n)$ Worst Case Update Time
Improved Algorithmic Versions of the Lovasz Local Lemma
On Estimating Maximum Matching Size in Graph Streams
Online Lower Bounds via Duality
Efficient Algorithms for Constructing Very Sparse Spanners and Emulators
Polylogarithmic Bounds on the Competitiveness of Min-cost (Bipartite) Perfect Matching with Delays
Commutativity in the Algorithmic Lovasz Local Lemma
A New Framework for Distributed Submodular Maximization
A Distributed ($2+\epsilon$)-Approximation for Vertex Cover in $O(log \Delta/\epsilon log log \Delta)$ Rounds
Distributed Strong Diameter Network Decomposition: Extended Abstract
The Greedy Spanner is Existentially Optimal
Distributed MST in Log-Star Rounds of Congested Clique
Self-stabilizing Balls & Bins in Batches: The Power of Leaky Bins
Tight Bounds for Single-Pass Streaming Complexity of the Set Cover Problem
New Deterministic Approximation Algorithms for Fully Dynamic Matching
Optimal Principal Component Analysis in Distributed and Streaming Models
A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths
Distributed (\Delta+1)-Coloring in Sublogarithmic Rounds
Online Matching: Haste makes Waste!