Mohsen Ghaffari


I am an Assistant Professor in the Computer Science department of ETH Zurich. Before coming to Zurich, I completed my PhD at the EECS department of MIT in 2016.

I am interested in theoretical computer science, broadly interpreted. My research is typically centered around the theory of distributed computing and especially distributed graph algorithms and network algorithms.


 


 

 

Contact information:

Prof. Mohsen Ghaffari
Computer Science Department, ETH Zurich
CAB G32.1,
Universitatstrasse 6,
8092 Zurich, Switzerland.

Office: CAB G32.1
Phone: +41-44-6327247
Email: my-last-name at mit.edu; my-last-name at inf.ethz.ch

 

Mohsen

Teaching

 

Publications

  • Mohsen Ghaffari, Fabian Kuhn, and Yannic Maus,
    On the Complexity of Local Distributed Graph Problems
    Manuscript 2016.
    [Abstract] [arXiv] [A video of Fabian's talk about this work]

  • 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 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.

  • 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 (co-winner) and Best Student Paper Award at SODA'16.

  • 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.

  • 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.
    [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.
    [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.
    [Abstract] [PDF]

  • 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]


  • 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]