Theoretical computer science is everywhere, for TCS is concerned with the foundations of computing and computing is everywhere! In the last three decades, a vibrant Latin American TCS community has emerged: here, we describe and celebrate some of its many noteworthy achievements.
Computer science became a distinct academic discipline in the 1950s and early 1960s. The first CS department in the U.S. was formed in 1962, and by the 1970s virtually every university in the U.S. had one. In contrast, by the late 1970s, just a handful of Latin American universities were actively conducting research in the area. Several CS departments were eventually established during the late 1980s. Often, theoreticians played a decisive role in the foundation of these departments.
One key catalyst in articulating collaborations among the few but growing number of enthusiastic theoreticians who were active in the international academic arena was the foundation of regional conferences. The first one was LATIN in 1992 followed by LAGOS and Latincrypt as well as other more specialized or local meetings (see the sidebars in this article for details). These conferences have fostered regional and international collaboration and helped consolidate TCS research groups in Argentina, Brazil, Chile, Mexico, and Uruguay, and their impact is felt in other Latin American countries.
In this article, we briefly discuss some of the most notorious research topics in TCS in Latin America. Our perspective is inspired by the research scope of LATIN, LAGOS, and Latincrypt; we have grouped them into nine topics.
One of the main instigators of interest and research in TCS in Brazil was Imre Simon, whose work in automata theory was very influential (for details see Pin1). Owing to Simon's research, a semiring and some of its variants were dubbed tropical semirings, and the name has endured as they became fashionable in algebraic geometry. São Paulo's theory group grew in several directions under Simon's leadership. In 1992, he launched the first Latin American theory conference (LATIN), thus fostering the emergence of a vibrant regional community. In Chile, a somewhat similar story took place. Eric Goles returned from Grenoble in the early 1980s and continued his Ph.D. thesis work on dynamics of cellular automata via discrete Lyapunov functions. He mentored several of the first Chilean TCS researchers, who, together with his more recent students, are active throughout several institutions in Chile, working in graph theory, distributed computing, Boolean networks, and so forth. Not surprisingly, the second edition of LATIN took place in Chile in 1995 and was co-chaired by Goles.
Another main source of TCS development in the region has been graph theory, which started about 50 years ago. The pioneering work by the late Victor Neumann-Lara and Jayme Szwarcfiter (UFRJ, Rio de Janeiro) has had great influence in Latin America.
The research interests and achievements of Latin American graph theorists are too broad to be highlighted briefly. Undoubtedly, the beautiful Lucchesi-Younger minimax theorem on directed cuts,6 by Cláudio L. Lucchesi (Unicamp, Campinas), is one of the best-known graph theory results by a Latin American. In addition to Unicamp, in São Paulo, research in graph theory has a long tradition at USP.4 Much of the graph theory in Argentina and Brazil can be traced back to UFRJ, where Szwarcfiter works. In Rio de Janeiro (at UERJ, UFF, UFRJ) the main areas are graph convexity, graph classes, and graph algorithms.2,5 Furthermore, there are important researchers at UFC (Fortaleza) and active groups at UFABC (São Paulo), UFMG (Belo Horizonte), UFMS (Campo Grande), and UFPE (Recife). In Argentina, significant contributions have been made on intersection graphs and graph complexity, both at UBA (Buenos Aires) and UNLP (La Plata). The collaboration of Flavia Bonomo (UBA) and Maya Stein (UCh, Santiago) has recently resulted in a noteworthy success in classical algorithmic graph theory, namely, in graph coloring.3 Graph theory is now a major area of research in Chile, with Martín Matamala (UCh) as one of its senior leaders. There are many strong active researchers in Mexico City working in graph theory, among others at UAM, UNAM, CINVESTAV and ITAM, and in several other cities, especially Gelasio Salazar at UASLP (San Luis Potosi).
Latin America has a strong tradition in research on string searching and information retrieval (IR), most of which can be traced back to the group led by Gaston Gonnet (from Uruguay) at Waterloo. Two of Gonnet's Ph.D. students, Nivio Ziviani (UFMG, Belo Horizonte) and Ricardo Baeza-Yates (UCh, Santiago) started a very fruitful and productive collaboration in the 1990s. They co-founded, in 1993, the International Symposium on String Processing and Information Retrieval and pioneered the use of a novel technique called bit-parallelism in string matching algorithms. Gonzalo Navarro (UCh, Santiago), a Ph.D. student of Baeza-Yates, extended and implemented the technique, publishing a well-received book,9 and developing the public software nrgrep. In the late 1990s, the groups at UFMG and Universidad de Chile developed a new area: direct search on compressed natural language text.10 Those developments were applied in novel Web search engines devised in Chile and Brazil, which were eventually instrumental in the interest of Yahoo! and Google to settle in Chile and Brazil, respectively. In the mid-1990s, Berthier Ribeiro-Neto joined UFMG, bringing his experience in core IR and ranking to the group. In 1999, with Baeza-Yates, he published the book Modern Information Retrieval.7 This is one of the most-cited publications in the history of IR, with close to 19K citations at the time of this writing, according to Google Scholar Citations. Since 2000, Navarro's research has focused on compressed data structures,8 which is described in the article by Arroyuelo et al. on p. 64.
One key catalyst in articulating collaborations among the few but growing number of enthusiastic theoreticians who were active in the international academic arena was the foundation of regional conferences.
A number of young researchers in the area now populate various regional universities, especially in Chile and Brazil but also in Colombia, Ecuador, and Mexico.
Algorithms research in Latin America is particularly successful in the areas of approximation algorithms, online algorithms, and algorithmic game theory. Excellent groups are found in Chile and Brazil. The community in Chile has been growing steadily and today the main groups are based in UCh, PUC-Chile, USACH, and UOH. Recent outstanding results are summarized next. Andreas Wiese (UCh, Santiago) obtained a (1 + ε)-approximation algorithm for finding a maximum weight independent set of polygons in quasi-polynomial time,11 José Correa (UCh) resolved an open problem from the 1980s related to the IID prophet inequality,13 while José Soto (UCh) and Victor Verdugo (UOH, Rancagua) proposed the best current algorithms for the secretary problem on some classes of matroids.17 In Brazil, the main groups are at PUC-Rio, Unicamp, and USP. At PUC-Rio, algorithms research mainly focuses on algorithms under uncertainty and learning. Marco Molinaro (PUC-Rio, Rio de Janeiro) has been exploring connections between online and stochastic problems and online learning.12 Eduardo Laber (PUC-Rio) has been working on decision tree problems and its connections with machine learning.14 The groups at Unicamp and USP collaborate regularly. For instance, Flávio Miyazawa (Unicamp, Campinas) and Yoshiko Wakabayashi (USP, São Paulo) have a long history of collaboration on approximation algorithms for geometric packing problems,16 while Cristina Fernandes (USP), Flávio Miyazawa, Luis Meira, and Lehilton Pedrosa (Unicamp) have developed a systematic technique to bound factor-revealing linear programs and used it to obtain approximation results for facility location problems.15 Also in São Paulo, Marcel de Carli Silva (USP) and Cristiane Sato (UFABC, Santo André) have worked on spectral sparsification algorithms.
In Mexico, there is an active research group in distributed algorithms since the early 1990s, started by Sergio Rajsbaum, which later incorporated Armando Castañeda, both at UNAM (Mexico City). They are internationally recognized as some of the main experts on the topological approach to distributed computing. This perspective was born in 1993 when Maurice Herlihy and Nir Shavit and others, uncovered a deep connection with algebraic topology, showing that communication among unreliable concurrent processes is actually deforming a geometric representation of the possible inputs to the system, and the topological properties in turn determine computability and complexity of the corresponding distributed algorithms. The long-term collaboration since the early 1990s especially with Herlihy resulted in the 2013 book22 and the organization in Mexico of the 10th Geometric and Topological Methods in Computer Science conference. Close international collaborations have been maintained, especially with the U.S., France, and Israel. Some research highlights of the topological approach demonstrate its interaction with formal methods, with network algorithms,20 with robot algorithms,18 and with epistemic logic.21 In Chile, distributed computing research is done by Iván Rapaport (UCh, Santiago), Pedro Montealegre (UAI, Santiago) and Karol Suchan (UDP, Santiago), who have worked on communication complexity,19 cellular automata, routing, and distributed property testing.
There is solid collaboration among researchers from Argentina and Uruguay in analytic combinatorics and dynamical analysis of algorithms. An illustration of the research done in this area is Alfredo Viola's complete distributional analysis of linear probing,26 generalizing Donald Knuth's work from 1962, considered to be the origin of analysis of algorithms.
Asymptotic and probabilistic combinatorics are important topics of study in Brazil and Chile. The research in this area in Chile is led by Marcos Kiwi and Maya Stein (UCh, Santiago) and Hiêp Hàn (USACH, Santiago). Among noteworthy contributions are the proof of an approximate version of a celebrated mid-1990s conjecture25 and the development of the theory of random models of complex networks.27 In Brazil, Yoshiharu Kohayakawa (USP, São Paulo) and Rob Morris (IMPA, Rio de Janeiro) and their collaborators work in this area. An example of a USP/IMPA collaboration on this front is a paper on the structure of dense graphs with high chromatic number,23 which was awarded the Fulkerson Prize in 2018. A striking regional research success is the discovery of "hypergraph containers" by Morris and co-authors.24 These objects were in fact independently and simultaneously born in two places: in Rio de Janeiro and at Cambridge, U.K., and the authors were jointly awarded the Pólya Prize in Applied Combinatorics in 2016 for their far-reaching discovery.
Computational geometry has been present in Latin America for at least 20 years, mainly in Mexico and more recently in Chile. In Mexico, the senior researcher in this area is Jorge Urrutia (UNAM, Mexico City) who works with David Flores-Peñaloza and Adriana Ramiréz-Vigueras (UNAM), Ruy Fabila-Monroy and Dolores Lara (CINVESTAV, Mexico City) and Marco Heredia (UAM, Mexico City). This group works in several areas such as those surveyed by Urrutia,32 with well-known results in routing in ad hoc wireless networks, geometric graphs on colored point sets,30 orthogonal convex hulls, and discrete geometry.28 The group maintains strong international collaborations, especially with research groups in Austria, Spain, Canada, and Japan, and in particular in Chile with Pablo Pérez-Lantero (USACH, Santiago). An independent research group that includes Jeremy Barbay (UCh, Santiago) has developed instance optimal algorithms for geometric problems such as computing the convex hull of a point set.29
We close by mentioning an interesting and early chapter of computational geometry involving a Latin American: Jorge Stolfi (Unicamp, Campinas) developed the celebrated quad-edge data structure31 as a graduate student at Stanford in the 1980s.
Buenos Aires has a strong research group in computational algebra, complexity, and algebraic geometry. Their focus is on the complexity of natural algebraic problems, such as solving systems of polynomial equations and related enumeration questions. Joos Heintz (UBA, Buenos Aires) has been a leader in these areas for decades, substantially contributing to the complexity of equation solving.33 He co-founded the international meetings MEGA and TERA, and has strong collaborations with Spain, France, and Germany. The algebraic geometer Guillermo Matera (UBA, UNGS, Buenos Aires) works on computational and enumeration problems.34 Eda Cesaratto's (UNGS) work focuses on computational number theory. In Colombia, there is a very active group of young researchers who have made important contributions in algebraic and geometric combinatorics, particularly in matroid theory, polytopes, and tropical geometry.
The main Latin American cryptographic research groups are concentrated in Brazil, Chile, Colombia, Mexico, and Uruguay.
The pioneering work on pairing-based cryptography of Paulo Barreto (USP, São Paulo) culminated with the discovery of the Barreto-Naehrig elliptic curves.35 Several elegant algorithmic improvements introduced by Diego Aranha, Ricardo Dahab and Julio López (Unicamp, Campinas) produced some of the fastest and most compact software implementations of elliptic curve cryptography.36,38 Ricardo Custódio (UFSC, Florianópolis) has contributed to digital signature systems. Jeroen van der Graaf (UFMG, Belo Horizonte) has worked in cryptographic protocols and electronic voting. Nicolas Thériault (USACH, Santiago) has worked on index calculus cryptanalysis attacks. Recently, Alejandro Hevia (UCh, Santiago) and collaborators developed the randomness beacon. John Baena and Daniel Cabarcas (UNAL, Bogotá) and Valérie Gauthier (UR, Bogotá) are junior researchers whose main interests lie in multivariate-based and code-based cryptography. In Mexico, Nareli Cruz-Cortés (IPN, Mexico City), Francisco Rodríguez-Henríquez (CINVESTAV, Mexico City), and their collaborators, currently hold the record for computing discrete logarithms on fields of characteristic three.39 Cuauhtemoc Mancillas (CINVESTAV) has designed authenticated encryption schemes. Alfredo Viola (UdelaR, Montevideo) has worked on the cryptanalysis of historical Uruguayan documents and in combinatorial constructions of Boolean cryptographic functions.
We have surveyed some of the Latin American achievements in TCS focusing on the scope of LATIN, LAGOS, and Latincrypt. We look forward to the future of Latin American research in TCS, and hope that sooner than later we will not only be able to celebrate that a Turing Award winner was born in the region (as Manuel Blum), but also that she or he was educated and produced major work in the Latin American academic environment.
The following people have kindly contributed with information and comments to this article: Federico Ardila, Marcelo Arenas, Ricardo Baeza-Yates, Flavia Bonomo-Braberman, José R. Correa, Cristina G. Fernandes, Celina M. H. de Figueiredo, Joachim von zur Gathen, Eric Goles, Claudio Gutierrez, Arnaldo Mandel, Marco Molinaro, Gonzalo Navarro, Daniel Panario, Gelasio Salazar, José A. Soto, Maya Stein, Jorge Urrutia, and Yoshiko Wakabayashi.
Automata and Network Theory
Pattern Matching and Information Retrieval
21. Goubault, E., Ledent, J., and Rajsbaum, S. To appear in Inf. Comput. 2020, A preliminary version of A simplicial complex model for dynamic epistemic logic to study distributed task computability. In Proceedings of 2018 GandALF (2018), 73–87.
Combinatorics and Random Structures
Computational Algebra and Algebraic Geometry
37. The Random UChile Project; https://random.uchile.cl/
39. Wikipedia. Discrete logarithm records; https://en.wikipedia.org/wiki/Discrete_logarithm_records
©2020 ACM 0001-0782/20/11
Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and full citation on the first page. Copyright for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or fee. Request permission to publish from firstname.lastname@example.org or fax (212) 869-0481.
The Digital Library is published by the Association for Computing Machinery. Copyright © 2020 ACM, Inc.
No entries found