Full Program
Times in the program are shown in BRT Time (UTC 3).
Tuesday, January 5
BRT TIME  ACTIVITY (place)  

9:00 AM  Getting to know Virtual Chair space  
9:40 AM  Opening (auditorium)  
10:00 AM  Technical session 1 (room B) Chair: Carla Negri Lintzmayer 
Technical session 2 (room A) Chair: Guilherme Oliveira Mota 
10:00 AM  J. R. S. Blair, P. Heggernes, Paloma T. Lima, and D. Lokshtanov On the maximum number of edges in chordal graphs of bounded degree and matching number 
Chen Avin, K. Mondal, and S. Schmid Dynamically Optimal SelfAdjusting SingleSource Tree Networks 
10:20 AM  H. Bodlaender, N. Brettell, M. Johnson, Giacomo Paesani, D. Paulusma, and E. Jan van Leeuwen Steiner Trees for Hereditary Graph Classes 
A. Bonato, Konstantinos Georgiou, C. MacRury, and P. Prałat Probabilistically Faulty Searching on a HalfLine 
10:40 AM  Z. Deniz, S. Nivelle, B. Ries, and David Schindl On some subclasses of split B_{1}EPG graphs 
S. Chaplick, M. M. Halldórsson, Murilo S. de Lima, and T. Tonoyan Query Minimization under Stochastic Uncertainty 
11:00 AM  Ny A. Andriambolamalala and V. Ravelomanana Transmitting Once to Elect a Leader on Wireless Networks 

11:20 AM  Extra Q&A for technical sessions (lobby) / Break  
11:40 AM  Plenary lecture: Nikhil Bansal (auditorium) Chair: Kirk Pruhs 

12:40 PM  Poster session 1 (lobby) / Lunch break  
13:40 PM  Plenary lecture: MariaFlorina Balcan (auditorium) Chair: Gonzalo Navarro 

14:40 PM  Break  
15:00 PM  Technical session 3 (room B) Chair: Carla Negri Lintzmayer 
Technical session 4 (room A) Chair: Yoshiko Wakabayashi 
15:00 PM  G. Barequet and Gil BenShachar On MinimalPerimeter Lattice Animals 
Md Luftar Rahman and T. Watson Tractable Unordered 3CNF Games 
15:20 PM  Due to technical difficulties, this talk was moved to Thursday, at 11h.  Bruno P. Cavalar, M. Kumar, and B. Rossman Monotone Circuit Lower Bounds from Robust Sunflowers 
15:40 PM  R. Daknama, K. Panagiotou, and Simon Reisser Asymptotics for Push on the Complete Graph 
T. Marcilon, N. Martins, and Rudini Sampaio Hardness of variants of the graph coloring game 
16:00 PM  Andrew ReadMcFarland and D. Štefankovič The Hardness of Sampling Connected Subgraphs 

16:20 PM  H. Hàn, M. Kiwi, and Matías PavezSigné Quasirandom words and limits of word sequences 

16:40 PM  Extra Q&A for technical sessions (lobby)  
Wednesday, January 6
BRT TIME  ACTIVITY (place)  

9:00 AM  Socialization  
10:00 AM  Technical session 5 (room B) Chair: Rafael Oliveira 
Technical session 6 (room A) Chair: Sándor Fekete 
10:00 AM  Benjamin Rossman Thresholds in the Lattice of Subspaces of F_{q}^{n} 
E. Arseneva, P. Bose, Pilar Cano, and R. I. Silveira Flips in higher order Delaunay triangulations 
10:20 AM  K. Shimizu and Ryuhei Mori Exponentialtime Quantum Algorithms for Graph Coloring Problems 
Mincheol Kim, S. D. Yoon, and H.K. Ahn Shortest Rectilinear Path Queries to Rectangles in a Rectangular Domain 
10:40 AM  S. Dantchev, Abdul Ghani, and B. Martin SheraliAdams and the binary encoding of combinatorial principles 
Ioannis Mantas, E. Papadopoulou, V. Sacristán, and R. I. Silveira Farthest color Voronoi diagrams: complexity and algorithms 
11:00 AM  Siddhesh Chaubal and A. Gál Tight Bounds on Sensitivity and Block Sensitivity of Some Classes of Transitive Functions 
Daria Pchelina, N. Schabanel, S. Seki, and Y. Ubukata Simple Intrinsic Simulation of Cellular Automata in Oritatami Molecular Folding Model 
11:20 AM  Extra Q&A for technical sessions (lobby) / Break  
11:40 AM  Plenary lecture: Maria Chudnovsky (auditorium) Chair: Celina M. H. de Figueiredo 

12:40 PM  Poster session 2 (lobby) / Lunch break  
13:40 PM  Plenary lecture: Eduardo Sany Laber (auditorium) Chair: Ferdinando Cicalese 

