The Algorithms and Combinatorics group at CMM focuses on the study of structural properties of graphs, the design and analysis of centralized and distributed algorithms, and the behavior of processes over networks. Its research integrates methods from graph theory, probability, and theoretical computer science to address fundamental questions with both theoretical and applied relevance.
Algorithms and Combinatorics
A central component of the group’s work lies in extremal and probabilistic combinatorics. Topics of interest include Ramsey-type, Dirac-type and Turan-type problems in random and deterministic graphs, hypergraphs and digraphs. The group also works in structural and algorithmic graph theory. Topics of interest include Ramsey-type problems, tree containment, and graph regularity, as well as more interdisciplinary directions such as geometric properties arising from metric spaces induced by finite graphs and connections between graph theory and group theory.
The group also develops research on random discrete structures and processes, as well as randomized algorithms, with applications to combinatorics and computer science. This includes the study of complex network models, information dissemination processes, random graphs, and sublinear-time algorithms.
In distributed computing, the group studies systems composed of multiple processors that cooperate to achieve global tasks under intrinsic constraints, such as limited knowledge of the network and restricted computational and communication resources. Research in this area focuses both on the design of efficient distributed algorithms and on establishing fundamental limits through lower bounds and impossibility results.
Finally, the group also conducts research in combinatorial optimization, with emphasis on exact, approximation, and polyhedral approaches to optimization problems on graphs and matroids. It also studies online and stochastic algorithms for incremental optimization under uncertainty, including online matching, secretary problems, and stochastic matching.