LATIN 2024
March 18 – 22, 2024 in Puerto Varas/Chile
LATIN 2024 program
Monday, March 18
|
8:00
|
Registration
|
|
9:00
|
Invited talk (session chair: Andreas Wiese) Pierre Fraigniaud. Distributed Proofs with Small Certificates |
| 10:00 | Coffee break |
| 10:30 | Session 1: Algorithms and Data Structures (session chair: Cristina Fernandes) |
|
10:30 |
Emilio Di Giacomo, Henry Förster, Daria Kokhovich, Tamara Mchedlidze, Fabrizio Montecchiani, Antonios Symvonis and Anaïs Villedieu. On 1-bend Upward Point-set Embeddings of $st$-digraphs |
| 10:52 | Samuel Silva and Uéverton Souza. Decoding tree decompositions from permutations |
|
11:15 |
Duncan Adamson, Pawel Gawrychowski and Florin Manea. Enumerating m-Length Paths in Directed Graphs with Constant Delay |
|
11:38 |
Diego Maldonado, Pedro Montealegre and Martín Ríos-Wilson. The Hardness of Local Certification of Finite-State Dynamics |
| 12:00 | Lunch break |
| 14:00 | Session 2: Approximation and Online Algorithms (session chair: Andrea Richa) |
|
14:00 |
Younan Gao and Meng He. On Approximate Colored Path Counting |
| 14:22 | Sushmita Gupta, Sounak Modak, Saket Saurabh and Sanjay Seetharaman. Quick-Sort Style Approximation Algorithms For Generalizations of Feedback Vertex Set in Tournaments |
|
14:45 |
Matej Lieskovský. Better Algorithms for Online Bin Stretching via Computer Search |
|
15:08 |
Sarita de Berg, Nathan van Beusekom, Max van Mulken, Kevin Verbeek and Jules Wulms. Competitive Searching over Terrains |
| 15:30 | Coffee break |
| 16:00 | Session 3: Computational Geometry (session chair: Jose Soto) |
| 16:00 | William Evans and Seyed Ali Tabatabaee. Minimizing the Size of the Uncertainty Regions for Centers of Moving Entities |
|
16:22 |
Omrit Filtser, Erik Krohn, Bengt J. Nilsson, Christian Rieck and Christiane Schmidt. Guarding Polyominoes under k-Hop Visibility |
|
16:45 |
Taehoon Ahn, Chaeyoon Chung, Hee-Kap Ahn, Sang Won Bae, Otfried Cheong and Sang Duk Yoon. Minimum-Width Double-Slabs and Widest Empty Slabs in High Dimensions |
|
17:08 |
Henry Förster, Philipp Kindermann, Till Miltzow, Irene Parada, Soeren Terziadis and Birgit Vogtenhuber. Geometric Thickness of Multigraphs is ER-Complete |
| 17:30 | Reception |
Tuesday, March 19
|
9:00
|
Invited talk (session chair: Andreas Wiese) Penny Haxell. Independent transversals, topology and resource allocation |
| 10:00 | Coffee break |
| 10:30 | Session 4: Combinatorics and Graph Theory (session chair: Jose Soto) |
| 10:30 | Yixin Cao, Haowei Chen and Shenghua Wang. Self-complementary (Pseudo-)Split Graphs |
| 10:52 | Christian Ortlieb. Schnyder woods and long induced paths in 3-connected planar graphs |
| 11:15 | Pavoll Hell, Arash Rafiey and Akbar Rafiey. Bi-arc Digraphs: Recognition Algorithm and Applications |
|
11:38 |
Matheus Adauto, Viktoriya Bardenova, Mariana Cruz, Celina Figueiredo, Glenn Hulbert and Diana Sasaki. Pebbling in Kneser graphs |
| 12:00 | Lunch break |
| 14:00 | Session 5: Algorithms and Data Structures (session chair: Andrea Richa) |
|
14:00 |
Gonzalo Navarro and Cristian Urbina. Iterated Straight-Line Programs |
|
14:22 |
Ankush Acharyya, Vahideh Keikha, Maria Saumell and Rodrigo I. Silveira. Computing largest minimum color-spanning intervals of imprecise points |
|
14:45 |
Dhanyamol Antony, L. Sunil Chandran, Ankit Gayen, Shirish Gosavi and Dalu Jacob. Total Domination, Separated-Cluster, CD-Coloring: Algorithms and Hardness |
|
15:08 |
Yuan Friedrich Qiu and Aaron Williams. Generating Signed Permutations by Twisting Two-Sided Ribbons |
| 15:30 | Coffee break |
|
16:00
|
Session 6: Parametrized algorithms and complexity theory (session chair: Pedro Montalegre) |
| 16:00 | Pallavi Jain and Manveer Singh Rathore. Sparsity in Covering Solutions |
|
16:22 |
Uéverton Souza, Luis Cunha, Loana Nogueira, Fabio Protti and Gabriel Duarte. Induced Tree Covering and the Generalized Yutsis Property |
|
16:45 17:08 |
Palash Dey, Sudeshna Kolay and Sipra Singh. Knapsack: Connectedness, Path, and Shortest-Path Christoph Grüne. The Complexity Classes of Hamming Distance Recoverable Robust Problems |
| 17:30 | Break |
|
18:00 18:00 18:30
|
Session 7: Alejandro López-Ortiz Best paper award and Imre Simon Test-of-Time award (session chair: Andreas Wiese) Amir Abboud, Yarin Shechter, and Nick Fischer. Faster Combinatorial k-Clique Algorithms Pierre Fraigniaud, Leszek Gasieniec, Dariusz R. Kowalski and Andrzej Pelc. Collective Tree Exploration
|
| 19:00 | Business meeting |
Wednesday, March 20
|
9:00
|
Invited talk (session chair: Jose Soto) Pablo Barceló. The Expressive Power of Graph Neural Networks |
| 10:00 | Coffee break |
| 10:30 | Session 8: Algorithms and Data Structures (session chair: Victor Verdugo) |
|
10:30 |
Zsuzsanna Liptak and Luca Parmigiani. A BWT-based algorithm for random de Bruijn sequence construction |
| 10:52 | Adrián Goga, Travis Gagie, Gonzalo Navarro and Artur Jeż. Space-efficient conversions from SLPs |
|
11:15 |
Lorraine Ayad, Grigorios Loukides, Solon Pissis and Hilde Verbeek. Sparse Suffix and LCP Array: Simple, Direct, Small, and Fast |
|
11:38 |
Adrián Goga, Andrej Baláž, Travis Gagie, Gonzalo Navarro, Alessia Petescia, Simon Heumos and Jouni Sirén. Wheeler maps |
| 12:00 | Lunch break |
| 13:30 | Excursion |
| Visit to the Vicente Pérez Rosales National Park | |
| 19:00 | Conference dinner |
Thursday, March 21
Please note that there were some recent changes in the program.
|
9:00 |
Session 9: Parametrized algorithms (session chair: Pedro Montalegre) |
| Soumen Mandal, Pranabendu Misra, Ashutosh Rai and Saket Saurabh. Parameterized Approximation Algorithms for Weighted Vertex Cover | |
| Shubhada Aute and Fahad Panolan. Parameterized Algorithms for Minimum Sum Vertex Cover |
|
| Akanksha Agrawal, Satyabrata Jana and Abhishek Sahu. A Polynomial Kernel for Proper Helly Circular-arc Vertex Deletion |
|
| Pallavi Jain, Fahad Panolan, Lawqueen Kanesh, Souvik Saha, Abhishek Sahu, Saket Saurabh and Anannya Upasana. Max-SAT with Cardinality Constraint Parameterized by the Number of Clauses |
|
| 10:30 | Coffee break |
|
11:00
|
Invited talk (session chair: Andreas Wiese) Eunjung Kim. Flow-augmentation technique and its applications |
| 12:00 | Lunch break |
| 14:00 | Session 10: Combinatorics and Graph Theory (session chair: Waldo Galvez) |
|
14:00 |
Duncan Adamson, Nathan Flaherty, Igor Potapov and Paul Spirakis. Structural and combinatorial properties of 2-swap word permutation graphs |
| 14:22 | Marcelo Garlet Milani. Directed Ear Anonymity |
|
14:45 |
Cristina G. Fernandes, Guilherme Oliveira Mota and Nicolás Sanhueza-Matamala. Separating path systems in complete graphs |
| 15:08 | Alexander Kozachinskiy. Infinite separation between general and chromatic memory |
| 15:30 | Coffee break |
|
16:00
|
Session 11: Automata Theory and Formal Languages (session chair: Victor Verdugo) |
| 16:00 | Volker Turau. Counting Fixed Points and Pure 2-Cycles of Tree Cellular Automata |
|
16:22 |
Thomas Brihaye, Sophie Pinchinat and Alexandre Terefenko. Semantics of Attack-Defense Trees for Dynamic Countermeasures and a New Hierarchy of Star-free Languages |
|
16:45 |
Isabel Donoso, Eric Goles, Martín Ríos-Wilson and Sylvain Sené. Asymptotic (a)synchronism sensitivity and complexity of elementary cellular automata |
Friday, March 22
|
9:00
|
Invited talk (session chair: Jose Soto) Jon Kleinberg. Revisiting the Behavioral Foundations of User Modeling Algorithms |
| 10:00 | Coffee break |
| 10:30 | Session 12: Game theory and fairness (session chair: Waldo Galvez) |
| 10:30 | Palash Dey and Arnab Maiti. On Binary Networked Public Goods Game with Altruism |
| 10:52 | Minh Hieu Nguyen, Mourad Baiou, Viet Hung Nguyen and Thi Quynh Trang Vo. Proportional Fairness for Combinatorial Optimization |
|
11:15 |
Matthias Hoffjan, Anna Maria Kerkmann and Jörg Rothe. Core Stability in Altruistic Coalition Formation Games |
|
11:38 |
Kristóf Bérczi, Lydia Mirabel Mendoza Cadena and Kitti Varga. Newton-type algorithms for inverse optimization: weighted span objective |
| 12:00 | Closing |
© LATIN 2024