14th Latin American Theoretical Informatics Symposium

(25 – 29 May 2020) 5 – 8 January 2021 - Online conference

Originally scheduled to be at University of São Paulo | São Paulo, Brazil

About the event
Credit: Caio Pimenta / SPTuris.  


NEW January 20, 2021

LATIN 2020 was a success, thanks to all the participants!
Photos of the event are available, as well a small trailer.
You can check the whole playlist here.

January 8, 2021

We decided to make the closing remarks right after the end of the technical sessions.
So, please join us in the auditorium (and from there go to Zoom) at 16h20.
After that, everybody is invited to go back to the lobby.

January 7, 2021

The proceedings are freely available for the next month.

January 5, 2021

Due to some technical issues, we made two changes in the program:
1) the talk for paper "Improved Upper Bounds on the Growth Constants of Polyominoes and Polycubes", which will be given by Mira Shalah, went from Tuesday to 11h on Thursday, in Session 8.
2) the talk for paper "Dynamically Optimal Self-Adjusting Single-Source Tree Networks", by Chen Avin, will be replayed at 16h on Friday, in Session 13.

January 5, 2021

There has been a small program change: the talk for paper "Ordered Strip Packing", which will be given by Willem Sonke, went from 11h on Thursday to 15h40 on Friday, in Session 13.

January 3, 2021

The program with all of the programmed activities is finalized.
Titles and abstracts for the plenary talks as well as the posters are available.

December 10, 2020

The full version of the program is now available.

December 2, 2020

A preliminary version of the program is available and the venue is decided.

November 24, 2020

Registration is now open!

November 9, 2020

We apologize for taking very long to give you news about LATIN 2020.

The Local Organizing and the Steering committees have decided to run LATIN online from 5 to 8 January 2021.

We do hope that holding the event online will make it possible for everyone to take part and that this will make the meeting an exciting one.

The proceedings are in production and the proofs should be received by the authors anytime soon.

April 20, 2020

The Local Organizing Committee and the Steering Committee have decided to postpone the conference to 2021.

Final dates and further information will be given in the future.

We hope you are all safe and well and we hope to see you at the conference in 2021!

March 13, 2020

After careful consideration of the current Coronavirus outbreak, the LATIN 2020 Local Organizing Committee decided to put the registration temporarily on hold.

We kindly ask all participants to not make any travel or accommodation arrangements at this moment.
The Local Organizing Committee will continue monitoring the latest developments carefully.
We will update this site with further news as soon as we can.

The main concern of the Local Organizing Committee is the health of all conference participants and the limitation of the spreading of this new disease.
The situation changes every day and some countries and some institutions are imposing different restrictions.

We would like to wish you all the best and thank you for your support of LATIN 2020!


LATIN (Latin American Theoretical Informatics) was born in 1992, when a group of Latin American researchers, under the leadership of Imre Simon (São Paulo, Brazil), launched the first of a series of symposia in theoretical computer science, to be held triennially in Latin America. Since 1998 it has been held biennially: Valparaiso, Chile (1995); Campinas, Brazil (1998); Punta del Este, Uruguay (2000); Cancún, Mexico (2002); Buenos Aires, Argentina (2004); Valdivia, Chile (2006); Búzios, Brazil (2008); Oaxaca, Mexico (2010); Arequipa, Peru (2012); Montevideo, Uruguay (2014); Ensenada, Mexico (2016); and Buenos Aires, Argentina (2018).

We are excited to have this meeting, so close to our hearts, back in São Paulo in 2020.

For further information on LATIN, please visit the LATIN Symposium Website.


LATIN is devoted to different areas in theoretical computer science including, but not limited to: algorithms (approximation, online, combinatorial optimization, etc.), algorithmic game theory, analytic combinatorics and analysis of algorithms, automata theory and formal languages, combinatorics and graph theory, computational algebra and number theory, computational complexity, computational biology, computational geometry, data structures and information retrieval, foundations of data science and theoretical machine learning, parallel and distributed computing, quantum computing, randomization and pseudorandomness, sublinear algorithms and testing.


