Chair


Yoshiharu Kohayakawa (Program Commmittee cochair),
Universidade de São Paulo, Brazil
Flávio Keidi Miyazawa (Program Committee cochair),
Universidade Estadual de Campinas, Brazil
Carla Negri Lintzmayer (Organizing Committee cochair),
Universidade Federal do ABC, Brazil
Guilherme Oliveira Mota (Organizing Committee cochair),
Universidade Federal do ABC, Brazil
José Coelho de Pina (Organizing Committee cochair),
Universidade de São Paulo, Brazil
Yoshiko Wakabayashi (Organizing Committee cochair),
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ándezBaca, 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, BarIlan 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


MariaFlorina Balcan
(Carnegie Mellon University), Datadriven algorithm design
Datadriven 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 datadriven
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
noregret 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 previouslychosen 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 QuasiRandomness
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 firstorder theory \(T\); they
generalize all previously considered partial cases, some of them (like
permutons) in a rather nontrivial way.
In the second part we apply this framework to offer a new perspective
on quasirandomness for combinatorial objects more complicated than
ordinary graphs. Our quasirandomness 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,
linearalgebraic, 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]


Papers


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 WellCovered and Partitionable into \(k\) Independent Sets and \(\ell\) Cliques. [Bibtex]
Bertie Ancona, Ayesha Bajwa, Nancy A. Lynch and Frederik MallmannTrenn, How to Color a French Flag  Biologically Inspired Algorithms for ScaleInvariant 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 Selfadjusting SingleSource Tree Networks. [Bibtex]
Costin Badescu and Ryan O'Donnell, Lower Bounds for Testing Complete Positivity and Quantum Separability. [Bibtex]
Gill Barequet and Gil BenShachar, On MinimalPerimeter 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örgRüdiger Sack, An \(\Omega(n^3)\) Lower Bound on the Number of Cell Crossings for Weighted Shortest Paths in 3Dimensional Polyhedral Structures. [Bibtex]
Michael A. Bender, Mayank Goswami, Dzejla Medjedovic, Pablo Montes and Kostas Tsichlas, Batched Predecessor and Sorting with SizePriced 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 CliqueWidth. [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 HalfLine  (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 MaxCut 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, SheraliAdams 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, NearLinear Time Algorithm for Approximate Minimum Degree Spanning Trees. [Bibtex]
Khaled M. Elbassioni, Approximation Algorithms for CostRobust Discrete Minimization Problems Based on Their LPRelaxations. [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 PavezSigné, QuasiRandom 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 HeeKap 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 2Approximation for the \(k\)PrizeCollecting Steiner Tree Problem. [Bibtex]
Pablo PérezLantero, Carlos Seara and Jorge Urrutia, Rectilinear Convex Hull of Points in 3D. [Bibtex]
Md Lutfar Rahman and Thomas Watson, Tractable Unordered 3CNF Games. [Bibtex]
Andrew ReadMcFarland 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, ExponentialTime Quantum Algorithms for Graph Coloring Problems. [Bibtex]


[Top]
[Home]
[All LATIN Papers]


Sponsors



[Top]
[Home]
[All LATIN Sponsors]


Location


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


[Top]
[Home]
[All LATIN Locations]


Photos



[Top]
[Home]
[All LATIN Photos]


Statistics


General: 
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 LatinAmerica 
At least one  11  (22.0%) 
All  7  (14.0%) 
^{* } Authors with n affiliations contributes 1/n to each affiliation.
^{**} Papers with n authors contribute 1/n to each affiliation.
^{* } Authors with n affiliations contributes 1/n to each affiliation.
^{**} Papers with n authors contribute 1/n to each affiliation.
Africa
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, HeeKap;
Kim, Mincheol;
Yoon, Sang Duk;

Europe
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;
MallmannTrenn, 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;

LatinAmerica
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;
PavezSigné, Matías;
PérezLantero, Pablo;

Middle East
USA & Canada
Canada 
Bonato, Anthony;
Bose, Prosenjit;
Cano, Pilar;
Georgiou, Konstantinos;
MacRury, Calum;
Maheshwari, Anil;
Pralat, Pawel;
Rossman, Benjamin;
Sack, JörgRü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;
ReadMcFarland, Andrew;
Shalah, Mira;
Stefankovic, Daniel;
Watson, Thomas;



[Top]
[Home]
[All LATIN Statistics]

