3rd Workshop Complexity and Algorithms (CoA 2023) 18-20 septembre 2023, LIP6 (LIP6), Paris Local Information CoA 2023 will be taking place on the Jussieu campus of Sorbonne Université in Paris. We meet in room 25-26/105, to be accessed from 'tower' 26, first to the left after entering the Jussieu campus coming from Jussieu metro station. (see map above). Videostreaming will be done in this Zoom room. Participants must book their accommodation in Paris themselves. Registration Registration is free but mandatory. Name Tag Please bring your own name tag. (Use/recycle one from a recent conference/workshop!) Invited Speakers Sophie Huiberts (LIMOS) Francois Pirot (LISN) Bertrand Simon (IN2P3) Hang Zhou (Ecole Polytechnique) Scientific Program (subject to modifications) Monday (Sept. 18) 13h45-14h00: Opening and Welcome 14h00-14h50: Invited talk: Sophie Huiberts: Smoothed Analysis of the Simplex Method 15h00-15h20: Louis Esperet: Optimal Adjacency Labels for Subgraphs of Cartesian Products 15h20-15h40: Édouard Bonnet: Small but Unwieldy–Lower Bounds on Labeling Schemes and Universal Graphs 15h40-16h20: Coffee break 16h20-16h40: George Giakkoupis: Distributed Self-Stabilizing MIS with Few States and Weak Communication 16h40-16h50: Mikael Rabie: Making Self-Stabilizing Algorithms for any Locally Greedy Problem 16h50-17h00: Arthur da Cunha: Revisiting the Random Subset Sum Problem 17h00-17h20: Arthur Braida: Quantum Annealing Tuesday (Sept. 19) 09h00-09h50: Invited talk: Bertrand Simon: Learning-augmented Online Algorithms & Paging 09h50-10h10: Simon Mauras: Constant Approximation for Private Interdependent Valuations 10h10-10h30: Oijid Nacim: Avoider-Enforcer is PSPACE-complete 10h30-11h00: Coffee break 11h00-11h20: Arnaud de Mesmay: A PTAS for $\ell_0$-Low Rank Approximation: Solving Dense CSPs over Reals 11h20-11h40: Laurent Feuilloley: Compact Distributed Certification of Graph Properties 11h40-12h00: Romain Bourneuf: PPP-Completeness and Extremal Combinatorics 12h00-14h00: Lunch (on your own) 14h00-14h50: Invited talk: Francois Pirot: The Freezing Threshold for Uniformly Random Colourings of Sparse Graphs 14h50-15h10: Felix Klingelhoefer: Coloring Tournaments with Few Colors 15h10-15h30: Lucas Picasarri Arrieta: Digraph Re-dicoloring 15h30-15h50: Thomas Suzan: Reconfiguration of Digraph Homomorphisms 15h50-16h30: Coffee break 16h30-16h50: Spyros Angelopoulos: Rényi-Ulam Games and Online Computation with Imperfect Advice 16h50-17h10: Martin Krejca: Analysis of the Survival Time of the SIRS Process via Expansion 17h10-17h30: Julien Duron: Stretch-width Wednesday (Sept. 20) 09h00-09h50: Invited talk: Hang Zhou: Capacitated Vehicle Routing 09h50-10h10: David Saulpic: Quadtree for $k$-means in Euclidean Space 10h10-10h30: Raul Wayne Teixeira Lopes: New Menger-like dualities in digraphs and applications to half-integral linkages 10h30-11h00: Coffee break 11h00-11h20: Garance Gourdel: Optimal Runs Computation over General Alphabets 11h20-11h30: Colin Geniet: Factorization of Pattern-Free Permutations 11h30-11h50: Michel Habib: Pattern Detection in Ordered Graphs 12h00-12h45: Final discussions and wrap-up