2nd Workshop Complexity and algorithms (CoA 2022) 26-28 septembre 2022, amphithéâtre Hermite, Institut Henri Poincaré (IHP), Paris 5ème Local Information Access and Hotels Call for Presentations All members of GdR IM interested in algorithm design and complexity are invited to submit scientific presentations to CoA 2022. Presentations at CoA 2022 are expected but not limited to contributions based on recent publications to conferences such as STOC, FOCS, SODA, PODC, SPAA, CCC, ICALP, TQC, ESA, DISC, STACS, WG, MFCS, etc., or to any specialized workshops such as WAOA, IPEC, Approx-Random, SIROCCO, etc., or based on recent results susceptible to be submitted to such events. To propose a presentation, please send a title and abstract to Pierre.Fraigniaud@irif.fr, and specify the name of the speaker, as well as the names of the potential co-authors. Submission deadline : July 15, 2022. Invited Speakers Marthe Bonamy (LaBRI) Carola Doerr (LIP6) Sébastien Tavenas (LAMA) Adrian Vladu (IRIF) Preliminary Scientific Program Monday (Sept. 26) 13h45-14h00: Opening and Welcome 14h00-14h50: Invited talk: Marthe Bonamy: Title TBA 14h50-15h10: Dimitrios Thilikos: Killing a Vortex 15h10-15h30: Ugo Giocanti: Twin-Width IV: Ordered Graphs and Matrices 15h30-15h50: Edouard Bonnet: Algorithmic developments using twin-width 15:50-16h10: Cyril Gavoille: Smaller Universal Graphs for Caterpillars and Graphs of Bounded Path-Width 16h10-16h40: Coffee break 16h40-17h00: Hang Zhou: A PTAS for Capacitated Vehicle Routing on Trees 17h00-17h20: Ralf Klasing: Bamboo Garden Trimming Problem 17h20-17h40: Vincent Jugé: Sorting presorted data 17h40-18h00: Pascal Préa: Modules in Robinson Spaces 18h00-20h00: Cocktail (on site) Tuesday (Sept. 27) 09h00-09h50: Invited talk: Adrian Vladu: Title TBA 09h50-10h10: Alantha Newman: Correlated Rounding for Correlation Clustering 10h10-10h30: David Saulpic: Clustering, k-median and k-means Coresets 10h30-11h00: Coffee break 11h00-11h20: George Giakkoupis: Expanders via local edge flips in quasilinear time 11h20-11h40: Louis Esperet: Sketching distances in monotone graph classes 11h40-12h00: Arnaud de Mesmay: Fitting Metrics and Ultrametrics with Minimum Disagreements 12h00-12h20: Simon Apers: Simple graphs are simpler: faster quantum algorithms for spanners, sparsifiers and approximate minimum cut 12h20-14h00: Lunch 14h00-14h50: Invited talk: Carola Doerr: Research at the interface of theory and practice in black-box optimization 14h50-15h10: Chien-Chung Huang: Maximum Weight b-Matchings in Random-Order Streams 15h10-15h30: Garance Gourdel: Streaming Regular Expression Membership and Pattern Matching 15h30-15h50: Caroline Brosse: Polynomial delay algorithm for minimal chordal completions 15h50-16h10: Claire Hilaire: On the proper interval completion problem within some chordal subclasses 16h10-16h40: Coffee break 16h40-17h00: Sergio Rajsbaum: A Combinatorial Topology Approach to Arrow’s Impossibility Theorem 17h00-17h20: Robin Vacus: Early Adapting to Trends: Zealot Consensus using Passive Communication 17h20-17h40: Gabriel Le Bouder: Optimal Space Lower Bound for Deterministic Self-Stabilizing Leader Election Algorithms 17h40-18h00: Michel Raynal: Power and Limit of Prime Numbers to Break Symmetry in Fully Anonymous Shared Memory Systems Wednesday (Sept. 28) 09h00-09h50: Invited talk: Sébastien Tavenas: Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits : An overview 09h50-10h10: Riccardo Gozzi: Analog characterization of complexity classes 10h10-10h30: Alex Grilo: Quantum learning algorithms imply circuit lower bounds 10h30-11h00: Coffee break 11h00-11h20: Giannos Stamoulis: Fixed-Parameter Tractability of Maximum Colored Path and Beyond 11h20-11h40: Clément Legrand-Duchesne: Parameterized complexity of untangling knots 11h40-12h00: Christophe Paul: A Linear Fixed-Parameter Tractable Algorithm for Connected Pathwidth 12h00-14h00: Lunch 14h00-14h20: Spyros Angelopoulos: Searching with hints 14h20-14h40: Arnaud Labourel: Almost-Optimal Deterministic Treasure Hunt in Arbitrary Graphs 14h40-15h00: Niklas Hahn: Delegated Online Search 15h00-15h20: Daniel Szilagyi: Hamiltonian Monte Carlo for efficient Gaussian sampling: long and random steps 15h20-15h40: Martin Krejca: Accelerated Information Dissemination on Networks with Local and Global Edges 15h40-16h00: Final discussions and closing