Mohsen Ghaffari

Orcid: 0000-0003-4213-9898

Affiliations:
  • MIT, Cambridge, MA, USA
  • ETH Zurich, Switzerland (former)
  • MIT, Cambridge, MA, USA (PhD)
  • Sharif University of Technology, Iran (former)


According to our database1, Mohsen Ghaffari authored at least 133 papers between 2009 and 2024.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
Near-optimal distributed dominating set in bounded arboricity graphs.
Distributed Comput., December, 2024

Decentralized Low-Stretch Trees via Low Diameter Graph Decompositions.
SIAM J. Comput., 2024

Shared Randomness Helps with Local Distributed Problems.
CoRR, 2024

Lenzen's Distributed Routing Generalized: A Full Characterization of Constant-Time Routability.
Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Work-Efficient Parallel Derandomization II: Optimal Concentrations via Bootstrapping.
Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Dynamic O(Arboricity) Coloring in Polylogarithmic Worst-Case Time.
Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Fast Broadcast in Highly Connected Networks.
Proceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures, 2024

Parallel Dynamic Maximal Matching.
Proceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures, 2024

A Distributed Palette Sparsification Theorem.
Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

A Near-Optimal Low-Energy Deterministic Distributed SSSP with Ramifications on Congestion and APSP.
Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing, 2024

Near-Optimal Deterministic Network Decomposition and Ruling Set, and Improved MIS.
Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

2023
Node and edge averaged complexities of local graph problems.
Distributed Comput., December, 2023

Faster Deterministic Distributed MIS and Approximate Matching.
Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Coloring Fast with Broadcasts.
Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures, 2023

Nearly Work-Efficient Parallel DFS in Undirected Graphs.
Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures, 2023

Local Distributed Rounding: Generalized to MIS, Matching, Set Cover, and Beyond.
Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

A Nearly Time-Optimal Distributed Approximation of Minimum Cost <i>k</i>-Edge-Connected Spanning Subgraph.
Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Improved Distributed Network Decomposition, Hitting Sets, and Spanners, via Derandomization.
Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

A Near-Optimal Deterministic Distributed Synchronizer.
Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing, 2023

Distributed MIS with Low Energy and Time Complexities.
Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing, 2023

Work-Efficient Parallel Derandomization I: Chernoff-like Concentrations via Pairwise Independence.
Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

2022
A Cut-Matching Game for Constant-Hop Expanders.
CoRR, 2022

A Nearly Time-Optimal Distributed Approximation of Minimum Cost k-Edge-Connected Spanning Subgraph.
CoRR, 2022

Hop-constrained expander decompositions, oblivious routing, and distributed universal optimality.
Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Deterministic Distributed Sparse and Ultra-Sparse Spanners and Connectivity Certificates.
Proceedings of the SPAA '22: 34th ACM Symposium on Parallelism in Algorithms and Architectures, Philadelphia, PA, USA, July 11, 2022

Average Awake Complexity of MIS and Matching.
Proceedings of the SPAA '22: 34th ACM Symposium on Parallelism in Algorithms and Architectures, Philadelphia, PA, USA, July 11, 2022

Massively Parallel Algorithms for b-Matching.
Proceedings of the SPAA '22: 34th ACM Symposium on Parallelism in Algorithms and Architectures, Philadelphia, PA, USA, July 11, 2022

Universally-Optimal Distributed Exact Min-Cut.
Proceedings of the PODC '22: ACM Symposium on Principles of Distributed Computing, Salerno, Italy, July 25, 2022

Local Computation of Maximal Independent Set.
Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

2021
Improved distributed Δ-coloring.
Distributed Comput., 2021

Hop-constrained oblivious routing.
Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Massively Parallel Algorithms for Distance Approximation and Spanners.
Proceedings of the SPAA '21: 33rd ACM Symposium on Parallelism in Algorithms and Architectures, 2021

A Time-Optimal Randomized Parallel Algorithm for MIS.
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Improved Deterministic Network Decomposition.
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Low-Congestion Shortcuts for Graphs Excluding Dense Minors.
Proceedings of the PODC '21: ACM Symposium on Principles of Distributed Computing, 2021

Strong-Diameter Network Decomposition.
Proceedings of the PODC '21: ACM Symposium on Principles of Distributed Computing, 2021

Network Decomposition and Distributed Derandomization.
Proceedings of the ICDCN '21: International Conference on Distributed Computing and Networking, 2021

Deterministic Distributed Vertex Coloring: Simpler, Faster, and without Network Decomposition.
Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

2020
Improved distributed degree splitting and edge coloring.
Distributed Comput., 2020

Improved MPC Algorithms for MIS, Matching, and Coloring on Trees and Beyond.
Proceedings of the 34th International Symposium on Distributed Computing, 2020

Polylogarithmic-time deterministic network decomposition and distributed derandomization.
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

