Full Program

Times in the program are shown in BRT Time (UTC -3).

Tuesday, January 5

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 Self-Adjusting Single-Source 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 Half-Line
10:40 AM Z. Deniz, S. Nivelle, B. Ries, and David Schindl
On some subclasses of split B1-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: Maria-Florina 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 Ben-Shachar
On Minimal-Perimeter Lattice Animals
Md Luftar Rahman and T. Watson
Tractable Unordered 3-CNF 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 Read-McFarland and D. Štefankovič
The Hardness of Sampling Connected Subgraphs
16:20 PM H. Hàn, M. Kiwi, and Matías Pavez-Signé
Quasi-random words and limits of word sequences
16:40 PM Extra Q&A for technical sessions (lobby)

Wednesday, January 6

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 Fqn
E. Arseneva, P. Bose, Pilar Cano, and R. I. Silveira
Flips in higher order Delaunay triangulations
10:20 AM K. Shimizu and Ryuhei Mori
Exponential-time 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
Sherali-Adams 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 Cost-robust Discrete Minimization Problems Based on their LP-Relaxations
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 2-approximation for the k-prize-collecting 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

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érez-Lantero, Carlos Seara, and J. Urrutia
Rectilinear convex hull of points in 3D
R. Duan, H. He, and Tianyi Zhang
Near-linear Time Algorithm for Approximate Minimum Degree Spanning Trees
10:40 AM Frank Bauernöppel, A. Maheshwari, and J.-R. Sack
An Ω(n3) Lower Bound on the Number of Cell Crossings for Weighted Shortest Paths in 3-dimensional 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

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. Mallmann-Trenn
How to Color a French Flag: Biologically Inspired Algorithms for Scale-Invariant 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 well-covered 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 Max-Cut 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 Size-Priced 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 Clique-Width
Chen Avin, K. Mondal, and S. Schmid
Dynamically Optimal Self-Adjusting Single-Source Tree Networks
16:20 PM Closing remarks (auditorium)
16:30 PM Extra Q&A for technical sessions (lobby)


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: Maria-Florina Balcan (Carnegie Mellon University)

Title: Data-driven algorithm design

Abstract: 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).

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 Quasi-Randomness

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 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.

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, 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.

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 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.


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)

Coefficients of the solid angle and Ehrhart quasi-polynomials (abstract) Fabrício C. Machado and Sinai Robins Fabrício C. Machado
Exact Solutions for Area-Optimal Simple Polygonization Problems (abstract) Natanael Ramos, Pedro J. de Rezende and Cid C. de Souza Natanael Ramos
W[1]-Hardness of the k-Center Problem Parameterized by the Skeleton Dimension (abstract) Johannes Blum Johannes Blum
Linial's Conjecture for Matching-Spine 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)

Intersection of longest paths in 4-connected 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