____  __
  ______     _______


Yoshiharu Kohayakawa (Program Commmittee co-chair), Universidade de São Paulo, Brazil
Flávio Keidi Miyazawa (Program Committee co-chair), Universidade Estadual de Campinas, Brazil
Carla Negri Lintzmayer (Organizing Committee co-chair), Universidade Federal do ABC, Brazil
Guilherme Oliveira Mota (Organizing Committee co-chair), Universidade Federal do ABC, Brazil
José Coelho de Pina (Organizing Committee co-chair), Universidade de São Paulo, Brazil
Yoshiko Wakabayashi (Organizing Committee co-chair), Universidade de São Paulo, Brazil

[Top] [Home] [All LATIN Chairs]

  Program Committee

Yoshiharu Kohayakawa, Universidade de São Paulo, Brazil
Flávio Keidi Miyazawa, 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

[Top] [Home] [All LATIN PCs]

  Organizing Committee

Carla Negri Lintzmayer, Universidade Federal do ABC, Brazil
Guilherme Oliveira Mota, Universidade Federal do ABC, Brazil
José Coelho de Pina, Universidade de São Paulo, Brazil
Yoshiko Wakabayashi, 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

[Top] [Home] [All LATIN Org. Committees]

  Invited Speakers

Maria-Florina Balcan (Carnegie Mellon University), Data-driven algorithm design

Data-driven algorithm design for combinatorial problems is an important aspect of modern data science. Rather than using off the shelf algorithms that only have worst case performance guarantees, practitioners typically optimize over large families of parameterized algorithms and tune the parameters of these algorithms using a training set of problem instances from their domain to determine a configuration with high expected performance over future instances. However, most of this work comes with no performance guarantees. The challenge is that for many combinatorial problems, including partitioning and subset selection problems, a small tweak to the parameters can cause a cascade of changes in the algorithm's behavior, so the algorithm's performance is a discontinuous function of its parameters.

In this talk, I will present new work that helps put data-driven combinatorial algorithm selection on firm foundations. This includes strong computational and statistical performance guarantees, both for the batch and online scenarios where a collection of typical problem instances from the given application are presented either all at once or in an online fashion, respectively. I will describe both specific examples (for clustering, partitioning, and subset selection problems) and general principles that emerge in this context (including general techniques for sample complexity guarantees in the batch setting and no-regret guarantees in the online settings).

Nikhil Bansal (CWI and Eindhoven University of Technology), Discrepancy, Rounding and Approximation

Discrepancy theory deals with the following question: Given a set system on some universe of elements, color the elements red and blue so that each set in the system is colored as evenly as possible. I will give an overview of discrepancy and describe some of its applications. Then we focus on some results and techniques in discrepancy, and in particular show how they can be used to design new general rounding techniques leading to improved approximation guarantees for various algorithmic problems.

Maria Chudnovsky (Princeton University), Induced subgraphs and tree decompositions

Tree decompositions are a powerful tool in structural graph theory, that is traditionally used in the context of forbidden graph minors. Connecting tree decompositions and forbidden induced subgraphs has so far remained out of reach. Recently we obtained several results in this direction; the talk will be a survey of these results.

Nicole Immorlica (Microsoft Research), Incentivizing Exploration with Selective Data Disclosure

We study the design of rating systems that incentivize efficient social learning. Agents arrive sequentially and choose actions, each of which yields a reward drawn from an unknown distribution. A policy maps the rewards of previously-chosen actions to messages for arriving agents. The regret of a policy is the difference, over all rounds, between the expected reward of the best action and the reward induced by the policy. Prior work proposes policies that recommend a single action to each agent, obtaining optimal regret under standard rationality assumptions. We instead assume a frequentist behavioral model and, accordingly, restrict attention to disclosure policies that use messages consisting of the actions and rewards from a subsequence of past agents, chosen ex ante. We design a policy with optimal regret in the worst case over reward distributions. Our research suggests three components of effective policies: independent focus groups, group aggregators, and interlaced information structures.

Joint work with Jieming Mao, Alex Slivkins and Steven Wu.

Eduardo Sany Laber (Pontifical Catholic University of Rio de Janeiro), On the Price of Explainability for some Clustering Problems

Machine learning models and algorithms have been used in a number of systems that take decisions that affect our lives. Thus, explainable methods are desirable so that people are able to have a better understanding about their behaviour. However, we may be forced to lose quality and/or efficiency in order to achieve explainability. In this talk we investigate, from a theoretical perspective, the price of explainability for some clustering problems.

