NEW 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
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.
SCOPE AND TOPICS
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.
(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.
ALGORITHMICA SPECIAL ISSUE
An issue of ALGORITHMICA will be dedicated to selected papers of LATIN 2020.
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 are eligible for the 2020 award.
Best Paper Award
Papers presented at the conference will be considered for the LATIN 2020 Alejandro Lopez-Ortiz Best Paper Award.
- 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
- 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
Details will be given soon.
- 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
- 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
- Thresholds in the Lattice of Subspaces of $(F_q)^n$
- 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
- 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
- Farthest color Voronoi diagrams: complexity and algorithms
Ioannis Mantas, Evanthia Papadopoulou, Vera Sacristán and Rodrigo Silveira