14:40 PM  Break  
15:00 PM  Technical session 7 (room B) Chair: Lehilton Pedrosa 

15:00 PM  Khaled Elbassioni Approximation Algorithms for Costrobust Discrete Minimization Problems Based on their LPRelaxations 

15:20 PM  V. Fagnon, I. Kacem, G. Lucarelli, and Bertand Simon Scheduling on Hybrid Platforms: Improved Approximability Window 

15:40 PM  L. L. C. Pedrosa and Hugo K. K. Rosado A 2approximation for the kprizecollecting Steiner tree problem 

16:00 PM  P. A. Golovach, Paloma T. Lima, and C. Papadopoulos Graph Square Roots of Small Distance from Degree One Graphs 

16:20 PM  J. Clément and Antoine Genitrini Binary Decision Diagrams: from Tree Compaction to Sampling 

16:40 PM  Extra Q&A for technical sessions (lobby)  
Thursday, January 7
BRT TIME  ACTIVITY (place)  

9:00 AM  Socialization  
10:00 AM  Technical session 8 (room B) Chair: Arnaldo Mandel 
Technical session 9 (room A) Chair: Cláudia Linhares Sales 
10:00 AM  Sergey Bereg Computing Balanced Convex Partitions of Lines 
J. Byrka, Mateusz Lewandowski, S. M. Meesum, J. Spoerhase, and S. Uniyal PTAS for Steiner Tree on Map Graphs 
10:20 AM  P. PérezLantero, Carlos Seara, and J. Urrutia Rectilinear convex hull of points in 3D 
R. Duan, H. He, and Tianyi Zhang Nearlinear Time Algorithm for Approximate Minimum Degree Spanning Trees 
10:40 AM  Frank Bauernöppel, A. Maheshwari, and J.R. Sack An Ω(n^{3}) Lower Bound on the Number of Cell Crossings for Weighted Shortest Paths in 3dimensional Polyhedral Structures 
C. G. Fernandes and Carla N. Lintzmayer Leafy Spanning Arborescences in DAGs 
11:00 AM  G. Barequet and Mira Shalah Improved Upper Bounds on the Growth Constants of Polyominoes and Polycubes 
L. L. C. Pedrosa and Greis Y. O. Quesquén Approximating Routing and Connectivity Problems with Multiple Distances 
11:20 AM  Extra Q&A for technical sessions (lobby) / Break  
11:40 AM  Plenary lecture: Bianca Zadrozny (auditorium) Chair: Roberto Imbuzeiro Oliveira 

12:40 PM  Poster session 1 (lobby) / Lunch break  
13:40 PM  Plenary lecture: Alexander Razborov (auditorium) Chair: Marcos Kiwi 

14:40 PM  Break  
15:00 PM  Awards session (auditorium)  
15:30 PM  Business meeting (auditorium)  
Friday, January 8
BRT TIME  ACTIVITY (place)  

9:00 AM  Socialization  
10:00 AM  Technical session 10 (room B) Chair: Martin Dietzfelbinger 
Technical session 11 (room A) Chair: Jayme Luiz Szwarcfiter 
10:00 AM  Ido Nachum and A. Yehudayoff On Symmetry and Initialization for Neural Networks 
Guilherme C. M. Gomes, M. R. Guedes, and V. F. dos Santos Structural Parameterizations for Equitable Coloring 
10:20 AM  Bertie Ancona, A. Bajwa, N. Lynch, and F. MallmannTrenn How to Color a French Flag: Biologically Inspired Algorithms for ScaleInvariant Patterning 
P. A. Golovach, R. Krithika, Abhishek Sahu, S. Saurabh, and M. Zehavi Graph Hamiltonicity Parameterized by Proper Interval Deletion Set 
10:40 AM  Shunsuke Inenaga Suffix Trees, DAWGs and CDAWGs for Forward and Backward Tries 
Sancrey R. Alves, F. Couto, L. Faria, S. Gravier, S. Klein, and U. S. Souza Graph sandwich problem for the property of being wellcovered and partitionable into k independent sets and ℓ cliques 
11:00 AM  T. Kociumaka, G. Navarro, and Nicola Prezza Towards a Definitive Measure of Repetitiveness 
M. Groshaus, A. L. P. Guedes, and Fabricio S. Kolberg On the Helly Subclasses of Interval Bigraphs and Circular Arc Bigraphs 
11:20 AM  Extra Q&A for technical sessions (lobby) / Break  
11:40 AM  Plenary lecture: Luca Trevisan (auditorium) Chair: Marcel Kenji de Carli Silva 

12:40 PM  Poster session 2 (lobby) / Lunch break  
13:40 PM  Plenary lecture: Nicole Immorlica (auditorium) Chair: Cristina G. Fernandes 