A Massively Parallel Algorithm for Minimum Weight Vertex Cover.
Proceedings of the SPAA '20: 32nd ACM Symposium on Parallelism in Algorithms and Architectures, 2020

Faster Algorithms for Edge Connectivity via Random 2-Out Contractions.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Network Decomposition and Distributed Derandomization (Invited Paper).
Proceedings of the Structural Information and Communication Complexity, 2020

Massively Parallel Algorithms for Minimum Cut.
Proceedings of the PODC '20: ACM Symposium on Principles of Distributed Computing, 2020

2019
Improved Network Decompositions Using Small Messages with Applications on MIS, Neighborhood Covers, and Beyond.
Proceedings of the 33rd International Symposium on Distributed Computing, 2019

Distributed Algorithms for Low Stretch Spanning Trees.
Proceedings of the 33rd International Symposium on Distributed Computing, 2019

Distributed Computation in Node-Capacitated Networks.
Proceedings of the 31st ACM on Symposium on Parallelism in Algorithms and Architectures, 2019

Simplified and Space-Optimal Semi-Streaming (2+epsilon)-Approximate Matching.
Proceedings of the 2nd Symposium on Simplicity in Algorithms, 2019

Sparsifying Distributed Algorithms with Ramifications in Massively Parallel Computation and Centralized Local Computation.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Distributed Maximal Independent Set using Small Messages.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

On the Use of Randomness in Local Distributed Graph Algorithms.
Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, 2019

Improved Distributed Approximations for Minimum-Weight Two-Edge-Connected Spanning Subgraph.
Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, 2019

The Complexity of (Δ+1) Coloring in Congested Clique, Massively Parallel Computation, and Centralized Local Computation.
Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, 2019

On the Complexity of Distributed Splitting Problems.
Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, 2019

Improved Parallel Algorithms for Density-Based Network Clustering.
Proceedings of the 36th International Conference on Machine Learning, 2019

Distributed Arboricity-Dependent Graph Coloring via All-to-All Communication.
Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Conditional Hardness Results for Massively Parallel Computation from Distributed Lower Bounds.
Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

2018
Near-Optimal Distributed Maximum Flow.
SIAM J. Comput., 2018

Simple Graph Coloring Algorithms for Congested Clique and Massively Parallel Computation.
CoRR, 2018

Distributed Computation in the Node-Congested Clique.
CoRR, 2018

Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover.
CoRR, 2018

New Distributed Algorithms in Almost Mixing Time via Transformations from Parallel Algorithms.
Proceedings of the 32nd International Symposium on Distributed Computing, 2018

Distributed MST and Broadcast with Fewer Messages, and Faster Gossiping.
Proceedings of the 32nd International Symposium on Distributed Computing, 2018

Derandomizing Distributed Algorithms with Small Messages: Spanners and Dominating Set.
Proceedings of the 32nd International Symposium on Distributed Computing, 2018

A Simple Parallel and Distributed Sampling Technique: Local Glauber Dynamics.
Proceedings of the 32nd International Symposium on Distributed Computing, 2018

Distributed Set Cover Approximation: Primal-Dual with Optimal Locality.
Proceedings of the 32nd International Symposium on Distributed Computing, 2018

Improved distributed algorithms for exact shortest paths.
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Deterministic distributed edge-coloring with fewer colors.
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Congested Clique Algorithms for the Minimum Cut Problem.
Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, 2018

Nearly-Tight Analysis for 2-Choice and 3-Majority Consensus Dynamics.
Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, 2018

Improved Distributed Delta-Coloring.
Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, 2018

Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover.
Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, 2018

Session details: Session 2B: Routing and Leader Election.
Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, 2018

A Tight Analysis of the Parallel Undecided-State Dynamics with Two Colors.
Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science, 2018

On Derandomizing Local Distributed Algorithms.
Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

2017
Improved Distributed Algorithms for Fundamental Graph Problems.
PhD thesis, 2017

Tight Bounds on Vertex Connectivity Under Sampling.
ACM Trans. Algorithms, 2017

Tight Analysis for the 3-Majority Consensus Dynamics.
CoRR, 2017

Space-Optimal Semi-Streaming for (2+ε)-Approximate Matching.
CoRR, 2017

Deterministic Distributed Matching: Simpler, Faster, Better.
CoRR, 2017

Near-Optimal Distributed DFS in Planar Graphs.
Proceedings of the 31st International Symposium on Distributed Computing, 2017

Simple and Near-Optimal Distributed Coloring for Sparse Graphs.
Proceedings of the 31st International Symposium on Distributed Computing, 2017

Sublogarithmic Distributed Algorithms for Lovász Local Lemma, and the Complexity Hierarchy.
Proceedings of the 31st International Symposium on Distributed Computing, 2017

