Vincent Jugé

Joint work with Ghazal Khalighinejad, Elahe Ghasemi and Helia Yazdanyar
Algorithmica, volume 87, issue 2, pages 242-291
Absract - BibTeX - PDF

ACM Transactions on Algorithms, volume 20, issue 4, pages 31:1–31:55
Absract - BibTeX - PDF

Joint work with Irène Marcovici
RAIRO - Theoretical Informatics and Applications, volume 58, article 10
Abstract - BibTeX - PDF

Joint work with Laurent Bulteau and Stéphane Vialette
Theoretical Computer Science, volume 941, pages 91–103
Abstract - BibTeX - PDF

Joint work with Samy Abbes, Sébastien Gouëzel and Jean Mairesse
Journal of Algebra, volume 525, pages 497–561
Abstract - BibTeX - PDF

International Journal of Algebra and Computation, volume 27, issue 04, pages 61–105
Abstract - BibTeX - PDF

Joint work with Samy Abbes, Sébastien Gouëzel and Jean Mairesse
Journal of Algebra, volume 473, pages 627–666
Abstract - BibTeX - PDF

Journal of Knot Theory and Its Ramifications, volume 24, issue 08
Abstract - BibTeX - PDF

Joint work with David Basin, Felix Klaedtke and Eugen Zălinescu
ACM Transactions on Information and System Security, volume 16, issue 1, ACM Library
Abstract - BibTeX - PDF

Joint work with June Roupin
International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA), LIPIcs volume 302, pages 23:1–23:15
Abstract - BibTeX - PDF - No slides available

Galloping in fast-growth natural merge sorts (2022)

Joint work with Ghazal Khalighinejad and Elahe Ghasemi and
Extended version published in Algorithmica (vol. 87, issue 2, pages 242-291)
International Colloquium on Automata, Languages and Programming (ICALP), LIPIcs volume 229, pages 68:1–68:19
Abstract - BibTeX - PDF - Slides

Reduction ratio of the IS-algorithm: Worst and random cases (2022)

Symposium on Combinatorial Pattern Matching (CPM), LIPIcs volume 223, pages 8:1–8:23
Abstract - BibTeX - PDF - Slides

Permutation pattern matching for doubly partially ordered patterns (2022)

Joint work with Laurent Bulteau, Guillaume Fertin and Stéphane Vialette
Symposium on Combinatorial Pattern Matching (CPM), LIPIcs volume 223, pages 21:1–21:17
Abstract - BibTeX - PDF - No slides available

Finding automatic sequences with few correlations (2022)

Joint work with Irène Marcovici
International Conference on Random and Exhaustive Generation of Combinatorial Structures (GASCom), PuMA volume 30:1, pages 75–81
Extended version published in RAIRO - Theoretical Informatics and Applications (RAIRO-ITA, vol. 58, article 10)
Abstract - BibTeX - PDF - Slides

Uniform generation of infinite concurrent runs: the case of trace monoids (2022)

Joint work with Samy Abbes
International Conference on Random and Exhaustive Generation of Combinatorial Structures (GASCom), PuMA volume 30:1, pages 1–7
Abstract - BibTeX - PDF - Slides - Full version

Adaptive Shivers Sort: An alternative sorting algorithm (2020)

Symposium on Discrete Algorithms (SoDA), ACM-SIAM symposium, pages 1639–1654
Extended version published in ACM Transactions on Algorithms (vol. 20, issue 4, article 31)
Abstract - BibTeX - PDF - Slides - Full version

Timed systems through the lens of logic (2019)

Joint work Sundararaman Akshay, Paul Gastin and Shankara Narayanan Krishna
Logic in Computer Science (LiCS), 34^th annual ACM/IEEE symposium, pages 359–371
Abstract - BibTeX - PDF - No slides available

Finite bisimulations for dynamical systems with overlapping trajectories (2018)

Joint work with Béatrice Bérard and Patricia Bouyer-Decitre
Computer Science in Logic (CSL), LIPIcs volume 119, pages 26:1–26:19
Abstract - BibTeX - PDF - Slides

