Ming Ming Tan
Augusta University, GA·Computer Science
Many computing systems are networks of machines that work together by passing messages to one another. The program each machine runs is called a distributed algorithm.
- Fields
Computer Science
Mathematics & Statistics
- Topics
distributed algorithms
distributed computing
message complexity
- Grants
- 1 known grant, through Mar 2027
What they work on
- Design message-efficient distributed algorithms for building and verifying approximate breadth-first search trees and single-source shortest path trees, assuming nodes start with partial knowledge of nearby network topology.
- Explore how partial network knowledge affects the trade-off between running time and message count for vertex coloring, maximal independent set and maximal matching.
- Introduce an oracle framework that gives each node an "advice" bit string based on its neighborhood, and find the minimum advice length needed for optimal algorithm performance on fundamental graph problems.
More about the research
How fast these algorithms run, and how many messages they need, often depends on what each machine knows about the network at the start. That might be a rough estimate of the network's size, or the addresses of its direct neighbors. This theoretical project asks how much that starting knowledge can cut the communication an algorithm needs. It also maps the trade-offs among running time, number of messages and initial knowledge.
Why it matters
The work is mainly theoretical. It clarifies how starting knowledge of a network limits or enables fast, low-communication coordination among machines. The algorithmic approaches are meant as a foundation for future practical distributed algorithms. Such algorithms could eventually help networked computing systems coordinate using fewer messages.
Known grants
From NIH and NSF research grants. Labs often have other funding we can't see.
Closest labs
Shachar Lovett
University of California-San Diego, CA·Computer Science
Develop the theory of spreadness, a measure that no structured subset contains too many elements, into a general framework connecting existing structure-versus-randomness arguments.
Shaddin Dughmi
University of Southern California, CA·Computer Science
Identify algorithmic recipes for optimal supervised learning by treating classification as bipartite matching on the one-inclusion graph, a structure linking possible labelings of data.
Sayan Bandyapadhyay
Portland State University, OR·Computer Science
Design polynomial-time approximation algorithms for balanced k-median and k-means clustering, where each cluster must fairly represent every protected group, aiming for constant-factor guarantees like those known for ordinary clustering.
The school
Augusta University: 11 labs on PI Pages, $166M a year on research, 37 research doctorates a year.
Reach out
A start for your email. Fill in the brackets.