14:40 PM  Break  
15:00 PM  Technical session 12 (room B) Chair: Conrado Martínez 
Technical session 13 (room A) Chair: Martin Fürer 
15:00 PM  Miklos Bóna A method to prove the nonrationality of some combinatorial generating functions 
Charles Carlson, A. Kolla, R. Li, N. Mani, B. Sudakov, and L. Trevisan Lower Bounds for MaxCut via Semidefinite Programming 
15:20 PM  Louisa S. Benkner and S. Wagner On the Collection of Fringe Subtrees in Random Binary Trees 
Costin Bădescu and R. O'Donnell Lower Bounds for Testing Complete Positivity and Quantum Separability 
15:40 PM  M. A. Bender, Mayank Goswami, D. Medjedovic, P. Montes, and K. Tsichlas Batched Predecessor and Sorting with SizePriced Information in External Memory 
K. Buchin, D. Kosolobov, Willem Sonke, B. Speckmann, and K. Verbeek Ordered Strip Packing 
16:00 PM  I. Bliznets and Danil Sagunov Maximizing Happiness in Graphs of Bounded CliqueWidth 
Chen Avin, K. Mondal, and S. Schmid Dynamically Optimal SelfAdjusting SingleSource Tree Networks 
16:20 PM  Closing remarks (auditorium)  
16:30 PM  Extra Q&A for technical sessions (lobby)  
Plenaries
Speaker: Nikhil Bansal (CWI and Eindhoven University of Technology)
Title: Discrepancy, Rounding and Approximation
Abstract: 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.
Speaker: MariaFlorina Balcan (Carnegie Mellon University)
Title: Datadriven algorithm design
Abstract: 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).
Speaker: Maria Chudnovsky (Princeton University)
Title: Induced subgraphs and tree decompositions
Abstract: 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.
Speaker: Eduardo Sany Laber (Pontifical Catholic University of Rio de Janeiro)
Title: On the Price of Explainability for some Clustering Problems
Abstract: 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.
Speaker: Bianca Zadrozny (IBM Research Brazil)
Title: Evaluating classifier learning methods under covariate shift and spatial correlation
Abstract: 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.
Speaker: Alexander Razborov (The University of Chicago)
Title: Theons and QuasiRandomness
Abstract: 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
Tons, 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.
Speaker: Luca Trevisan (Bocconi University)
Title: Graph and Hypergraph Sparsification
Abstract: A weighted 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.
Speaker: Nicole Immorlica (Microsoft Research)
Title: Incentivizing Exploration with Selective Data Disclosure
Abstract: 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.
Posters
We organized poster sessions to facilitate and promote attendance.
We especially encouraged students and young researchers to submit their preliminary findings and ongoing work covering all the subjects of LATIN 2020.
In all sessions, the presenters will be available from 9h30 to 10h (BRT time) in the Virtual Chair venue space.
Poster session 1 (Tuesday and Thursday)
TITLE  AUTHORS  PRESENTER  DOWNLOAD 

Coefficients of the solid angle and Ehrhart quasipolynomials (abstract)  Fabrício C. Machado and Sinai Robins  Fabrício C. Machado  
Exact Solutions for AreaOptimal Simple Polygonization Problems (abstract)  Natanael Ramos, Pedro J. de Rezende and Cid C. de Souza  Natanael Ramos  
W[1]Hardness of the kCenter Problem Parameterized by the Skeleton Dimension (abstract)  Johannes Blum  Johannes Blum  
Linial's Conjecture for MatchingSpine Digraphs (abstract)  Jadder B. de S. Cruz, Cândida N. da Silva and Orlando Lee  Jadder B. de S. Cruz  
Exact Algorithms and Heuristics for the Perfect Awareness Problem (abstract)  Felipe de C. Pereira, Pedro J. de Rezende and Cid C. de Souza  Felipe de C. Pereira 
Poster session 2 (Wednesday and Friday)
TITLE  AUTHORS  PRESENTER  DOWNLOAD 

Intersection of longest paths in 4connected graphs (abstract)  Juan Gutiérrez  Juan Gutiérrez  
Valid inequalities for the Integer Knapsack Cover polyhedron with setup constraints (abstract)  Natália S. Rodrigues and Socorro Rangel  Natália S. Rodrigues  
On total chromatic number of circulant graphs (abstract)  Mauro N. Alves Junior and Diana S. Nobrega  Mauro N. Alves Junior  
Maximum acyclic subgraph under conflict constraints on bounded degree graphs (abstract)  Leonardo C. Abreu, Manoel Campêlo and Ana K. Maia  Leonardo C. Abreu  
Chromatic number, orientations and subtrees (abstract)  Tássio Naia  Tássio Naia  
Token Swap in Cographs (abstract)  Caio Tonetti, Vinicius Santos and Sebastián Urrutia  Caio Tonetti 