Search
Join ACM
Research and Advances
Computing Applications Latin America Regional Special Section: Big Trends

A Perspective on Theoretical Computer Science in Latin America

By , , , , , and
Posted
map of North and South America, illustration
  1. Introduction
  2. Automata Theory and Networks
  3. Graph Theory
  4. Pattern Matching and Information Retrieval
  5. Algorithms
  6. Distributed Algorithms
  7. Combinatorics and Random Structures
  8. Computational Geometry
  9. Computational Algebra and Algebraic Geometry
  10. Cryptology
  11. Conclusion
  12. Acknowledgments
  13. References
  14. Authors
  15. Sidebar: Main Meetings
  16. Sidebar: Other Meetings
  17. Sidebar: Acronyms of Universities and Research Institutes
map of North and South America, illustration

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

Back to Top

Back to Top

Sidebar: Main Meetings

LATIN. The Latin American Theoretical INformatics Symposium started in 1992. It is currently in its 14th edition. Since 1998 it has been held each two years. More than 1,900 papers have been submitted to these meetings and 719 have been accepted. The authors of the published papers come from nearly 50 countries and about 1/6 of these papers have an author with a Latin American affiliation and 1/12 have all their authors affiliated to Latin American institutions. Many other articles are written by the Latin American diaspora working mostly in Europe and North America. In terms of worldwide reach measured by origin of accepted articles, the top 10 list is dominated by the U.S., France, and Germany, and is complemented by Canada, Brazil, Chile, Italy, U.K., Israel, and Switzerland. Among the strong research areas for which LATIN is a thoroughfare are algorithms, computational complexity, data structures, pattern matching, and random structures.

Although effectively a four-full-day meeting, LATIN plays out over five days. This, coupled with its single session format gives ample time for interaction among attendees. Another distinctive aspect of the conference is its relatively large lineup of invited speakers that includes ACM Fellows, ACM A.M. Turing Award and Nevanlinna Prize recipients. Although LATIN keeps its Latin American nature, it is a meeting that reaches the world.

Latincrypt. The International Conference on Cryptology and Information Security in Latin America and the Advanced School on Cryptology and Information Security in Latin America (ASCrypto) have been held several times since 2010. Latincrypt enjoys the “In cooperation with” status granted by the International Association for Cryptologic Research (IACR). Both events are the leading cryptographic periodic meetings in Latin America. One distinctive aspect of Latincrypt is its outstanding list of invited speakers, which includes several IACR Fellows and ACM A.M. Turing Award recipients. Furthermore, during all of its editions, ASCrypto has served more than 1,000 students from all over the world, most of them from Latin America.

Over 320 papers have been submitted to Latincrypt and 113 have been accepted for publication. Among the latter papers, 1/5 have at least one author while 1/8 have all authors affiliated to a Latin American institution. The authors of the published papers come from nearly 30 countries and many of them, while not working in Latin America, are originally from the region.

LAGOS. The Latin American Algorithms, Graphs and Optimization Symposium has been held on 10 occasions, all but once in Latin America. The meeting per se arose in 2005 as the merger of two regional events that were taking place since 2001. Its proceedings were first published in Electronic Notes in Discrete Mathematics and later in Electronic Notes in Theoretical Computer Science.

The average number of submitted papers has been approximately 130. The average acceptance rate is approximately 45%. Each edition of LAGOS attracts authors from approximately 20 distinct countries. Outside Latin America, the largest number of submissions and participants are affiliated with French institutions.

Back to Top

Sidebar: Other Meetings

SPIRE. The International Symposium on String Processing and Information Retrieval, held annually since 1993 (initially under a different name), alternates its venues between Latin America and the rest of the world. While it focuses on string processing, it also features relevant articles on information retrieval and computational biology, particularly on algorithmic and efficiency aspects. SPIRE is a key meeting point between the Latin American and the international communities working around its topics of interest.

LAWCG. The Latin American Workshop on Cliques of Graphs is a biennial meeting originally focused on clique graphs (the intersection graphs of the maximal cliques of a graph) a research topic that mostly originated in Latin America. However, it soon broadened its spectrum and became a forum for research in graph theory. The workshop attracts about 150 participants from Argentina, Brazil, Chile and Mexico, and is being held alternately in these countries.