Alexander Razborov (The University of Chicago), Theons and Quasi-Randomness

There are two known approaches to the theory of limits of discrete combinatorial objects: geometric (graph limits) and algebraic (flag algebras). In the first part of the talk we present a general framework intending to combine useful features of both theories and compare it with previous attempts of this kind. Our main objects are \(T\)-ons, for a universal relational first-order theory \(T\); they generalize all previously considered partial cases, some of them (like permutons) in a rather non-trivial way.

In the second part we apply this framework to offer a new perspective on quasi-randomness for combinatorial objects more complicated than ordinary graphs. Our quasi-randomness properties are natural in the sense that they do not use ad hoc densities and they are preserved under the operation of defining combinatorial structures of one kind from structures of a different kind. One key concept in this theory is that of unique coupleability roughly meaning that any alignment of two objects on the same ground set should “look like” random.

Based on two joint papers with Leonardo Coregliano: Russian Mathematical Surveys (2020, 75(4)) and arXiv:2012.11773.

Luca Trevisan (Bocconi University), Graph and Hypergraph Sparsification
graph \(H\) is a sparsifier of a graph \(G\) if \(H\) has much fewer edges than \(G\) and, in an appropriate technical sense, \(H\) “approximates” \(G\). Sparsifiers are useful as compressed representations of graphs and to speed up certain graph algorithms. In a “cut sparsifier,” the notion of approximation is that every cut is crossed by approximately the same number of edges in \(G\) as in \(H\). In a “spectral sparsifier” a stronger, linear-algebraic, notion of approximation holds. Similar definitions can be given for hypergraph.

We discuss recent progress on constructions and lower bounds for graph and hypergraph sparsification, and we point out some challenging open problems.

Bianca Zadrozny (IBM Research Brazil), Evaluating classifier learning methods under covariate shift and spatial correlation

Classifier learning methods commonly assume that the training data consist of randomly drawn examples from the same distribution as the test examples about which the learned model is expected to make predictions. In the real world, the joint distribution of inputs to the model and outputs of the model differs between training and test data, a problem known as sample selection bias or dataset shift. In this talk, I will review existing methods for dealing with this problem, in particular of the special case known as covariate shift where only the input distribution changes and the conditional distribution of the output for a given input is assumed to remain fixed. I will then introduce the problem of covariate shift in geospatial data and illustrate the challenges of learning from geospatial data by assessing existing methods for evaluating the accuracy of classifier learning methods under covariate shift and spatial correlation.

[Top] [Home] [All LATIN Inv. Speakers]


Julien Clément and Antoine Genitrini, Binary Decision Diagrams: From Tree Compaction to Sampling. [Bibtex]

Sancrey Rodrigues Alves, Fernanda Couto, Luérbio Faria, Sylvain Gravier, Sulamita Klein and Uéverton S. Souza, Graph Sandwich Problem for the Property of Being Well-Covered and Partitionable into \(k\) Independent Sets and \(\ell\) Cliques. [Bibtex]

Bertie Ancona, Ayesha Bajwa, Nancy A. Lynch and Frederik Mallmann-Trenn, How to Color a French Flag - Biologically Inspired Algorithms for Scale-Invariant Patterning. [Bibtex]

Ny Aina Andriambolamalala and Vlady Ravelomanana, Transmitting once to Elect a Leader on Wireless Networks. [Bibtex]

Elena Arseneva, Prosenjit Bose, Pilar Cano and Rodrigo I. Silveira, Flips in Higher Order Delaunay Triangulations. [Bibtex]

Chen Avin, Kaushik Mondal and Stefan Schmid, Dynamically Optimal Self-adjusting Single-Source Tree Networks. [Bibtex]

Costin Badescu and Ryan O'Donnell, Lower Bounds for Testing Complete Positivity and Quantum Separability. [Bibtex]

Gill Barequet and Gil Ben-Shachar, On Minimal-Perimeter Lattice Animals. [Bibtex]

Gill Barequet and Mira Shalah, Improved Upper Bounds on the Growth Constants of Polyominoes and Polycubes. [Bibtex]

Frank Bauernöppel, Anil Maheshwari and Jörg-Rüdiger Sack, An \(\Omega(n^3)\) Lower Bound on the Number of Cell Crossings for Weighted Shortest Paths in 3-Dimensional Polyhedral Structures. [Bibtex]

