2nd Workshop Complexity and Algorithms (CoA 2022)

26-28 septembre 2022, Institut Henri Poincaré (IHP), Paris

Local Information

CoA 2022 will be taking place in amphithéâtre Hermite of IHP, which is located 11 rue Pierre et Marie Curie, Paris (see maps above).

Participants must book their accommodation in Paris themselves.


Registration is free but mandatory: Registration form

Deadline for registration: September 9, 2022. (registration closed)

Invited Speakers
Scientific Program (subject to modifications)

Monday (Sept. 26)

13h45-14h00: Opening and Welcome

  • 14h00-14h50: Invited talk: Marthe Bonamy: Exploring the space of colourings with Kempe changes
  • 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: Discrepancy Minimization via Regularization
  • 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 (on your own)

  • 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 ou Vincent Limouzy: 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: Clément Legrand-Duchesne: Parameterized complexity of untangling knots
  • 10h10-10h30: Riccardo Gozzi: Analog characterization of complexity classes

10h30-11h00: Coffee break

  • 11h00-11h20: Alex Grilo: Quantum learning algorithms imply circuit lower bounds
  • 11h20-11h40: Giannos Stamoulis: Fixed-Parameter Tractability of Maximum Colored Path and Beyond
  • 11h40-12h00: Christophe Paul: A Linear Fixed-Parameter Tractable Algorithm for Connected Pathwidth

12h00-14h00: Lunch (on your own)

  • 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

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. (submission closed)