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