Michael A. Bender, Mayank Goswami, Dzejla Medjedovic, Pablo Montes and Kostas Tsichlas, Batched Predecessor and Sorting with Size-Priced Information in External Memory. [Bibtex]

Louisa Seelbach Benkner and Stephan G. Wagner, On the Collection of Fringe Subtrees in Random Binary Trees. [Bibtex]

Sergey Bereg, Computing Balanced Convex Partitions of Lines. [Bibtex]

Jean R. S. Blair, Pinar Heggernes, Paloma T. Lima and Daniel Lokshtanov, On the Maximum Number of Edges in Chordal Graphs of Bounded Degree and Matching Number. [Bibtex]

Ivan Bliznets and Danil Sagunov, Maximizing Happiness in Graphs of Bounded Clique-Width. [Bibtex]

Hans L. Bodlaender, Nick Brettell, Matthew Johnson, Giacomo Paesani, Daniël Paulusma and Erik Jan van Leeuwen, Steiner Trees for Hereditary Graph Classes. [Bibtex]

Miklós Bóna, A Method to Prove the Nonrationality of Some Combinatorial Generating Functions. [Bibtex]

Anthony Bonato, Konstantinos Georgiou, Calum MacRury and Pawel Pralat, Probabilistically Faulty Searching on a Half-Line - (Extended Abstract). [Bibtex]

Kevin Buchin, Dmitry Kosolobov, Willem Sonke, Bettina Speckmann and Kevin Verbeek, Ordered Strip Packing. [Bibtex]

Jaroslaw Byrka, Mateusz Lewandowski, Syed Mohammad Meesum, Joachim Spoerhase and Sumedha Uniyal, PTAS for Steiner Tree on Map Graphs. [Bibtex]

Charles Carlson, Alexandra Kolla, Ray Li, Nitya Mani, Benny Sudakov and Luca Trevisan, Lower Bounds for Max-Cut via Semidefinite Programming. [Bibtex]

Bruno Pasqualotto Cavalar, Mrinal Kumar and Benjamin Rossman, Monotone Circuit Lower Bounds from Robust Sunflowers. [Bibtex]

Steven Chaplick, Magnús M. Halldórsson, Murilo Santos de Lima and Tigran Tonoyan, Query Minimization Under Stochastic Uncertainty. [Bibtex]

Siddhesh Chaubal and Anna Gál, Tight Bounds on Sensitivity and Block Sensitivity of Some Classes of Transitive Functions. [Bibtex]

Rami Daknama, Konstantinos Panagiotou and Simon Reisser, Asymptotics for Push on the Complete Graph. [Bibtex]

Stefan S. Dantchev, Abdul Ghani and Barnaby Martin, Sherali-Adams and the Binary Encoding of Combinatorial Principles. [Bibtex]

Zakir Deniz, Simon Nivelle, Bernard Ries and David Schindl, On Some Subclasses of Split \(B_1\)-EPG Graphs. [Bibtex]

Ran Duan, Haoqing He and Tianyi Zhang, Near-Linear Time Algorithm for Approximate Minimum Degree Spanning Trees. [Bibtex]

Khaled M. Elbassioni, Approximation Algorithms for Cost-Robust Discrete Minimization Problems Based on Their LP-Relaxations. [Bibtex]

Vincent Fagnon, Imed Kacem, Giorgio Lucarelli and Bertrand Simon, Scheduling on Hybrid Platforms: Improved Approximability Window. [Bibtex]

Cristina G. Fernandes and Carla Negri Lintzmayer, Leafy Spanning Arborescences in DAGs. [Bibtex]

Petr A. Golovach, R. Krithika, Abhishek Sahu, Saket Saurabh and Meirav Zehavi, Graph Hamiltonicity Parameterized by Proper Interval Deletion Set. [Bibtex]

Petr A. Golovach, Paloma T. Lima and Charis Papadopoulos, Graph Square Roots of Small Distance from Degree One Graphs. [Bibtex]

Guilherme de C. M. Gomes, Matheus R. Guedes and Vinicius F. dos Santos, Structural Parameterizations for Equitable Coloring. [Bibtex]

Marina Groshaus, André Luiz Pires Guedes and Fabricio Schiavon Kolberg, On the Helly Subclasses of Interval Bigraphs and Circular Arc Bigraphs. [Bibtex]