LATIN Symposium: (25 to 29 May 2020) 5 to 8 January 2021

Abstract submission: 17 November 2019
Paper submission: 24 November 2019
Author notification: 10 February 2020
Final version: 9 March 2020

Abstract submission: 1 March 2020 (new deadline)
Author notification: 17 March 2020
Final version: 20 March 2020

All deadlines are AOE time zone.


As in previous editions, the proceedings of LATIN 2020 will be published in Springer's Lecture Notes in Computer Science. Visit the LATIN webpage at SpringerLink.


An issue of ALGORITHMICA will be dedicated to selected papers of LATIN 2020.

Credit: Joshua Stevens, NASA Earth Observatory.  


Registration closed in December 28.

In case of any changes to the submitted registration or any problem, please contact the organisers.

Fees and payment deadlines

The payments are in the official currency of Brazil, the Brazilian Real (BRL).

Deadline Regular Speakers and Steering Committee members
December 27, 2020 100 BRL (approx. 18 USD) 0 BRL (free)

Payments will be accepted via credit card. For Brazilians, you may also pay via "débito" or "boleto" up to December 30, 2020.

Cancellation policy

All cancellation and changes must be received by December 30, 2020.


Full Papers

The submission process must be completed electronically through EasyChair. A paper abstract must be submitted by 17 November 2019.

