Mohsen Ghaffari


I am an Assistant Professor in the Computer Science department of ETH Zurich. Before joining ETH, I received my PhD from the EECS department of MIT in 2016. My research is in theoretical computer science, with a focus on distributed algorithms, parallel algorithms, and network algorithms.

I am grateful for the generous support of the European Research Council (starting grant DistMaP, 2019-2024), the Swiss National Foundation (project grant 200021_184735, 2019-2023), and Google (Faculty Research Award, 2019).


Curriculum Vitae [PDF]


Mohsen

Contact information:

CAB G32.1, Universitatstrasse 6,
8092 Zurich, Switzerland.

Phone: +41-44-6327247
Email: my-last-name at inf.ethz.ch

Assistant: Andrea Salow

 

 

Research Group


See also our

Reading Group





Professional
Activities



Teaching



Publications

  • Mohsen Ghaffari, Krzysztof Nowicki, and Mikkel Thorup
    Faster Algorithms for Edge Connectivity via Random 2-Out Contractions
    ACM-SIAM Symposium on Discrete Algorithms (SODA) 2020.

  • Mohsen Ghaffari and Julian Portmann
    Improved Network Decompositions using Small Messages with Applications on MIS, Neighborhood Covers, and Beyond
    International Symposium on DIStributed Computing (DISC) 2019.

  • Ruben Becker, Yuval Emek, Mohsen Ghaffari, and Christoph Lenzen
    Distributed Algorithms for Low Stretch Spanning Trees
    International Symposium on DIStributed Computing (DISC) 2019.

  • Mohsen Ghaffari, Fabian Kuhn, and Jara Uitto
    Conditional Hardness Results for Massively Parallel Computation from Distributed Lower Bounds
    IEEE Symposium on Foundations of Computer Science (FOCS) 2019.

  • Yi-Jun Chang, Manuela Fischer, Mohsen Ghaffari, Jara Uitto, and Yufan Zheng
    The Complexity of (Delta + 1) Coloring in Congested Clique, Massively Parallel Computation, and Centralized Local Computation
    ACM Symposium on Principles of Distributed Computing (PODC) 2019.
    Best Student Paper Award at PODC'19.

  • Mohsen Ghaffari and Fabian Kuhn
    On the Use of Randomness in Local Distributed Graph Algorithms
    ACM Symposium on Principles of Distributed Computing (PODC) 2019.

  • Michal Dory and Mohsen Ghaffari
    Improved Distributed Approximations for Minimum-Weight Two-Edge-Connected Spanning Subgraph
    ACM Symposium on Principles of Distributed Computing (PODC) 2019.

  • Philipp Bamberger, Mohsen Ghaffari, Fabian Kuhn, Yannic Maus, and Jara Uitto
    On the Complexity of Distributed Splitting Problems
    ACM Symposium on Principles of Distributed Computing (PODC) 2019.

  • Mohsen Ghaffari, Silvio Lattanzi, and Slobodan Mitrovic
    Improved Parallel Algorithms for Density-Based Network Clustering
    International Conference on Machine Learning (ICML) 2019.

  • Mohsen Ghaffari and Ali Sayyadi
    Distributed Arboricity-Dependent Graph Coloring via All-to-All Communication
    International Colloquium on Automata, Languages and Programming (ICALP) 2019.

  • John Augustine, Mohsen Ghaffari, Robert Gmyr, Kristian Hinnenthal, Fabian Kuhn, Jason Li, Christian Scheideler
    Distributed Computation in Node-Capacitated Networks
    ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) 2019.

  • Mohsen Ghaffari and Jara Uitto
    Sparsifying Distributed Algorithms with Ramifications in Massively Parallel Computation and Centralized Local Computation
    ACM-SIAM Symposium on Discrete Algorithms (SODA) 2019.
    [arXiv]

  • Mohsen Ghaffari
    Distributed Maximal Independent Set using Small Messages
    ACM-SIAM Symposium on Discrete Algorithms (SODA) 2019.

  • Mohsen Ghaffari and David Wajc
    Simplified and Space-Optimal Semi-Streaming for (2+epsilon)-Approximate Matching
    Symposium on Simplicity in Algorithms (SOSA) 2019.
    [arXiv]

  • Mohsen Ghaffari, David Harris, and Fabian Kuhn
    On Derandomizing Local Distributed Algorithms
    IEEE Symposium on Foundations of Computer Science (FOCS) 2018.
    [arXiv]

  • Mohsen Ghaffari and Fabian Kuhn
    Derandomizing Distributed Algorithms with Small Messages: Spanners and Dominating Set
    International Symposium on DIStributed Computing (DISC) 2018.

  • Mohsen Ghaffari and Fabian Kuhn
    Distributed MST and Broadcast with Fewer Messages, and Faster Gossiping
    International Symposium on DIStributed Computing (DISC) 2018.

  • Manuela Fischer and Mohsen Ghaffari
    A Simple Parallel and Distributed Sampling Technique: Local Glauber Dynamics
    International Symposium on DIStributed Computing (DISC) 2018.

  • Mohsen Ghaffari and Jason Li
    New Distributed Algorithms in Almost Mixing Time via Transformations from Parallel Algorithms
    International Symposium on DIStributed Computing (DISC) 2018.

  • Guy Even, Mohsen Ghaffari, and Moti Medina
    Distributed Set Cover Approximation: Primal-Dual with Optimal Locality
    International Symposium on DIStributed Computing (DISC) 2018.

  • Andrea Clementi, Mohsen Ghaffari, Luciano Guala, Emanuele Natale, Francesco Pasquale, and Giacomo Scornavacca
    A Tight Analysis of the Parallel Undecided-State Dynamics with Two Colors
    Mathematical Foundations of Computer Science (MFCS) 2018.

  • Mohsen Ghaffari, Themis Gouleakis, Christian Konrad, Slobodan Mitrovic, and Ronitt Rubinfeld
    Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover
    ACM Symposium on Principles of Distributed Computing (PODC) 2018.

  • Mohsen Ghaffari and Johannes Lengler
    Nearly-Tight Analysis for 2-Choice and 3-Majority Consensus Dynamics
    ACM Symposium on Principles of Distributed Computing (PODC) 2018.

  • Mohsen Ghaffari and Krzysztof Nowicki
    Congested Clique Algorithms for the Minimum Cut Problem
    ACM Symposium on Principles of Distributed Computing (PODC) 2018.

  • Mohsen Ghaffari, Juho Hirvonen, Fabian Kuhn, and Yannic Maus
    Improved Distributed Delta-Coloring
    ACM Symposium on Principles of Distributed Computing (PODC) 2018.

  • Mohsen Ghaffari, Fabian Kuhn, Yannic Maus, and Jara Uitto
    Deterministic Distributed Edge-Coloring with Fewer Colors
    ACM Symposium on Theory of Computing (STOC) 2018.
    [arXiv]

  • Mohsen Ghaffari, and Jason Li
    Improved Distributed Algorithms for Exact Shortest Paths
    ACM Symposium on Theory of Computing (STOC) 2018.
    [arXiv]

  • Manuela Fischer, Mohsen Ghaffari, and Fabian Kuhn
    Deterministic Distributed Edge Coloring via Hypergraph Maximal Matching
    IEEE Symposium on Foundations of Computer Science (FOCS) 2017.
    Invited to the SIAM Journal of Computing (SICOMP) Special Issue for FOCS'17.
    [Abstract] [arXiv]

  • Manuela Fischer and Mohsen Ghaffari
    Sublogarithmic Distributed Algorithms for Lovász Local Lemma, and the Complexity Hierarchy
    International Symposium on DIStributed Computing (DISC) 2017.
    [Abstract] [arXiv]

  • Mohsen Ghaffari and Christiana Lymouri
    Simple and Near-Optimal Distributed Coloring for Sparse Graphs
    International Symposium on DIStributed Computing (DISC) 2017.
    [arXiv]

  • Mohsen Ghaffari and Merav Parter
    Near-Optimal Distributed DFS in Planar Graphs
    International Symposium on DIStributed Computing (DISC) 2017.

  • Mohsen Ghaffari, Juho Hirvonen, Fabian Kuhn, Yannic Maus, Jukka Suomela, and Jara Uitto
    Improved Distributed Degree Splitting and Edge Coloring
    International Symposium on DIStributed Computing (DISC) 2017.
    Best Paper Award at DISC'17.
    [Abstract] [arXiv]

  • Mohsen Ghaffari,
    Distributed MIS via All-to-All Communication
    ACM Symposium on Principles of Distributed Computing (PODC) 2017.

  • Mohsen Ghaffari, Fabian Kuhn, and Hsin-Hao Su,
    Distributed MST and Routing in Almost Mixing Time
    ACM Symposium on Principles of Distributed Computing (PODC) 2017.

  • Reuven Bar-Yehuda, Keren Censor Hillel, Mohsen Ghaffari, and Gregory Schwartzman
    Distributed Approximation of Maximum Independent Set and Maximum Matching
    ACM Symposium on Principles of Distributed Computing (PODC) 2017.

  • Mohsen Ghaffari, Fabian Kuhn, and Yannic Maus,
    On the Complexity of Local Distributed Graph Problems
    ACM Symposium on Theory of Computing (STOC) 2017.
    [Abstract] [arXiv] [A TCS+ talk on youtube] [Fabian's talk]

  • Mohsen Ghaffari and Hsin-Hao Su,
    Distributed Degree Splitting, Edge Coloring, and Orientations
    ACM-SIAM Symposium on Discrete Algorithms (SODA) 2017.

  • Mohsen Ghaffari, David Karger, and Debmalya Panigrahi,
    Random Contractions and Sampling for Hypergraph and Hedge Connectivity.
    ACM-SIAM Symposium on Discrete Algorithms (SODA) 2017.

  • Mohsen Ghaffari,
    Improved Distributed Algorithms for Fundamental Graph Problems
    PhD thesis at the EECS department of MIT, October 2016.
    ACM Doctoral Dissertation Award, Honorable Mention, 2017.
    ACM-EATCS Principles of Distributed Computing Doctoral Dissertation Award, 2017.
    George M. Srowls Award of Best Computer Science PhD Thesis at MIT, 2017.
    [PDF]

  • Mohsen Ghaffari and Calvin Newport,
    How to Discreetly Spread a Rumor in a Crowd
    International Symposium on DIStributed Computing (DISC) 2016.

  • Mohsen Ghaffari and Merav Parter,
    MST in Log-Star Rounds of Congested Clique
    ACM Symposium on Principles of Distributed Computing (PODC) 2016.
    Invited Talk at Highlights of Algorithms (HALG) 2017.

  • Mohsen Ghaffari and Bernhard Haeupler,
    Distributed Algorithms for Planar Networks I: Planar Embedding
    ACM Symposium on Principles of Distributed Computing (PODC) 2016.

  • Mohsen Ghaffari and Merav Parter,
    A Polylogarithmic Gossip Algorithm for Plurality Consensus
    ACM Symposium on Principles of Distributed Computing (PODC) 2016.

  • Mohsen Ghaffari and Merav Parter,
    Near-Optimal Distributed Algorithms for Fault-Tolerant Tree Structures
    ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) 2016.

  • Mohsen Ghaffari and Calvin Newport,
    Leader Election in Unreliable Radio Networks
    International Colloquium on Automata, Languages, and Programming (ICALP) 2016.

  • Mohsen Ghaffari,
    An Improved Distributed Algorithm for Maximal Independent Set
    ACM-SIAM Symposium on Discrete Algorithms (SODA) 2016.
    Best Paper Award and Best Student Paper Award at SODA'16.
    Invited Talk at Highlights of Algorithms (HALG) 2017.
    Invited Talk at Symposium on Theory of Computing (STOC) 2017.

  • Mohsen Ghaffari and Bernhard Haeupler,
    Distributed Algorithms for Planar Networks II: Low-Congestion Shortcuts, MST, and Min-Cut
    ACM-SIAM Symposium on Discrete Algorithms (SODA) 2016.

  • Mohsen Ghaffari,
    Near-Optimal Scheduling of Distributed Algorithms
    ACM Symposium on Principles of Distributed Computing (PODC) 2015.
    Best Student Paper Award at PODC'15.
    Invited to the Journal of ACM (JACM) Special Issue for PODC'15.

  • Mohsen Ghaffari, Andreas Karrenbauer, Fabian Kuhn, Christoph Lenzen, and Boaz Patt-Shamir,
    Near-Optimal Distributed Maximum Flow
    ACM Symposium on Principles of Distributed Computing (PODC) 2015.

  • Mohsen Ghaffari, Cameron Musco, Tsvetomira Radeva, and Nancy Lynch,
    Distributed House-Hunting in Ant Colonies
    ACM Symposium on Principles of Distributed Computing (PODC) 2015.

  • Mohsen Ghaffari,
    Distributed Broadcast Revisited: Towards Universal Optimality
    International Colloquium on Automata, Languages, and Programming (ICALP) 2015.

  • Keren Censor Hillel, Mohsen Ghaffari, George Giakkoupis, Bernhard Haeupler, and Fabian Kuhn,
    Tight Bounds on Vertex Connectivity under Vertex Sampling
    ACM-SIAM Symposium on Discrete Algorithms (SODA) 2015.
    Invited to the Transactions of Algorithms Special Issue for SODA 2015
    [Abstract]

  • Mohsen Ghaffari and Christoph Lenzen,
    Near-Optimal Distributed Tree Embedding
    International Symposium on DIStributed Computing (DISC) 2014.
    [Abstract] [PDF]

  • Rati Gelashvili, Mohsen Ghaffari, Jerry Li and Nir Shavit,
    On the Importance of Registers for Computability
    International Conference on Principles of Distributed Systems (OPODIS) 2014.
    [Abstract]

  • Mohsen Ghaffari and Bernhard Haeupler,
    Optimal Error Rates for Interactive Coding II: Efficiency and List Decoding
    IEEE Symposium on Foundations of Computer Science (FOCS) 2014.
    [Abstract] [PDF] [arXiv] [Press Coverage: MIT News]

  • Mohsen Ghaffari, Erez Kantor, Nancy Lynch, and Calvin Newport,
    Multi-Message Broadcast with Abstract MAC Layers and Unreliable Links
    ACM Symposium on Principles of Distributed Computing (PODC) 2014.
    [Abstract]

  • Keren Censor Hillel, Mohsen Ghaffari, and Fabian Kuhn,
    Distributed Connectivity Decomposition
    ACM Symposium on Principles of Distributed Computing (PODC) 2014.
    Best Student Paper Award at PODC'14.
    Invited to the Journal of ACM (JACM) Special Issue for PODC'14.

    [Abstract] [PDF] [arXiv]

  • Mohsen Ghaffari,
    Near-Optimal Distributed Approximation of Minimum-Weight Connected Dominating Set
    International Colloquium on Automata, Languages, and Programming (ICALP) 2014.
    Best Student Paper Award at ICALP'14, track C.
    [Abstract] [PDF] [arXiv]

  • Mohsen Ghaffari and Bernhard Haeupler, and Madhu Sudan,
    Optimal Error Rates for Interactive Coding I: Adaptivity and Other Settings
    ACM Symposium on Theory of Computing (STOC) 2014.
    [Abstract] [PDF] [arXiv]

  • Keren Censor Hillel, Mohsen Ghaffari, and Fabian Kuhn,
    A New Perspective on Vertex Connectivity
    ACM-SIAM Symposium on Discrete Algorithms (SODA) 2014.
    [Abstract] [PDF] [arXiv] [Press Coverage: MIT News]

  • Noga Alon, Mohsen Ghaffari, Bernhard Haeupler, and Majid Khabbazian,
    Broadcast Throughput in Radio Networks: Routing vs. Network Coding
    ACM-SIAM Symposium on Discrete Algorithms (SODA) 2014.
    [Abstract] [PDF]

  • Mohsen Ghaffari and Fabian Kuhn,
    Distributed Minimum Cut Approximation
    International Symposium on DIStributed Computing (DISC) 2013.
    Best Paper Award at DISC'13.
    [Abstract] [PDF] [arXiv]

  • Mohsen Ghaffari and Bernhard Haeupler,
    Fast Structuring of Radio Networks for Multi-Message Communications
    International Symposium on DIStributed Computing (DISC) 2013.
    [Abstract] [PDF] [arXiv]

  • Mohsen Ghaffari, Bernhard Haeupler, and Majid Khabbazian,
    Randomized Broadcast in Radio Networks with Collision Detection
    ACM Symposium on Principles of Distributed Computing (PODC) 2013.
    [Abstract] [PDF] [arXiv]

  • Mohsen Ghaffari, Nancy Lynch, and Calvin Newport,
    The Cost of Radio Network Broadcast for Different Models of Unreliable Links
    ACM Symposium on Principles of Distributed Computing (PODC) 2013.
    [Abstract] [PDF] [Press Coverage: MIT News]

  • Sebastian Daum, Mohsen Ghaffari, Seth Gilbert, Fabian Kuhn, and Calvin Newport,
    Maximal Independent Sets in Multichannel Radio Networks
    ACM Symposium on Principles of Distributed Computing (PODC) 2013.
    [Abstract] [PDF]

  • Mohsen Ghaffari and Bernhard Haeupler,
    Near-Optimal Leader Election in Multi-Hop Radio Networks
    ACM-SIAM Symposium on Discrete Algorithms (SODA) 2013.
    [Abstract] [PDF] [arXiv]

  • Mohsen Ghaffari, Seth Gilbert, Calvin Newport, and Henry Tan,
    Optimal Broadcast in Shared Spectrum Radio Networks
    International Conference Principles of Distributed Systems (OPODIS) 2012.

  • Mohsen Ghaffari, Bernhard Haeupler, Nancy Lynch, and Calvin Newport,
    Bounds on Contention Management in Radio Networks
    International Symposium on DIStributed Computing (DISC) 2012.
    [Abstract] [PDF]

  • Mohsen Ghaffari, Nancy Lynch, and Srikanth Sastry,
    Leader Election Using Loneliness Detection
    International Symposium on DIStributed Computing (DISC) 2011 + Distributed Computing Journal 2012.
    [Abstract] [PDF]

Undergrad. Research

  • Mohsen Ghaffari, Behnoosh Hariri, and Shervin Shirmohammadi,
    On the Necessity of Using Delaunay Triangulation Substrate in Greedy Routing Based Networks
    IEEE Communication Letters 2010.
    [Abstract] [PDF]

  • Mohsen Ghaffari, Behnoosh Hariri, and Shervin Shirmohammadi,
    A Delaunay Triangulation Architecture Supporting Churn and User Mobility in MMVEs
    ACM workshop on Network and Operating System Support for Digital Audio and Video (NOSSDAV) 2009.
    [Abstract] [PDF]

  • Mohsen Ghaffari and Farid Ashtiani,
    A New Routing Algorithm for Sparse Vehicular Ad-Hoc Networks with Moving Destinations
    IEEE Wireless Communications and Networking Conference (WCNC) 2009.
    [Abstract]