On the complexity of local distributed graph problems.
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Distributed Degree Splitting, Edge Coloring, and Orientations.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Random Contractions and Sampling for Hypergraph and Hedge Connectivity.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Distributed MST and Routing in Almost Mixing Time.
Proceedings of the ACM Symposium on Principles of Distributed Computing, 2017

Distributed MIS via All-to-All Communication.
Proceedings of the ACM Symposium on Principles of Distributed Computing, 2017

Distributed Approximation of Maximum Independent Set and Maximum Matching.
Proceedings of the ACM Symposium on Principles of Distributed Computing, 2017

Deterministic Distributed Edge-Coloring via Hypergraph Maximal Matching.
Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

2016
Near-Optimal BFS-Tree Construction in Radio Networks.
IEEE Commun. Lett., 2016

How to Discreetly Spread a Rumor in a Crowd.
Proceedings of the Distributed Computing - 30th International Symposium, 2016

Near-Optimal Distributed Algorithms for Fault-Tolerant Tree Structures.
Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures, 2016

Distributed Algorithms for Planar Networks II: Low-Congestion Shortcuts, MST, and Min-Cut.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

An Improved Distributed Algorithm for Maximal Independent Set.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

A Polylogarithmic Gossip Algorithm for Plurality Consensus.
Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, 2016

MST in Log-Star Rounds of Congested Clique.
Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, 2016

Distributed Algorithms for Planar Networks I: Planar Embedding.
Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, 2016

Leader Election in Unreliable Radio Networks.
Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

2015
A Dynamic Networking Substrate for Distributed MMOGs.
IEEE Trans. Emerg. Top. Comput., 2015

Randomized broadcast in radio networks with collision detection.
Distributed Comput., 2015

Towards an Optimal Distributed Algorithm for Maximal Independent Set.
CoRR, 2015

Tight Bounds on Vertex Connectivity Under Vertex Sampling.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Brief Announcement: Distributed Single-Source Reachability.
Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, 2015

Distributed House-Hunting in Ant Colonies.
Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, 2015

Near-Optimal Distributed Maximum Flow: Extended Abstract.
Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, 2015

Near-Optimal Scheduling of Distributed Algorithms.
Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, 2015

Distributed Broadcast Revisited: Towards Universal Optimality.
Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

2014
Fast Structuring of Radio Networks for Multi-Message Communications.
CoRR, 2014

Near-Optimal Distributed Tree Embedding.
Proceedings of the Distributed Computing - 28th International Symposium, 2014

Optimal error rates for interactive coding I: adaptivity and other settings.
Proceedings of the Symposium on Theory of Computing, 2014

A New Perspective on Vertex Connectivity.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Broadcast Throughput in Radio Networks: Routing vs. Network Coding.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Multi-message broadcast with abstract MAC layers and unreliable links.
Proceedings of the ACM Symposium on Principles of Distributed Computing, 2014

Distributed connectivity decomposition.
Proceedings of the ACM Symposium on Principles of Distributed Computing, 2014

On the Importance of Registers for Computability.
Proceedings of the Principles of Distributed Systems - 18th International Conference, 2014

Near-Optimal Distributed Approximation of Minimum-Weight Connected Dominating Set.
Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Optimal Error Rates for Interactive Coding II: Efficiency and List Decoding.
Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

2013
A Bound on the Throughput of Radio Networks
CoRR, 2013

Distributed Minimum Cut Approximation.
Proceedings of the Distributed Computing - 27th International Symposium, 2013

Fast Structuring of Radio Networks Large for Multi-message Communications.
Proceedings of the Distributed Computing - 27th International Symposium, 2013

Near Optimal Leader Election in Multi-Hop Radio Networks.
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

The cost of radio network broadcast for different models of unreliable links.
Proceedings of the ACM Symposium on Principles of Distributed Computing, 2013

Maximal independent sets in multichannel radio networks.
Proceedings of the ACM Symposium on Principles of Distributed Computing, 2013

2012
Leader election using loneliness detection.
Distributed Comput., 2012

The Complexity of Multi-Message Broadcast in Radio Networks with Known Topology
CoRR, 2012

Bounds on Contention Management in Radio Networks.
Proceedings of the Distributed Computing - 26th International Symposium, 2012

Optimal Broadcast in Shared Spectrum Radio Networks.
Proceedings of the Principles of Distributed Systems, 16th International Conference, 2012

2010
On the necessity of using Delaunay Triangulation substrate in greedy routing based networks.
IEEE Commun. Lett., 2010

2009
On the Necessary and Sufficient Condition of Greedy Routing Supporting Geographical Data Networks
CoRR, 2009

A new routing algorithm for sparse vehicular ad-hoc networks with moving destinations.
Proceedings of the 2009 IEEE Wireless Communications and Networking Conference, 2009

A delaunay triangulation architecture supporting churn and user mobility in MMVEs.
Proceedings of the Network and Operating System Support for Digital Audio and Video, 2009


  Loading...