Sign In

Communications of the ACM

Latin America Regional Special Section: Big Trends

A Perspective on Theoretical Computer Science in Latin America


View as: Print Mobile App ACM Digital Library Full Text (PDF) In the Digital Edition Share: Send by email Share on reddit Share on StumbleUpon Share on Hacker News Share on Tweeter Share on Facebook
map of North and South America, illustration

Credit: Andrij Borys Associates, Shutterstock

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.

Back to Top

Automata Theory and Networks

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.

Back to Top

Graph Theory

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).

Back to Top

Pattern Matching and Information Retrieval

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.

Back to Top

Algorithms

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.

Back to Top

Distributed 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.

Back to Top

Combinatorics and Random Structures

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.

Back to Top

Computational Geometry

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.

Back to Top

Computational Algebra and Algebraic Geometry

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.

Back to Top

Cryptology

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.

Back to Top

Conclusion

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.

Back to Top

Acknowledgments

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.

* Further Reading

Back to Top

References

Automata and Network Theory

1. Pin, J. The influence of Imre Simon's work in the theory of automata, languages and semigroups. Semigr. Forum 98 (2019), 1–8.

Graph Theory

2. Alcon, L. et al. The complexity of clique graph recognition. Theoret. Comput. Sc. 410 (2009), 2072–2083.

3. Bonomo, F. et al. Three-coloring and three-list-coloring of graphs without induced paths of seven vertices. Combinatorica 38 (2018), 779–801.

4. Grötschel, M., Thomassen, C., and Wakabayashi, Y. Hypotraceable digraphs. J. Graph Theor. 4, 4 (1980), 377–381.

5. Itai, A., Papadimitriou, C., and Szwarcfiter, J. Hamilton paths in grid graphs. SIAM J. Comput. 11 (1982), 676–686.

6. Lucchesi, C.L. and Younger, D. A minimax theorem for directed graphs. J. Lond. Math. Soc. 2, 17 (1978), 369–374.

Pattern Matching and Information Retrieval

7. Baeza-Yates, R., and Ribeiro-Neto, B. Modern Information Retrieval: The Concepts and Technology Behind Search. ACM Press (2nd ed), 2011.

8. Navarro, G. Compact Data Structures—A Practical Approach. Cambridge University Press, 2016.

9. Navarro, G., and Raffinot, M. Flexible Pattern Matching in Strings-Practical On-line Search Algorithms for Texts and Biological Sequences. Cambridge University Press, 2002.

10. Ziviani, N., de Moura, E., Navarro, G., and Baeza-Yates, R. Compression: A key for next-generation text retrieval systems. IEEE Computer 33, 11 (2000), 37–44.

Algorithms

11. Adamszek, A., Har-Peled, S., and Wiese, A. Approximation schemes for independent set and sparse subsets of polygons. J. ACM 66, 4 article 29 (2019).

12. Buchbinder, N. et al. k-Servers with a smile: Online algorithms via projections. In Proceedings of 2019 SODA (2019), 98–116.

13. Correa, J. et al. Posted price mechanisms for a random stream of customers. In Proceedings of 2017 EC (2017), 169–186.

14. Cicalese, F., Laber, E. S., and Murtinho, L. New results on information theoretic clustering. In Proceedings of 2019 ICML, 1242–1251.

15. Fernandes, C.G. et al. A systematic approach to bound factor-revealing LPs and its application to the metric and squared metric facility location problems. Math. Program. 153 (2015), 655–685.

16. Miyazawa, F.K. and Wakabayashi, Y. Approximation algorithms for the orthogonal z-oriented three-dimensional packing problem. SIAM J. Comput. 29, 3 (2000), 1008–1029.

17. Soto, J., Turkieltaub, A., and Verdugo, V. Strong algorithms for the ordinal matroid secretary problem. In Proceedings of 2018 SODA (2018), 715–734.

Distributed Algorithms

18. Alcantara, M. et al. The topology of look-compute-move robot wait-free algorithms with hard termination. Distrib. Comput. 32, 3 (2019), 235–255.

