About me

My team at SWERC 2019. From left to right: my friends Zoé and Gaétan, and me.

Hi ! I am Gabriel, and I am currently a PhD student in computer science at the Université de Bordeaux and the DI of ENS Ulm, under the supervision of Tatiana Starikovskaya and Nathanaël Fijalkow. My research is focused on the theory of algorithms, with an emphasis on search algorithms, for approximate pattern matching and program synthesis. You can find my C.V. here.

Research experience: internships and visits

• Spring 2022: Uniform formula lower bounds for the satisfiability problem, under the supervision of Ryan Williams, at MIT, in Boston (USA).
• September 2021-January 2022: Networks, Percolation and Algorithms: applications to epidemics control, under the supervision of Claire Mathieu and Adrian Vladu, at IRIF, in Paris.
  
• February-July 2021: Kernelization of graph edge modification problems, under the supervision of Nicolas Bousquet and Théo Pierron, at LIRIS, in Lyon.
  
• May-July 2020: Property testing of regular languages and streaming property testing of visibly pushdown languages, under the supervision of Tatiana Starikovskaya, at ENS Ulm, in Paris.
  
• June-July 2019: Dynamic scheduling under memory constraints for shared-memory platforms, under the supervision of Loris Marchal and Yves Robert, at ENS Lyon, in Lyon.
  
• July 2018: Efficient dynamic programming algorithm for the computation of a contrast-invariant signal to noise ratio in imagery, under the supervision of Pierre Weiss, at ITAV, in Toulouse.

Publications:

You can find below a list of my publications in conferences or journals, in reverse chronological order.

Conferences:

1. Towards Stronger Depth Lower Bounds. Gabriel Bathie, Ryan Williams, ITCS'24 2024.
2. Small-Space Algorithms for the Online Language Distance Problem for Palindromes and Squares. Gabriel Bathie, Tomasz Kociumaka, Tatiana Starikovskaya, ISAAC'23 2023.
3. PACE solver description: DreyFVS. Gabriel Bathie, Gaétan Berthe, Yoann Coudert-Osmont, David Desobry, Amadeus Reinald, Mathis Rocton, IPEC'22 2022.
4. Property testing of regular languages with applications to streaming property testing of visibly pushdown languages. Gabriel Bathie, Tatiana Starikovskaya, ICALP'21 2021.
5. (Sub)linear kernels for edge modification problems towards structured graph classes. Gabriel Bathie, Nicolas Bousquet, Théo Pierron, IPEC'21 2021.
6. PACE Solver Description: $\mu$Solver-Heuristic Track. Valentin Bartier, Gabriel Bathie, Nicolas Bousquet, Marc Heinrich, Théo Pierron, Ulysse Prieto, IPEC'21 2021.
7. PACE Solver Description: PaSTEC-PAths, Stars and Twins to Edit Towards Clusters. Valentin Bartier, Gabriel Bathie, Nicolas Bousquet, Marc Heinrich, Théo Pierron, Ulysse Prieto, IPEC'21 2021.
8. Revisiting dynamic {DAG} scheduling under memory constraints for shared-memory platforms. Gabriel Bathie, Loris Marchal, Yves Robert, Samuel Thibault, IPDPS'20 2020.
   Received the Outstanding Paper Award, invited for publication in a special issue of IJNC.

Journals:

1. (Sub)linear Kernels for Edge Modification Problems Toward Structured Graph Classes. Gabriel Bathie, Nicolas Bousquet, Yixin Cao, Yuping Ke, Théo Pierron, Algorithmica, 85(8) (2022), pp. 1--27
2. Dynamic DAG Scheduling Under Memory Constraints for Shared-Memory Platforms. Gabriel Bathie, Loris Marchal, Yves Robert, Samuel Thibault, International Journal of Networking and Computing, 11 (2021), pp. 27--49
3. Contrast invariant SNR and isotonic regressions. Pierre Weiss, Paul Escande, Gabriel Bathie, Yiqiu Dong, International Journal of Computer Vision, 127 (2019), pp. 1144--1161

Misc

Competitive Programming

I enjoy competitive programming, both as a participant (see my Codeforces profile) and as an organizer.
In 2023-2024, I am co-organizing the SWERC in Paris, at Sorbonne Université.

Reading group

During Fall 2019, I am organizing a reading group on Algorithmic Game Theory (based on the book by Nisan et al.). Contact me if you would like to attend it!

Side projects

Coming soon. See my Github profile in the meantime.