Olivier Bodini
Olivier Bodini has a total of 33 co-authors. Here are the top co-authors by number of shared publications:
- Antoine Genitrini
Sorbonne Université CNRS LIP6 -UMR 7606
7 shared publications - Nicolas Rolin
Laboratoire d’Informatique de Paris-Nord CNRS UMR 7030 Université Paris-Nord 93430 Villetaneuse, France
4 shared publications Antoine Genitrini
UPMC Univ Paris 06, UMR 7606, LIP6
3 shared publications- Bernhard Gittenberger
Technische Universität Wien
3 shared publications - Frédéric Peschanski
Sorbonne Universite
3 shared publications - Danièle Gardy
David Laboratory, Université de Versailles Saint-Quentin-en-Yvelines, Versailles, France
2 shared publications
Latest Publications
- 18 July 2025
- Published by Springer Nature
- p. 405-417
Optimal Random Bit Complexity in Efficient Sampling of Set Partition-Like Structures
- 18 July 2025
- Published by Springer Nature
- p. 405-417
Optimal Random Bit Complexity in Efficient Sampling of Set Partition-Like Structures
- Open Access
- 8 October 2024
- Published by Association for Computing Machinery (ACM)
- p. 148-157
Do Recommender Systems Promote Local Music? A Reproducibility Study Using Music Streaming Data
- 8 October 2024
- Published by Association for Computing Machinery (ACM)
- p. 148-157
Open AccessDo Recommender Systems Promote Local Music? A Reproducibility Study Using Music Streaming Data
- Open Access
- 22 January 2024
- Published by Ubiquity Press, Ltd. in Transactions of the International Society for Music Information Retrieval
- Vol. 7 (1) , 15-29
Depict or Discern? Fingerprinting Musical Taste from Explicit Preferences
The notion of personal taste in general, and musical taste in particular, is pervasive in the literature on recommender systems, but also in cultural sociology and psychology. However, definitions and measurement methods strongly differ from one study to another. In this paper, we question two different views on taste that can be retrieved from the literature: either something that is distinctive of an individual, or something that essentially captures the extent and diversity of their preferences. Relying upon a dataset that contains the complete list of musical items liked by individual users of a streaming service, as well as streaming logs, we propose two methods to compute fingerprints of their musical taste. The first one explicitly targets a uniqueness property, aiming at selecting items that uniquely identify a user in the crowd. The second approach focuses on a representativeness task that is fundamental in recommendation, i.e. building a summary depiction of the user’s preferences that can be leveraged to propose other items of interest. We demonstrate that the two methods lead to conflicting solutions, hence highlighting the need to precisely acknowledge which point of view applies when addressing a computational question related to taste. We also raise the question of users’ identifiability through their online activity on music streaming platforms, and beyond.
- 22 January 2024
- Published by Ubiquity Press, Ltd. in Transactions of the International Society for Music Information Retrieval
- Vol. 7 (1) , 15-29
Open AccessDepict or Discern? Fingerprinting Musical Taste from Explicit Preferences
The notion of personal taste in general, and musical taste in particular, is pervasive in the literature on recommender systems, but also in cultural sociology and psychology. However, definitions and measurement methods strongly differ from one study to another. In this paper, we question two different views on taste that can be retrieved from the literature: either something that is distinctive of an individual, or something that essentially captures the extent and diversity of their preferences. Relying upon a dataset that contains the complete list of musical items liked by individual users of a streaming service, as well as streaming logs, we propose two methods to compute fingerprints of their musical taste. The first one explicitly targets a uniqueness property, aiming at selecting items that uniquely identify a user in the crowd. The second approach focuses on a representativeness task that is fundamental in recommendation, i.e. building a summary depiction of the user’s preferences that can be leveraged to propose other items of interest. We demonstrate that the two methods lead to conflicting solutions, hence highlighting the need to precisely acknowledge which point of view applies when addressing a computational question related to taste. We also raise the question of users’ identifiability through their online activity on music streaming platforms, and beyond.
- 29 October 2022
- Published by Springer Nature
- p. 493-509
A Combinatorial Link Between Labelled Graphs and Increasingly Labelled Schröder Trees
- 29 October 2022
- Published by Springer Nature
- p. 493-509
A Combinatorial Link Between Labelled Graphs and Increasingly Labelled Schröder Trees
- Open Access
- 1 June 2022
- Published by Walter de Gruyter GmbH in Pure Mathematics and Applications
- Vol. 30 (1) , 45-55
Sampling β-normal linear λ-terms
Leveraging our recent work on the enumeration of β-redices in closed linear λ-terms, we present an algorithm for sampling β-normal closed linear λ-terms and their corresponding maps. Such terms correspond to proofs of tautologies in implicational linear logic and their generation is of interest in various domains, including the testing of linear logic theorem provers.
- 1 June 2022
- Published by Walter de Gruyter GmbH in Pure Mathematics and Applications
- Vol. 30 (1) , 45-55
Open AccessSampling β-normal linear λ-terms
Leveraging our recent work on the enumeration of β-redices in closed linear λ-terms, we present an algorithm for sampling β-normal closed linear λ-terms and their corresponding maps. Such terms correspond to proofs of tautologies in implicational linear logic and their generation is of interest in various domains, including the testing of linear logic theorem provers.
- Open Access
Tuning as convex optimisation: a polynomial tuner for multi-parametric combinatorial samplers
Combinatorial samplers are algorithmic schemes devised for the approximate- and exact-size generation of large random combinatorial structures, such as context-free words, various tree-like data structures, maps, tilings, RNA molecules. They can be adapted to combinatorial specifications with additional parameters, allowing for a more flexible control over the output profile of parametrised combinatorial patterns. One can control, for instance, the number of leaves, profile of node degrees in trees or the number of certain sub-patterns in generated strings. However, such a flexible control requires an additional and nontrivial tuning procedure. Using techniques of convex optimisation, we present an efficient tuning algorithm for multi-parametric combinatorial specifications. Our algorithm works in polynomial time in the system description length, the number of tuning parameters, the number of combinatorial classes in the specification, and the logarithm of the total target size. We demonstrate the effectiveness of our method on a series of practical examples, including rational, algebraic, and so-called P\'olya specifications. We show how our method can be adapted to a broad range of less typical combinatorial constructions, including symmetric polynomials, labelled sets and cycles with cardinality lower bounds, simple increasing trees or substitutions. Finally, we discuss some practical aspects of our prototype tuner implementation and provide its benchmark results.
Open AccessTuning as convex optimisation: a polynomial tuner for multi-parametric combinatorial samplers
Combinatorial samplers are algorithmic schemes devised for the approximate- and exact-size generation of large random combinatorial structures, such as context-free words, various tree-like data structures, maps, tilings, RNA molecules. They can be adapted to combinatorial specifications with additional parameters, allowing for a more flexible control over the output profile of parametrised combinatorial patterns. One can control, for instance, the number of leaves, profile of node degrees in trees or the number of certain sub-patterns in generated strings. However, such a flexible control requires an additional and nontrivial tuning procedure. Using techniques of convex optimisation, we present an efficient tuning algorithm for multi-parametric combinatorial specifications. Our algorithm works in polynomial time in the system description length, the number of tuning parameters, the number of combinatorial classes in the specification, and the logarithm of the total target size. We demonstrate the effectiveness of our method on a series of practical examples, including rational, algebraic, and so-called P\'olya specifications. We show how our method can be adapted to a broad range of less typical combinatorial constructions, including symmetric polynomials, labelled sets and cycles with cardinality lower bounds, simple increasing trees or substitutions. Finally, we discuss some practical aspects of our prototype tuner implementation and provide its benchmark results.
- Open Access
The Combinatorics of Barrier Synchronization
In this paper we study the notion of synchronization from the point of view of combinatorics. As a first step, we address the quantitative problem of counting the number of executions of simple processes interacting with synchronization barriers. We elaborate a systematic decomposition of processes that produces a symbolic integral formula to solve the problem. Based on this procedure, we develop a generic algorithm to generate process executions uniformly at random. For some interesting sub-classes of processes we propose very efficient counting and random sampling algorithms. All these algorithms have one important characteristic in common: they work on the control graph of processes and thus do not require the explicit construction of the state-space.
Open AccessThe Combinatorics of Barrier Synchronization
In this paper we study the notion of synchronization from the point of view of combinatorics. As a first step, we address the quantitative problem of counting the number of executions of simple processes interacting with synchronization barriers. We elaborate a systematic decomposition of processes that produces a symbolic integral formula to solve the problem. Based on this procedure, we develop a generic algorithm to generate process executions uniformly at random. For some interesting sub-classes of processes we propose very efficient counting and random sampling algorithms. All these algorithms have one important characteristic in common: they work on the control graph of processes and thus do not require the explicit construction of the state-space.
- Open Access
Beyond series-parallel concurrent systems: the case of arch processes
In this paper we focus on concurrent processes built on synchronization by means of futures. This concept is an abstraction for processes based on a main execution thread but allowing to delay some computations. The structure of a general concurrent process with futures is more or less a directed acyclic graph. Since the quantitative study of such increasingly labeled graphs (directly related to processes) seems out of reach, we restrict ourselves to the study of arch processes, a simplistic model of processes with futures. They are based on two parameters related to their sizes and their numbers of arches. The increasingly labeled structures seems not to be specifiable in the sense of Analytic Combinatorics, but we manage to derive a recurrence equation for the enumeration. For this model we first exhibit an exact and an asymptotic formula for the number of runs of a given process. The second main contribution is composed of an uniform random sampler algorithm and an unranking one that allow efficient generation and exhaustive enumeration of the runs of a given arch process.
Open AccessBeyond series-parallel concurrent systems: the case of arch processes
In this paper we focus on concurrent processes built on synchronization by means of futures. This concept is an abstraction for processes based on a main execution thread but allowing to delay some computations. The structure of a general concurrent process with futures is more or less a directed acyclic graph. Since the quantitative study of such increasingly labeled graphs (directly related to processes) seems out of reach, we restrict ourselves to the study of arch processes, a simplistic model of processes with futures. They are based on two parameters related to their sizes and their numbers of arches. The increasingly labeled structures seems not to be specifiable in the sense of Analytic Combinatorics, but we manage to derive a recurrence equation for the enumeration. For this model we first exhibit an exact and an asymptotic formula for the number of runs of a given process. The second main contribution is composed of an uniform random sampler algorithm and an unranking one that allow efficient generation and exhaustive enumeration of the runs of a given arch process.
- Open Access
- 13 February 2018
- Published by Springer Nature in Annals of Combinatorics
- Vol. 22 (1) , 45-91
On the Number of Unary-Binary Tree-Like Structures with Restrictions on the Unary Height
- 13 February 2018
- Published by Springer Nature in Annals of Combinatorics
- Vol. 22 (1) , 45-91
Open AccessOn the Number of Unary-Binary Tree-Like Structures with Restrictions on the Unary Height
- Open Access
On Uniquely Closable and Uniquely Typable Skeletons of Lambda Terms
Uniquely closable skeletons of lambda terms are Motzkin-trees that predetermine the unique closed lambda term that can be obtained by labeling their leaves with de Bruijn indices. Likewise, uniquely typable skeletons of closed lambda terms predetermine the unique simply-typed lambda term that can be obtained by labeling their leaves with de Bruijn indices. We derive, through a sequence of logic program transformations, efficient code for their combinatorial generation and study their statistical properties. As a result, we obtain context-free grammars describing closable and uniquely closable skeletons of lambda terms, opening the door for their in-depth study with tools from analytic combinatorics. Our empirical study of the more difficult case of (uniquely) typable terms reveals some interesting open problems about their density and asymptotic behavior. As a connection between the two classes of terms, we also show that uniquely typable closed lambda term skeletons of size $3n+1$ are in a bijection with binary trees of size $n$.Open AccessOn Uniquely Closable and Uniquely Typable Skeletons of Lambda Terms
Uniquely closable skeletons of lambda terms are Motzkin-trees that predetermine the unique closed lambda term that can be obtained by labeling their leaves with de Bruijn indices. Likewise, uniquely typable skeletons of closed lambda terms predetermine the unique simply-typed lambda term that can be obtained by labeling their leaves with de Bruijn indices. We derive, through a sequence of logic program transformations, efficient code for their combinatorial generation and study their statistical properties. As a result, we obtain context-free grammars describing closable and uniquely closable skeletons of lambda terms, opening the door for their in-depth study with tools from analytic combinatorics. Our empirical study of the more difficult case of (uniquely) typable terms reveals some interesting open problems about their density and asymptotic behavior. As a connection between the two classes of terms, we also show that uniquely typable closed lambda term skeletons of size $3n+1$ are in a bijection with binary trees of size $n$.