News!
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 (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.
IMPORTANT DATES
LATIN Symposium: (25 to 29 May 2020) 5 to 8 January 2021
Papers
Abstract submission: 17 November 2019
Paper submission: 24 November 2019
Author notification: 10 February 2020
Final version: 9 March 2020
Posters
Abstract submission: 1 March 2020 (new deadline)
Author notification: 17 March 2020
Final version: 20 March 2020
All deadlines are AOE time zone.
PROCEEDINGS
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.
ALGORITHMICA SPECIAL ISSUE
An issue of ALGORITHMICA will be dedicated to selected papers of LATIN 2020.
Registration
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.
Submission
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.
Important
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.
Awards
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!
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!
Invited Speakers
Maria-Florina Balcan
Carnegie Mellon University
Nikhil Bansal
CWI and Eindhoven University of Technology
Maria Chudnovsky
Princeton University
Nicole Immorlica
Microsoft Research
Eduardo Sany Laber
Pontifical Catholic University of Rio de Janeiro
Luca Trevisan
Bocconi University
Bianca Zadrozny
IBM Research Brazil
Committees
-
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
Venue
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
Program
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)
Plenary lecture (auditorium)
Nikhil BansalPoster session 1 (lobby)
(and lunch break)Plenary lecture (auditorium)
Maria-Florina BalcanTechnical sessions 3 (room B) and 4 (room A)
End of day 1
Socialization
Technical sessions 5 (room B) and 6 (room A)
Plenary lecture (auditorium)
Maria ChudnovskyPoster session 2 (lobby)
(and lunch break)Plenary lecture (auditorium)
Eduardo Sany LaberTechnical session 7 (room B)
End of day 2
Socialization
Technical sessions 8 (room B) and 9 (room A)
Plenary lecture (auditorium)
Bianca ZadroznyPoster session 1 (lobby)
(and lunch break)Plenary lecture (auditorium)
Alexander RazborovAwards session 🏆 (auditorium)
Business meeting 👔 (auditorium)
End of day 3
Socialization
Technical sessions 10 (room B) and 11 (room A)
Plenary lecture (auditorium)
Luca TrevisanPoster session 2 (lobby)
(and lunch break)Plenary lecture (auditorium)
Nicole ImmorlicaTechnical sessions 12 (room B) and 13 (room A)
Closing remarks 🎤 (auditorium)
End of LATIN 2020
Gallery
All photos can be seen here.
The whole playlist of videos is here.