19. Becker, F. et al. The impact of locality in the broadcast congested clique model. SIAM J. Discret. Math. 34, 1 (2020), 682–700.

20. Castañeda, A. et al. A topological perspective on distributed network algorithms. In Proceedings of 2019 SIROCCO (2019), 3–18.

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.

22. Herlihy, M., Kozlov, D.N., and Rajsbaum, S. Distributed Computing Through Combinatorial Topology. Morgan Kaufmann, 2013.

Combinatorics and Random Structures

23. Allen, P. et al. The chromatic thresholds of graphs. Adv. Math. 235 (2013), 261–295.

24. Balogh, J., Morris, R., and Samotij, W. Independent sets in hypergraphs. J. Amer. Math. Soc. 28, 3 (2015), 669–709.

25. Hladký, J. et al. The approximate Loebl-Komlós-Sós conjecture, Parts I, II, II, and IV. SIAM J. Discrete Math. 31, 2 (2017), 945–1148.

26. Janson, J. and Viola, A. A unified approach to linear probing hashing with buckets. Algorithmica 75, 4 (2016), 724–781.

27. Kiwi, M. and Mitsche, D. Spectral gap of random hyperbolic graphs and related parameters. Ann. Appl. Probab. 28 (2018), 941–989.

Computational Geometry

28. Arocha, J.L. et al. Very colorful theorems. Discret. Comput. Geom. 42, 2 (2009), 142–154.

29. Afshani, P., Barbay, J., and Chan, T. M. Instance-optimal geometric algorithms. J. ACM 64, 1 article 3 (2017).

30. Bereg, S. et al. On balanced 4-holes in bichromatic point sets. Comput. Geom. 48, 3 (2015), 169–179.

31. Guibas, L. and Stolfi, J. Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams. ACM Trans. Graph. 4, 2 (1985), 74–123.

32. Urrutia, J. Art gallery and illumination problems. In Handbook on Computational Geometry, J.R. Sack and J. Urrutia, Eds., North Holland (Elsevier Science Publishers), (2000), 973–1026.

Computational Algebra and Algebraic Geometry

33. Bank, E. et al. Intrinsic complexity estimates in polynomial optimization. J. Complex. 30, 4 (2014), 430–443.

34. Cesaratto, E., von zur Gathen, J., and Matera, G. The number of reducible space curves over a finite field. J. Number Theory 133, 4 (2013), 1409–1434.

Cryptology

35. Barreto, P.S.L.M., and Naehrig, M. Pairing-friendly elliptic curves of prime order. In Proceedings of 2005 SAC (2005), 319–331.

36. Hernández, J. and Dahab, R. Fast multiplication on elliptic curves over GF(2m) without precomputation. In Proceedings of 1999 CHES, 316–327.

37. The Random UChile Project; https://random.uchile.cl/

38. Oliveira, L.B. et al. TinyPBC: Pairings for authenticated identity-based non-interactive key distribution in sensor networks. Comput. Commun. 34, 3 (2011), 485–493.

39. Wikipedia. Discrete logarithm records; https://en.wikipedia.org/wiki/Discrete_logarithm_records

Back to Top

Authors

Marcos Kiwi is a professor at the Universidad de Chile, Santiago, Chile.

Yoshiharu Kohayakawa is a professor at the Universidade de São Paulo, Brazil.

Sergio Rajsbaum is a professor at the Universidad Autónoma de México, Mexico City, Mexico.

Francisco Rodríguez-Henríquez is a professor at the CINVESTAV, Mexico City, Mexico.

Jayme Luiz Szwarcfiter is a professor at the Universidade Federal do Rio de Janeiro and Universidade do Estado do Rio de Janeir, Brazil.

Alfredo Viola is a professor at the Universidad de la República, Montevideo, Uruguay.

Back to Top

Back to Top

Back to Top


©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 permissions@acm.org or fax (212) 869-0481.

The Digital Library is published by the Association for Computing Machinery. Copyright © 2020 ACM, Inc.


 

No entries found