Submitted papers are limited to twelve (12) single-column letter/A4-size pages in Springer LNCS format, and must be written in English. This page limit includes figures and references. An optional appendix (to be read at the program committee's discretion) may be included if desired. Submissions deviating substantially from this format risk rejection without consideration of their merits.

Authors should consult Springer's authors' guidelines and use their proceedings templates, either for LaTeX or for Word, for the preparation of their papers. Springer's proceedings LaTeX templates are also available in Overleaf. Springer encourages authors to include their ORCIDs in their papers. For each accepted paper, the corresponding author, acting on behalf of all of the authors of that paper, must complete and sign a Consent-to-Publish form. The corresponding author signing the copyright form should match the corresponding author marked on the paper. Once the files have been sent to Springer, changes relating to the authorship of the papers cannot be made. Authors who have included their email addresses in their papers will receive an email roughly four weeks after publication of the proceedings, linking them to their personal My Springer page. From here, they will be able to download the pdf of the entire volume. In addition, authors and editors are entitled to a 40% discount off Springer publications. Details are given on MySpringer page.


Manuscripts submitted to LATIN should present original, previously unpublished work. At the time of their submission to LATIN, manuscripts must not have been submitted to any other conference or scientific journal. Simultaneous submission of papers to any other conference with published proceedings is not allowed.

For each accepted paper at least one author must register and attend the symposium to present it. Moreover, an author cannot register for multiple papers. That is, each accepted paper must have its own registered presenter.


Imre Simon Test-of-Time Award

As of 2012, the Imre Simon Test-of-Time Award is given to the LATIN paper deemed most influential among all those published at least ten years prior to the current edition of the conference. Papers published in the LATIN proceedings up to and including 2010 were eligible for the 2020 award.

The awardee of the 2020 edition is Anne Brüggemann-Klein, for the paper Regular expressions into finite automata, published in the first LATIN, in 1992. Heartfelt congratulations!

Anne Brüggemann-Klein
LATIN 1992: Lecture Notes in Computer Science
Plaque of Imre Simon Test-of-Time award
Plaque of Imre Simon Test-of-Time award

Best Paper Award

Papers presented at the conference were considered for the LATIN 2020 Alejandro López-Ortiz Best Paper Award.

The awardees of the 2020 edition are Bruno Pasqualotto Cavalar, Mrinal Kumar, and Benjamin Rossman, for the paper Monotone Circuit Lower Bounds from Sunflowers. Heartfelt congratulations!

Bruno Pasqualotto Cavalar
Mrinal Kumar
Benjamin Rossman
LATIN 2020: Lecture Notes in Computer Science
Certificate of best paper award

Invited Speakers

Maria-Florina Balcan

Maria-Florina Balcan

Carnegie Mellon University

Nikhil Bansal

Nikhil Bansal

CWI and Eindhoven University of Technology

Maria Chudnovsky

Maria Chudnovsky

Princeton University

Nicole Immorlica

Nicole Immorlica

Microsoft Research

Eduardo Sany Laber

Eduardo Sany Laber

Pontifical Catholic University of Rio de Janeiro

Alexander Razborov

Alexander Razborov

The University of Chicago

Luca Trevisan

Luca Trevisan

Bocconi University

Bianca Zadrozny

Bianca Zadrozny

IBM Research Brazil


  • Program Committee
    • Yoshiharu Kohayakawa (Chair), Universidade de São Paulo, Brazil
    • Flávio Keidi Miyazawa (Chair), Universidade Estadual de Campinas, Brazil
    • Andris Ambainis, University of Latvia, Latvia
    • Frédérique Bassino, Université Paris 13, France
    • Flavia Bonomo, Universidad de Buenos Aires, Argentina
    • Prosenjit Bose, Carleton University, Canada
    • Olivier Carton, Université Paris Diderot, France
    • Ferdinando Cicalese, University of Verona, Italy
    • Jose Correa, Universidad de Chile, Chile
    • Pierluigi Crescenzi, Université Paris Diderot, France
    • Luc Devroye, McGill University, Canada
    • Martin Dietzfelbinger, TU Ilmenau, Germany
    • David Fernández-Baca, Iowa State University, USA
    • Esteban Feuerstein, Universidad de Buenos Aires, Argentina
    • Eldar Fischer, The Technion, Israel
    • Pierre Fraigniaud, Université Paris Diderot, France
    • Martin Fürer, The Pennsylvania State University, USA
    • Anna Gál, The University of Texas at Austin, USA
    • Ron Holzman, The Technion, Israel
    • Marcos Kiwi, Universidad de Chile, Chile
    • Teresa Krick, Universidad de Buenos Aires, Argentina
    • Cláudia Linhares Sales, Universidade Federal do Ceará, Brazil
    • Kazuhisa Makino, Kyoto University, Japan
    • Conrado Martínez, Universitat Politècnica de Catalunya, Spain
    • Marco Molinaro, Pontifical Catholic University of Rio de Janeiro, Brazil
    • Veli Mäkinen, University of Helsinki, Finland
    • Gonzalo Navarro, Universidad de Chile, Chile
    • Rolf Niedermeier, TU Berlin, Germany
    • Rafael Oliveira, University of Toronto, Canada
    • Roberto Imbuzeiro Oliveira, IMPA, Brazil
    • Daniel Panario, Carleton University, Canada
    • Alessandro Panconesi, Sapienza Università di Roma, Italy
    • Pan Peng, University of Sheffield, UK
    • Ely Porat, Bar-Ilan University, Israel
    • Paweł Prałat, Ryerson University, Canada
    • Pavel Pudlák, Czech Academy of Sciences, Czech Republic
    • Svetlana Puzynina, Saint Petersburg State University, Russia
    • Sergio Rajsbaum, Universidad Nacional Autónoma de México, Mexico
    • Andrea Richa, Arizona State University, USA
    • Rahul Santhanam, University of Oxford, UK
    • Asaf Shapira, Tel Aviv University, Israel
    • Alistair Sinclair, UC Berkeley, USA
    • Mohit Singh, Georgia Tech, USA
    • Maya Stein, Universidad de Chile, Chile
    • Jayme Luiz Szwarcfiter, Universidade Federal do Rio de Janeiro, Brazil
    • Eli Upfal, Brown University, USA
    • Jorge Urrutia, Universidad Nacional Autónoma de México, Mexico
    • Brigitte Vallée, Université de Caen, France
    • Mikhail V. Volkov, Ural Federal University, Russia
    • Raphael Yuster, University of Haifa, Israel
  • Organizing Committee
    • Carla Negri Lintzmayer (co-chair), Universidade Federal do ABC, Brazil
    • Guilherme Oliveira Mota (co-chair), Universidade Federal do ABC, Brazil
    • José Coelho de Pina (co-chair), Universidade de São Paulo, Brazil
    • Yoshiko Wakabayashi (co-chair), Universidade de São Paulo, Brazil
    • Marcel Kenji de Carli Silva, Universidade de São Paulo, Brazil
    • Carlos Eduardo Ferreira, Universidade de São Paulo, Brazil
    • Cristina Gomes Fernandes, Universidade de São Paulo, Brazil
    • Arnaldo Mandel, Universidade de São Paulo, Brazil
    • Daniel Morgato Martin, Universidade Federal do ABC, Brazil
    • Lehilton Lelis Chaves Pedrosa, Universidade Estadual de Campinas, Brazil
    • Sinai Robins, Universidade de São Paulo, Brazil
    • Cristiane Maria Sato, Universidade Federal do ABC, Brazil
    • Rafael Crivellari Saliba Schouery, Universidade Estadual de Campinas, Brazil
    • Eduardo Cândido Xavier, Universidade Estadual de Campinas, Brazil
  • Latin Steering Committee
    • Kirk Pruhs (Chair), University of Pittsburgh, USA
    • Michael A. Bender, Stony Brook University, USA
    • Cristina G. Fernandes, Universidade de São Paulo, Brazil
    • Joachim von zur Gathen, Bonn-Aachen International Center for Information Technology, Germany
    • Evangelos Kranakis, Carleton University, Canada
    • Alfredo Viola, Universidad de la República, Uruguay


We are thrilled to announce that LATIN 2020 will be produced by Virtual Chair on the Gather platform.

Accepted papers

Full papers published in LNCS are available until February 15, 2021, in this link.

  • Towards a Definitive Measure of Repetitiveness
    Tomasz Kociumaka, Gonzalo Navarro and Nicola Prezza
  • How to Color a French Flag: Biologically Inspired Algorithms for Scale-Invariant Patterning
    Bertie Ancona, Ayesha Bajwa, Nancy Lynch and Frederik Mallmann-Trenn
  • Exponential-time quantum algorithms for graph coloring problems
    Kazuya Shimizu and Ryuhei Mori
  • Simple Intrinsic Simulation of Cellular Automata in Oritatami Molecular Folding Model
    Daria Pchelina, Nicolas Schabanel, Shinnosuke Seki and Yuki Ubukata
  • Probabilistically Faulty Searching on a Half-Line
    Anthony Bonato, Konstantinos Georgiou, Calum MacRury and Pawel Pralat
  • Ordered Strip Packing
    Kevin Buchin, Dmitry Kosolobov, Willem Sonke, Bettina Speckmann and Kevin Verbeek
  • Sherali-Adams and the binary encoding of combinatorial principles
    Stefan Dantchev, Abdul Ghani and Barnaby Martin
  • On Minimal-Perimeter Lattice Animals
    Gill Barequet and Gil Ben-Shachar
  • Tight Bounds on Sensitivity and Block Sensitivity of Some Classes of Transitive Functions
    Siddhesh Chaubal and Anna Gal
  • Quasi-random words and limits of word sequences
    Hiệp Hàn, Marcos Kiwi and Matías Pavez-Signé Pavez-Signé
  • An $\Omega(n^3)$ Lower Bound on the Number of Cell Crossings for Weighted Shortest Paths in 3-dimensional Polyhedral Structures
    Frank Bauernöppel, Anil Maheshwari and Jörg-Rüdiger Sack
  • Transmitting Once to Elect a Leader on Wireless Networks
    Ny Aina Andriambolamalala and Vlady Ravelomanana
  • Structural Parameterizations for Equitable Coloring
    Guilherme de Castro Mendes Gomes, Matheus Resende Guedes and Vinicius F. dos Santos
  • Rectilinear convex hull of points in 3D
    Pablo Pérez-Lantero, Carlos Seara and Jorge Urrutia
  • Tractable Unordered 3-CNF Games
    Md Lutfar Rahman and Thomas Watson
  • Near-linear Time Algorithms for Approximate Minimum Degree Spanning Trees
    Ran Duan, Haoqing He and Tianyi Zhang
  • Lower bounds for testing complete positivity and quantum separability
    Costin Badescu and Ryan O'Donnell
  • PTAS for Steiner Tree on Map Graphs
    Jaroslaw Byrka, Mateusz Lewandowski, Syed Mohammad Meesum, Joachim Spoerhase and Sumedha Uniyal
  • Hardness of some variants of the graph coloring game
    Thiago Marcilon, Nicolas Martins and Rudini Sampaio
  • Approximation Algorithms for Cost-robust Discrete Minimization Problems Based on their LP-Relaxations
    Khaled Elbassioni
  • Query Minimization under Stochastic Uncertainty
    Steven Chaplick, Magnús M. Halldórsson, Murilo de Lima and Tigran Tonoyan
  • A method to prove the nonrationality of some combinatorial generating functions
    Miklos Bona
  • Thresholds in the Lattice of Subspaces of $(F_q)^n$
    Benjamin Rossman
  • Binary Decision Diagrams: from Tree Compaction to Sampling
    Julien Clément and Antoine Genitrini
  • Scheduling on Hybrid Platforms: Improved Approximability Window
    Vincent Fagnon, Imed Kacem, Giorgio Lucarelli and Bertrand Simon
  • Improved Upper Bounds on the Growth Constants of Polyominoes and Polycubes
    Gill Barequet and Mira Shalah
  • Suffix Trees, DAWGs, and CDAWGs for Forward and Backward Tries
    Shunsuke Inenaga
  • Graph sandwich problem for the property of being well-covered and partitionable into $k$ independent sets and $\ell$ cliques
    Sancrey Rodrigues Alves, Fernanda Couto, Luerbio Faria, Sylvain Gravier, Sulamita Klein and Uéverton Souza
  • On some subclasses of split B1-EPG graphs
    Zakir Deniz, Simon Nivelle, Bernard Ries and David Schindl
  • On the Collection of Fringe Subtrees in Random Binary Trees
    Louisa Seelbach Benkner and Stephan Wagner
  • On the maximum number of edges in chordal graphs of bounded degree and matching number
    Jean Blair, Pinar Heggernes, Paloma de Lima and Daniel Lokshtanov
  • Graph Square Roots of Small Distance from Degree One Graphs
    Petr Golovach, Paloma de Lima and Charis Papadopoulos
  • Steiner Trees for Hereditary Graph Classes
    Hans Bodlaender, Nick Brettell, Matthew Johnson, Giacomo Paesani, Daniel Paulusma and Erik Jan van Leeuwen
  • The Hardness of Sampling Connected Subgraphs
    Andrew Read-McFarland and Daniel Stefankovic
  • Flips in Higher Order Delaunay triangulations
    Elena Arseneva, Prosenjit Bose, Pilar Cano and Rodrigo Silveira
  • On the Helly Subclasses of Interval Bigraphs and Circular Arc Bigraphs
    Marina Groshaus, André L. P. Guedes and Fabricio Schiavon Kolberg
  • Maximizing Happiness in Graphs of Bounded Clique-Width
    Ivan Bliznets and Danil Sagunov
  • Asymptotics for Push on the Complete Graph
    Rami Daknama, Konstantinos Panagiotou and Simon Reisser
  • Approximating Routing and Connectivity Problems with Multiple Distances
    Greis Y. O. Quesquen and Lehilton L. C. Pedrosa
  • Monotone Circuit Lower Bounds from Robust Sunflowers
    Bruno Pasqualotto Cavalar, Mrinal Kumar and Benjamin Rossman
  • Shortest Rectilinear Path Queries to Rectangles in a Rectangular Domain
    Mincheol Kim, Sang Duk Yoon and Hee-Kap Ahn
  • Lower bounds for Max-Cut via semidefinite programming
    Charlie Carlson, Alexandra Kolla, Luca Trevisan, Ray Li, Nitya Mani and Benny Sudakov
  • Batched Predecessor and Sorting with Size-Priced Information in External Memory
    Mayank Goswami, Michael A. Bender, Dzejla Medjedovic, Pablo Montes and Kostas Tsichlas
  • A 2-approximation for the k-prize-collecting Steiner tree problem
    Hugo Kooki Kasuya Rosado and Lehilton L. C. Pedrosa
  • Leafy Spanning Arborescences in DAGs
    Cristina Fernandes and Carla Negri Lintzmayer
  • On Symmetry and Initialization for Neural Networks
    Ido Nachum and Amir Yehudayoff
  • Graph Hamiltonicity Parameterized by Proper Interval Deletion Set
    Petr A. Golovach, R. Krithika, Abhishek Sahu, Saket Saurabh and Meirav Zehavi
  • Dynamically Optimal Self-Adjusting Single-Source Tree Networks
    Chen Avin, Kaushik Mondal and Stefan Schmid
  • Computing Balanced Convex Partitions of Lines
    Sergey Bereg
  • Farthest color Voronoi diagrams: complexity and algorithms
    Ioannis Mantas, Evanthia Papadopoulou, Vera Sacristán and Rodrigo Silveira


The following is a short program. Please click here for the full program.

Times in the program are shown in BRT Time (UTC -3).

Getting to know the Virtual Chair space

Opening 🎤 (auditorium)

Technical sessions 1 (room B) and 2 (room A)

Extra Q&A for technical sessions (lobby) / Break
Nikhil Bansal

Plenary lecture (auditorium)

Nikhil Bansal

Poster session 1 (lobby)

(and lunch break)
Maria-Florina Balcan

Plenary lecture (auditorium)

Maria-Florina Balcan

Technical sessions 3 (room B) and 4 (room A)

Extra Q&A for technical sessions (lobby)

End of day 1


Technical sessions 5 (room B) and 6 (room A)

Extra Q&A for technical sessions (lobby) / Break
Maria Chudnovsky

Plenary lecture (auditorium)

Maria Chudnovsky

Poster session 2 (lobby)

(and lunch break)
Eduardo Sany Laber

Plenary lecture (auditorium)

Eduardo Sany Laber

Technical session 7 (room B)

Extra Q&A for technical sessions (lobby)

End of day 2


Technical sessions 8 (room B) and 9 (room A)

Extra Q&A for technical sessions (lobby) / Break
Bianca Zadrozny

Plenary lecture (auditorium)

Bianca Zadrozny

Poster session 1 (lobby)

(and lunch break)
Alexander Razborov

Plenary lecture (auditorium)

Alexander Razborov

Awards session 🏆 (auditorium)

Business meeting 👔 (auditorium)

End of day 3


Technical sessions 10 (room B) and 11 (room A)

Extra Q&A for technical sessions (lobby) / Break
Luca Trevisan

Plenary lecture (auditorium)

Luca Trevisan

Poster session 2 (lobby)

(and lunch break)
Nicole Immorlica

Plenary lecture (auditorium)

Nicole Immorlica

Technical sessions 12 (room B) and 13 (room A)

Closing remarks 🎤 (auditorium)

Extra Q&A for technical sessions (lobby)

End of LATIN 2020


We are thankful for our Sponsors!