Source author record

Vincent Jugé

Vincent Jugé appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Data Structures and Algorithms math.CO Computational Complexity Computer Science and Game Theory math.GT

Catalog footprint

What is connected

5works

5topics

2close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2022arXiv

Reduction ratio of the IS-algorithm: worst and random cases

We study the IS-algorithm, a well-known linear-time algorithm for computing the suffix array of a word. This algorithm relies on transforming the input word $w$ into another word, called the reduced word of $w$, that will be at least twice shorter; then, the algorithm recursively computes the suffix array of the reduced word. In this article, we study the reduction ratio of the IS-algorithm, i.e., the ratio between the lengths of the input word and the word obtained after reducing $k$ times the input word. We investigate both worst cases, in which we find precise results, and random cases, where we prove some strong convergence phenomena. Finally, we prove that, if the input word is a randomly chosen word of length $n$, we should not expect much more than $\log(\log(n))$ recursive function calls.

preprint2020arXiv

Adaptive Shivers Sort: An Alternative Sorting Algorithm

We present one stable mergesort algorithm, called \Adaptive Shivers Sort, that exploits the existence of monotonic runs for sorting efficiently partially sorted data. We also prove that, although this algorithm is simple to implement, its computational cost, in number of comparisons performed, is optimal up to a small additive linear term.

preprint2016arXiv

Abelian Ramsey Length and Asymptotic Lower Bounds

This technical note aims at evaluating an asymptotic lower bound on abelian Ramsey lengths.

preprint2016arXiv

Dynamic Complexity of Parity Games with Bounded Tree-Width

Dynamic complexity is concerned with updating the output of a problem when the input is slightly changed. We study the dynamic complexity of two-player parity games over graphs of bounded tree-width, where updates may add or delete edges, or change the owner or color of states. We show that this problem is in DynFO (with LOGSPACE precomputation); this is achieved by a reduction to a Dyck-path problem on an acyclic automaton.

preprint2015arXiv

Curve Diagrams, Laminations, and the Geometric Complexity of Braids

Braids can be represented geometrically as curve diagrams. The geometric complexity of a braid is the minimal complexity of a curve diagram representing it. We introduce and study the corresponding notion of geometric generating function. We compute explicitly the geometric generating function for the group of braids on three strands and prove that it is neither rational nor algebraic, nor even holonomic. This result may appear as counterintuitive. Indeed, the standard complexity (due to the Artin presentation of braid groups) is algorithmically harder to compute than the geometric complexity, yet the associated generating function for the group of braids on three strands is rational.