Hiệp Hàn, Marcos Kiwi and Matías Pavez-Signé, Quasi-Random Words and Limits of Word Sequences. [Bibtex]

Shunsuke Inenaga, Suffix Trees, DAWGs and CDAWGs for Forward and Backward Tries. [Bibtex]

Mincheol Kim, Sang Duk Yoon and Hee-Kap Ahn, Shortest Rectilinear Path Queries to Rectangles in a Rectangular Domain. [Bibtex]

Tomasz Kociumaka, Gonzalo Navarro and Nicola Prezza, Towards a Definitive Measure of Repetitiveness. [Bibtex]

Ioannis Mantas, Evanthia Papadopoulou, Vera Sacristán and Rodrigo I. Silveira, Farthest Color Voronoi Diagrams: Complexity and Algorithms. [Bibtex]

Thiago Marcilon, Nícolas A. Martins and Rudini Menezes Sampaio, Hardness of Variants of the Graph Coloring Game. [Bibtex]

Ido Nachum and Amir Yehudayoff, On Symmetry and Initialization for Neural Networks. [Bibtex]

Daria Pchelina, Nicolas Schabanel, Shinnosuke Seki and Yuki Ubukata, . [Bibtex]

Lehilton L. C. Pedrosa and Greis Y. O. Quesquén, Approximating Routing and Connectivity Problems with Multiple Distances. [Bibtex]

Lehilton L. C. Pedrosa and Hugo Kooki Kasuya Rosado, A 2-Approximation for the \(k\)-Prize-Collecting Steiner Tree Problem. [Bibtex]

Pablo Pérez-Lantero, Carlos Seara and Jorge Urrutia, Rectilinear Convex Hull of Points in 3D. [Bibtex]

Md Lutfar Rahman and Thomas Watson, Tractable Unordered 3-CNF Games. [Bibtex]

Andrew Read-McFarland and Daniel Stefankovic, The Hardness of Sampling Connected Subgraphs. [Bibtex]

Benjamin Rossman, Thresholds in the Lattice of Subspaces of \(\mathbb{F}_q^n\). [Bibtex]

Kazuya Shimizu and Ryuhei Mori, Exponential-Time Quantum Algorithms for Graph Coloring Problems. [Bibtex]

[Top] [Home] [All LATIN Papers]


CAPES (Coordenação de Aperfeicoamento de Pessoal de Nível Superior)
CNPq (Conselho Nacional de Desenvolvimento Científico e Tecnológico)
FAPESP (Fundação de Amparo à Pesquisa do Estado de São Paulo)
IME/USP (Instituto de Matemática e Estatística / Universidade de São Paulo)
SBC (Sociedade Brasileira de Computação)
UFABC (Universidade Federal do ABC)
Unicamp (Universidade Estadual de Campinas)
USP (Universidade de São Paulo)
B2W Digital

[Top] [Home] [All LATIN Sponsors]


The conference was held by Virtual Chair on the Gather platform.

[Top] [Home] [All LATIN Locations]


[Top] [Home] [All LATIN Photos]


No. of submissions 136
No. of accepted papers 50
% of accepted papers 36.8%
Total No. of authors 151
Avg. No. of authors per paper 3.02
No. of countries represented 29
No. of papers according to how many authors work in Latin-America
    At least one 11(22.0%)
    All 7(14.0%)

Statistics by Country of Author's Affiliation


1.0(0.7%)0.20(0.4%)Bosnia and Herzegovina
0.5(0.3%)0.25(0.5%)South Africa

Authors with n affiliations contributes 1/n to each affiliation.
** Papers with n authors contribute 1/n to each affiliation.

Statistics by Region of Author's Affiliation


32.5(21.5%)12.39(24.8%)USA & Canada
20.0(13.2%)7.22(14.4%)Australia & Asia
10.0(6.6%)4.37(8.7%)Middle East

Authors with n affiliations contributes 1/n to each affiliation.
** Papers with n authors contribute 1/n to each affiliation.


South Africa Wagner, Stephan G.;

Australia & Asia