On the worst-case complexity of TimSort (2018)

Joint work with Nicolas Auger, Cyril Nicaud and Carine Pivoteau
European Symposium on Algorithms (ESA), LIPIcs volume 112, pages 4:1–4:13
Abstract - BibTeX - PDF - Slides - Full version

Unbounded product-form Petri nets (2017)

Joint work with Patricia Bouyer-Decitre and Serge Haddad
International Conference on Concurrency Theory (ConCur), LIPIcs volume 85, pages 31:1–31:16
Abstract - BibTeX - PDF - Slides

Dynamic complexity of the Dyck reachability (2017)

Joint work with Patricia Bouyer-Decitre
Foundations of Software Science and Computation Structures (FoSSaCS), LNCS volume 10203, 2017, pages 265–282, Springer Verlag
Abstract - BibTeX - PDF - Slides

Enforceable security policies revisited (2012)

Joint work with David Basin, Felix Klaedtke and Eugen Zălinescu
Principles of Security and Trust (PoST), LNCS volume 7215, 2012, pages 309–328, Springer Verlag
Extended version published in ACM Transactions on Information and System Security (TISSEC, vol. 16, issue 1)
Abstract - BibTeX - PDF - Slides

Preprints

Counting bi-colored A'Campo forests (2017)

Joint work with Noémie Combe
Available on arXiv
Abstract - BibTeX - PDF

Courcelle's Theorem Made Dynamic (2017)

Joint work with Patricia Bouyer-Decitre and Nicolas Markey
Available on arXiv
Abstract - BibTeX - PDF

Abelian Ramsey length and asymptotic lower bounds (2016)

Available on arXiv
Abstract - BibTeX - PDF

Dynamic complexity of parity games with bounded tree-width (2016)

Joint work with Patricia Bouyer-Decitre and Nicolas Markey
Available on arXiv
Abstract - BibTeX - PDF

Autres

Popularisation (in French)

Olympiades internationales de mathématiques 2006-2021 (2021)

Joint work with Pierre Bornsztein and Thomas Budzinski
Book published in Cassini editions - 368 pages - 32 €

L’algorithme de tri ShiversSort adaptatif (2020)

Bulletin de la Société informatique de France - 1024, volume 15
This article is inspired from the article Adaptive Shivers Sort: An alternative sorting algorithm published in 2020 at the SoDA conference.
PDF

PhD Thesis (2016)

Combinatorics of Braids

Performed at University Paris 7 under the supervision of Jean Mairesse
PDF - Slides

Bachelor Thesis (2009)

Complexity of Decision Problems in Computational Logic

Performed at Rice University under the supervision of Moshe Vardi
PDF - Slides

Presentations (in seminar or informal conferences)

Tris, comparaisons et efficacité (in French)
Sorting presorted data
Growth rates of braid monoids with many generators
Garside normal forms and convergence of random walks in braid groups
Être plus efficace grâce au hasard (in French)
Courcelle's theorem made dynamic
Braids, lattices and Garside families
Counting configurations of monic polynomials (a.k.a. A'Campo bi-colored forests)
The relaxation normal form of braids is regular
Uniform generation of braids
Curve diagrams, laminations, and the geometric complexity of braids
La théorie des tresses expliquée en cinq minutes à un mathématicien en herbe (in French)

Posters

Analysis of TimSort algorithm
Courcelle's theorem made dynamic
Uniform generation of braids

Research

Publications — Journal

Galloping in fast-growth natural merge sorts (2025)

Adaptive Shivers Sort: An alternative sorting algorithm (2024)

Finding automatic sequences with few correlations (2024)

On shuffled-square-free words (2023)

Asymptotic combinatorics of Artin-Tits monoids and of some other monoids (2019)

The relaxation normal form of braids is regular (2017)

Uniform measures on braid monoids and dual braid monoids (2017)

Curve diagrams, laminations, and the geometric complexity of braids (2015)

Enforceable security policies revisited (2013)

Publications — Conference

The alternating normal form in braids and its minimal automaton (2024)