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.

   

   

 

 

Research Group

See also our Reading Group

Mohsen

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

Administrative Assistant: Andrea Salow

 


Program Committees

Teaching

Publications

  • Manuela Fischer, Mohsen Ghaffari, and Fabian Kuhn
    Deterministic Distributed Edge Coloring via Hypergraph Maximal Matching
    IEEE Symposium on Foundations of Computer Science (FOCS) 2017.
    [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.

  • 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.
    Principles of Distributed Computing Doctoral Dissertation Award, 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 (co-winner) 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.

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

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

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