Algorithms and Combinatorics

Researchers

Julio Aracena, José Correa, Hiep Han, Marcos Kiwi, Martín Matamala, Matías Pavez-Signé, Iván Rapaport, José Soto, Maya Stein, José Verschae

Coordinators: Iván Rapaport and Maya Stein

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.

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 on structural and algorithmic graph theory, as well as on non-symmetric ordered geometry, such as that arising from shortest-path distances in weighted digraphs.

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.