ACCOTA. The biennial International Workshop on Combinatorial and Computational Aspects of Optimization, Topology and Algebra is a meeting at the crossroads of TCS, combinatorics, graph theory, geometry, topology, and algebra. Started in 1996, it has always taken place in Mexico, exerting great influence on the mathematics community both within and beyond Mexican borders. ACCOTA has benefited from the often regular participation of researchers of the highest level, including some of the best living graph theorists and computer scientists.

Schools. Many high-level schools are held periodically in the region. One of the longest running and more prestigious is the Discrete Mathematics Summer School, launched in 2004 by researchers at Universidad de Chile. It takes place annually on a scenic hilltop overlooking the port of Valparaiso, Chile. It has become a lively and consolidated event that attracts students from all over the region and beyond. Since 2008, the biennial Encuentro Colombiano de Combinatoria brings together the world’s top researchers in algebraic and geometric combinatorics and undergraduate and graduate students from all over Latin America and the world.

Back to Top

Sidebar: Acronyms of Universities and Research Institutes

  • CINVESTAV: Centro de Investigación y de Estudios Avanzados del IPN, Mexico
  • IMPA: Instituto de Matemática Pura e Aplicada, Brazil
  • IPN: Instituto Politécnico Nacional, Mexico
  • ITAM: Instituto Tecnológico Autónomo de México, Mexico
  • PUC-Chile: Pontificia Universidad Católica de Chile, Chile
  • PUC-Rio: Pontifícia Universidade Católica do Rio de Janeiro, Brazil
  • UAI: Universidad Adolfo Ibáñez, Chile
  • UAM: Universidad Autónoma Metropolitana, Mexico
  • UASLP: Universidad Autónoma de San Luis Potosí, Mexico
  • UBA: Universidad de Buenos Aires, Argentina
  • UCh: Universidad de Chile, Chile
  • UdelaR: Universidad de la República, Uruguay
  • UDP: Universidad Diego Portales, Chile
  • UERJ: Universidade do Estado do Rio de Janeiro, Brazil
  • UFABC: Universidade Federal do ABC, Brazil
  • UFC: Universidade Federal do Ceará, Brazil
  • UFF: Universidade Federal Fluminense, Brazil
  • UFMG: Universidade Federal de Minas Gerais, Brazil
  • UFMS: Universidade Federal do Mato Grosso do Sul, Brazil
  • UFPE: Universidade Federal de Pernambuco, Brazil
  • UFRJ: Universidade Federal do Rio de Janeiro, Brazil
  • UFSC: Universidade Federal de Santa Catarina, Brazil
  • UNAL: Universidad Nacional de Colombia, Colombia
  • UNAM: Universidad Nacional Autónoma de México, Mexico
  • UNGS: Universidad Nacional de General Sarmiento, Argentina
  • Unicamp: Universidade Estadual de Campinas, Brazil
  • UNLP: Universidad Nacional de La Plata, Argentina
  • UOH: Universidad de O’Higgins, Chile
  • UR: Universidad del Rosario, Colombia
  • USACH: Universidad de Santiago de Chile, Chile
  • USP: Universidade de São Paulo, Brazil

    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

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.

Submit an Article to CACM

CACM welcomes unsolicited submissions on topics of relevance and value to the computing community.

You Just Read

A Perspective on Theoretical Computer Science in Latin America

View in the ACM Digital Library

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

DOI

10.1145/3419975

November 2020 Issue

Published: November 1, 2020

Vol. 63 No. 11

Pages: 102-107

Table of Contents

Related Reading

Advertisement

Advertisement

Join the Discussion (0)

Become a Member or Sign In to Post a Comment

The Latest from CACM

Explore More

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved

Communications of the ACM (CACM) is now a fully Open Access publication.

By opening CACM to the world, we hope to increase engagement among the broader computer science community and encourage non-members to discover the rich resources ACM has to offer.

Learn More