Algorithms and Combinatorics


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

Coordinators: Iván Rapaport and Maya Stein

About the research group

The Algorithms and Combinatorics group at CMM focuses on understanding structural aspects of graphs, centralized and distributed algorithms, and the behavior of certain processes in networks. Our main lines are outlined below.

Graph theory

We are interested in structural, extremal and algorithmic graph theory. Our topics include Ramsey type-questions and tree containment problems, as well as graph regularity. Other more interdisciplinary topics are classical geometric properties in the context of metric spaces induced by finite graphs, and topics on the border between graph theory and group theory.

Random Structures and Algorithms

We are interested in discrete random structures and processes as well as present applications of such research to problems in combinatorics and computer science. Specifically, our research concerns topics such as models of complex networks, information dissemination in networks, random graphs, property testing and sub-linear time algorithms.

Distributed Computing

Distributed computing concerns a collection of processors that collaborate in order to achieve some global task. Any distributed algorithm must deal with, at least, the following two constraints: (1) the lack of knowledge about far away processors; (2) the limitation on available resources such as time, local memory and communication (bandwidth). Together with devising efficient distributed algorithms, we are interested in obtaining lower bounds and impossibility results.

Discrete dynamical systems

The group at Concepción works on Boolean networks, cellular automata and Turing machine dynamics.