China Duan, Ran; He, Haoqing; Zhang, Tianyi;
Russia Arseneva, Elena; Bliznets, Ivan; Kosolobov, Dmitry; Sagunov, Danil;
Japan Inenaga, Shunsuke; Mori, Ryuhei; Seki, Shinnosuke; Shimizu, Kazuya; Ubukata, Yuki;
India Krithika, R.; Kumar, Mrinal; Mondal, Kaushik; Sahu, Abhishek; Saurabh, Saket;
Korea Ahn, Hee-Kap; Kim, Mincheol; Yoon, Sang Duk;


Italy Prezza, Nicola; Trevisan, Luca;
Iceland Halldórsson, Magnús M.;
Bosnia and Herzegovina Medjedovic, Dzejla;
Poland Byrka, Jaroslaw; Lewandowski, Mateusz; Meesum, Syed Mohammad;
Sweden Wagner, Stephan G.;
Norway Golovach, Petr A.; Heggernes, Pinar; Lima, Paloma T.;
Netherlands Bodlaender, Hans L.; Buchin, Kevin; Chaplick, Steven; Sonke, Willem; Speckmann, Bettina; van Leeuwen, Erik Jan; Verbeek, Kevin;
Finland Spoerhase, Joachim; Uniyal, Sumedha;
Spain Cano, Pilar; Sacristán, Vera; Seara, Carlos; Silveira, Rodrigo I.;
Switzerland Mantas, Ioannis; Nachum, Ido; Papadopoulou, Evanthia; Ries, Bernard; Schindl, David; Sudakov, Benny;
France Andriambolamalala, Ny Aina; Clément, Julien; Fagnon, Vincent; Genitrini, Antoine; Kacem, Imed; Klein, Sulamita; Lucarelli, Giorgio; Nivelle, Simon; Pchelina, Daria; Ravelomanana, Vlady; Schabanel, Nicolas;
UK Brettell, Nick; Dantchev, Stefan S.; de Lima, Murilo Santos; Ghani, Abdul; Johnson, Matthew; Mallmann-Trenn, Frederik; Martin, Barnaby; Paesani, Giacomo; Paulusma, Daniël;
Germany Bauernöppel, Frank; Chaplick, Steven; Daknama, Rami; Panagiotou, Konstantinos; Reisser, Simon; Seelbach Benkner, Louisa; Simon, Bertrand;
Austria Schmid, Stefan;
Greece Papadopoulos, Charis; Tsichlas, Kostas;


Mexico Urrutia, Jorge;
Brazil Alves, Sancrey Rodrigues; Cavalar, Bruno Pasqualotto; Couto, Fernanda; dos Santos, Vinicius F.; Faria, Luérbio; Fernandes, Cristina G.; Gomes, Guilherme de C. M.; Gravier, Sylvain; Groshaus, Marina; Guedes, André Luiz Pires; Guedes, Matheus R.; Kolberg, Fabricio Schiavon; Lintzmayer, Carla Negri; Marcilon, Thiago; Martins, Nícolas A.; Pedrosa, Lehilton L. C.; Quesquén, Greis Y. O.; Rosado, Hugo Kooki Kasuya; Sampaio, Rudini Menezes; Souza, Uéverton S.;
Chile Hàn, Hiệp; Kiwi, Marcos; Navarro, Gonzalo; Pavez-Signé, Matías; Pérez-Lantero, Pablo;

Middle East

Israel Avin, Chen; Barequet, Gill; Ben-Shachar, Gil; Kociumaka, Tomasz; Tonoyan, Tigran; Yehudayoff, Amir; Zehavi, Meirav;
UAE Elbassioni, Khaled M.;
Turkey Deniz, Zakir;

USA & Canada

Canada Bonato, Anthony; Bose, Prosenjit; Cano, Pilar; Georgiou, Konstantinos; MacRury, Calum; Maheshwari, Anil; Pralat, Pawel; Rossman, Benjamin; Sack, Jörg-Rüdiger;
USA Ancona, Bertie; Badescu, Costin; Bajwa, Ayesha; Bender, Michael A.; Bereg, Sergey; Blair, Jean R. S.; Bóna, Miklós; Carlson, Charles; Chaubal, Siddhesh; Gál, Anna; Goswami, Mayank; Kolla, Alexandra; Li, Ray; Lokshtanov, Daniel; Lynch, Nancy A.; Mani, Nitya; Montes, Pablo; O'Donnell, Ryan; Rahman, Md Lutfar; Read-McFarland, Andrew; Shalah, Mira; Stefankovic, Daniel; Watson, Thomas;

[Top] [Home] [All LATIN Statistics]