Publications

Dieu parle tantôt d'une manière, tantôt d'une autre.
Archive : [v1.pdf]

On n'est pas obligé d'attendre la toute fin pour ouvrir les yeux et régler certains problèmes.
Archive : [v1.pdf]

La franchise est le langage de Dieu.
Archive : [v1.pdf]

Ce n'est pas parce que certains sujets sont tabous ou lourds de tensions, et de revendications, qu'il ne faut pas les aborder.
Archive : [v1.pdf] , [v2.pdf]

Bien heureusement, nous ne sommes pas seuls sur la ligne de front :).
Archive : [v1.pdf]

Le pouvoir de la prière est à la mesure de Dieu, pas à la nôtre.
Archive : [v1.pdf]

Dieu nous montre le chemin.
Archive : [v1.pdf]

Dieu nous protège.
Archive : [v1.pdf]

Dieu nous donne des choses simples à retenir.
Archive : [v1.pdf]

Dieu est Dieu.
Archive : [v1.pdf] , [v2.pdf]

Soyons au clair avec Dieu, avec nous-même et avec les autres :).
Archive : [v1.pdf] , [v2.pdf] , [v3.pdf]

Dieu nous oblige.
Archive : [v1.pdf]

L'exemple instructif et attachant de Saint-Thomas.
Archive : [v1.pdf] , [v2.pdf]

Quelques pensées qui font ma joie sur les solutions préparées d'avance par Dieu.
Archive : [v1.pdf] , [v2.pdf] , [v3.pdf]

Dans cet article, je vais parler un peu d’anges et de démons, mais surtout de notre attitude vis à vis de tout cela. Il y a quelques points assez durs ou perturbants, donc je recommande de le lire avec un esprit reposé, pas juste avant la messe et pas juste avant d’aller se coucher, surtout si c’est un soir de semaine avec la fatigue de la journée.
Archive : [v1.pdf] , [v2.pdf] , [v3.pdf]

Dans cet article, je présente ce que j’ai compris des dernières minutes du Christ en croix. Je ne sais pas s’il y a quoi que ce soit de nouveau dans ce que je vais écrire, car j’ai été nourri des homélies liées à ce moment de la vie du Christ. De plus, les théologiens ont beaucoup écrit sur le sujet. Ce qui est sûr, c’est que ce message est important.
Archive : [v1.pdf]

Vouer un culte de haine à quelqu’un ne vaut pas beaucoup mieux qu’une adoration à un faux dieu.
Archive : [v1.pdf]

Un peu d'ordre dans sa vie ne fait jamais de mal.
Archive : [v1.pdf] , [v2.pdf]

La meilleure Défense c'est la Grâce de Dieu. C'est dur à admettre dans l'épreuve, mais il faut regarder ce qu'on gagne ou perd pour la vie éternelle, et pas seulement le court terme de notre vie.
Archive : [v1.pdf] , [v2.pdf] , [v3.pdf] , [v4.pdf]

La Bible est polysémique et poly-contextuelle
Archive : [v1.pdf] , [v2.pdf] , [v3.pdf] , [v4.pdf]

À force de regarder uniquement du côté des paradoxes et du relativisme, on en oublie les bases qui sont saines.
Archive : [v1.pdf] , [v2.pdf] , [v3.pdf] , [v4.pdf]

Tous les humains ont un super-pouvoir et en plus il est bien connu.
Archive : [v1.pdf] , [v2.pdf] , [v3.pdf] , [v4.pdf] , [v5.pdf]

Pourquoi la cryptographie c'est dur ? Car tu ne sais jamais si tu as pensé à tout.
Archive : [fr_v1.pdf] , [en_v1.pdf] , [fr_v2.pdf] , [en_v2.pdf] , [en_v3.pdf]

Dans cet article, nous étudions la largeur de jumeaux et la largeur de fusion à la lumière du principe de première différence.
Archive : [fr_v1.pdf] , [en_v1.pdf] , [fr_v2.pdf] , [en_v2.pdf]

Dans cet article, nous montrons qu’il y a une infinité de types de largeur arborescente questionnable non-bijective, dont 6 types principaux. L’étude de ces types vient d’un exemple de décomposition arborescente questionnable de degré non-borné et de profondeur 2 pour toute structure binaire. Nous hiérarchisons ces types et tissons des liens avec la largeur arborescente questionnable bijective.
Archive : [fr_v1.pdf] , [en_v1.pdf] , [fr_v2.pdf] , [en_v2.pdf] , [fr_v3.pdf] , [en_v3.pdf]

Dans cette note, nous pointons une erreur logique dans van Rooij et al. (2013) et nous montrons comment la corriger.
Archive : [fr_v1.pdf] , [en_v1.pdf]

Dans cette note, nous montrons que les classes de graphes de largeur arborescente bornée ont une largeur arborescente questionnable bijective équilibrée bornée.
Archive : [fr_v1.pdf] , [en_v1.pdf]

Dans cet article, je propose d’aborder le problème de la factorisation des nombres entiers comme un problème de comptage, puis de factoriser ou plus généralement d’avoir un modèle de calcul à base de graphes et d’opérations matricielles non triviales. Enfin, je présente une heuristique de factorisation amusante nommée Fibolous. Attention : expression libre et style non-académique sur la forme.
Archive : [v1.pdf] , [v2.pdf] , [v3.pdf]

En première année d’algorithmie, on découvre des exemples de schémas « Diviser pour régner » où une bonne division de l’instance du problème algorithmique étudié fournit aussi un algorithme de résolution efficace. Dans cet article, je présente un moyen de diviser efficacement tous les graphes de degré borné. Ce qui amène au fait intéressant que si P ≠ NP, alors « Diviser n’est pas régner. ».
Archive : [v1.pdf] , [v2.pdf] , [v3.pdf] , [v4.pdf] , [v4.php] , [v5.pdf] , [v5.php] , [v6.pdf] , [v6.php]

Dans cet article, nous étudions des largeurs/décompositions de structures binaires variées à la lumière du principe de première différence. Nous montrons l'égalité de la largeur modulaire et de la largeur questionnable, bien que les représentations questionnables soient plus primitives/grossières que les décompositions modulaires/de clan. En utilisant le principe de première différence, nous montrons que les décompositions de clique des structures binaires ont un équivalent séquentiel, que nous appelons représentation questionnable de clique. Enfin, nous donnons des remarques sur la vraie validité de la largeur de rang des structures binaires.
Archive : [v1.pdf] , [v2.pdf] , [v3.pdf] , [v4.pdf] , [v5.pdf]

Dans cet article, nous caractérisons les ordres qui sont des sous-ordres induits par niveau, toutes les fois où ils sont des sous-ordres induits d'un sur-ordre. Nous caractérisons aussi les ordres qui sont des sous-ordres induits par niveaux consécutifs, toutes les fois où ils sont des sous-ordres induits par niveau d'un sur-ordre. Ainsi nous caractérisons les ordres qui sont des sous-ordres induits par niveaux consécutifs, toutes les fois où ils sont des sous-ordres induits d'un sur-ordre.

Dans cet article, nous donnons un contre-exemple au lemme 12 de l'article “On Operations and Linear Extensions of Well Partially Ordered Sets” par Maciej Malicki et Aleksander Rutkowski (2003).

Dans cet article, nous étudions les "représentations questionnables" des ordres (partiels ou totaux), introduites dans notre article précédent "A class of orders with linear? time sorting algorithm". (Plus tard, nous considérons des structures relationnelles ou fonctionnelles binaires arbitraires plutôt que des ordres.) Une "question" est la première différence entre 2 suites (indexées par un ordinal) d'éléments d'ordres/ensembles. Dans les "représentations questionnables" de largeur finie d'un ordre O, la comparaison de deux éléments peut être résolue en regardant la "question" qui compare les éléments d'un ordre fini O'. Un corollaire d'un théorème de Cantor (1895) est que tous les ordres totaux dénombrables ont une représentation questionnable binaire (de largeur 2). Nous trouvons de nouvelles classes d'ordres pour lesquelles tester l'isomorphisme de deux ordres ou compter le nombre d'extensions linéaires peut être fait en temps polynomial. Nous présentons aussi une généralisation de la largeur questionnable, appelée largeur arborescente questionnable équilibrée, et montrons que si une classe de structures binaires a une largeur arborescente ou une largeur de clique bornée, alors elle a une largeur arborescente questionnable équilibrée bornée. Mais il y a des classes de graphes de largeur arborescente questionnable équilibrée bornée et largeur arborescente ou largeur de clique infinie.

Dans cet article, nous donnons un sens mathématique précis à "linear? time" qui correspond au comportement expérimental de l'algorithme. L'algorithme de tri n'est pas le nôtre, il s'agit d'une variante de radix sort avec counting sort comme sous-routine. Le vrai résultat de cet article est un résultat d'universalité efficiente de l'ordre lexicographique, ou plus généralement pour certaines extensions linéaires de l'ordre partiel "Next" : "si les items courants sont égaux, comparer les items suivants". Nous définissons de nouvelles classes d'ordres : (Finite width) Tree Structured Orders ou ordres arborescents (de largeur finie) en français. Nous montrons qu'une instance d'un ordre arborescent de largeur finie peut être convertie en temps et espace linéaire en une instance d'ordre lexicographique. Les constantes impliquées par l'algorithme de "nextification" sont petites (autour de 3 pour les ordres de la vie réelle). La classe des ordres arborescents de largeur finie contient les ordres finis ({0, 1}, int32, int64, ..., float, double, ...), ainsi que les ordres construits à partir des ordres finis sur une structure arborescente. En particulier, les entiers de taille non bornée, les chaînes avec une collation arbitraire et tous les ordres utilisés pour trier les requêtes SQL sont des ordres arborescents de largeur finie.

Étant donné un graphe non-orienté G = (V, E) avec n sommets et une longueur positive w(e) sur chaque arête e ∈ E, nous considérons des arbres couvrants de Distance Moyenne Minimum (DMM, MAD en anglais), c'est à dire des arbres qui minimisent la somme des longueurs des chemins entre toutes les paires de sommets. L'un des premiers résultats sur ce problème est celui de Wong qui a montré en 1980 qu'un arbre couvrant de Plus Courts Chemins (PCC, DP en anglais pour Distance Preserving) enraciné sur un sommet médian de G est une solution approchée à un facteur 2 près. D'un autre côté, Dankelmann a fourni en 2000 une classe de graphes où aucun arbre DMM n'est PCC depuis un sommet. Nous établissons ici une nouvelle relation entre les arbres DMM et PCC. Nous montrons que dans un arbre DMM de G, chaque sous-arbre T' = (V', E') composé d'un sommet r et de l'union des branches de r qui sont chacunes de taille au plus √(n/2w+), où w+ est la longueur maximum d'une arête dans G, est un arbre PCC depuis r du sous-graphe de G induit par V'.

Dans un article récent, Amini et al. ont introduit un cadre de travail général pour prouver des théorèmes de dualité entre divers types de décompositions arborescentes et leurs objets combinatoires duaux. Ils unifient toutes les preuves particulières en un théorème de dualité basé sur les fonctions de partition sous-modulaires. Ce théorème général reste néanmoins un peu technique et surtout reste limité à cette propriété de sous-modularité. Au lieu de fonctions de partition, nous proposons ici une propriété combinatoire simple sur les ensembles de partitions qui a pour conséquence ces résultats de dualité. Notre approche est à la fois plus simple et un petit peu plus générale. Nous montrons aussi que, sous une hypothèse raisonnable, l'existence de cette dualité a pour conséquence la propriété combinatoire mise en évidence.

Il y a 25 ans, Valiant a introduit un modèle algébrique de calcul afin d'étudier la complexité de l'évaluation de familles de polynômes. Cette théorie fut introduite avec les classes de complexité VP et VNP qui sont des analogues algébriques des classes P et NP. Parmi les familles de polynômes qui sont difficiles à évaluer (c.-à-d. VNP-complètes) figurent le permanent et le polynôme hamiltonien. Dans un article précédent, les auteurs avec P. Koiran ont étudié l'expressivité du permanent et de l'hamiltonien de matrices de largeur arborescente bornée, ainsi que l'expressivité des couplages parfaits de graphes planaires. Il fût établi que le permanent et l'hamiltonien de matrices de largeur arborescente bornée sont équivalents aux formules arithmétiques. De plus, il fût démontré que la somme des poids des couplages parfaits des graphes planaires est équivalente aux circuits (faiblements) asymétriques. Dans cet article, nous poursuivons les recherches dans la direction décrite ci-dessus et étudions l'expressivité des permanent, hamiltonien et couplages parfaits des matrices qui sont de largeur linéaire ou de largeur de clique bornée. En particulier, nous prouvons que ces trois familles de polynômes sur les matrices de largeur linéaire bornée sont équivalentes aux formules arithmétiques. C'est une amélioration de notre résultat précédent pour les matrices de largeur arborescente bornée. Enfin, nous démontrons l'appartenance à VP de ces polynômes pour les matrices de largeur de clique bornée.

Cet article présente une famille infinie de problèmes combinatoires qui montre des changements de complexité extrêmement brusques entre problèmes voisins. Nous définissons le problème P_k^l qui est une variante du partitionnement d'hypergraphes seulement exprimé sous forme de contraintes avec les paramètres k et l comme suit : Étant donnés un hypergraphe à n sommets et k tailles de couleurs t₁, ..., t_k de somme n, peut-on colorer les sommets avec k couleurs ayant les tailles spécifiées de telle sorte que chaque hyperarête intersecte au plus l couleurs ? Nous montrons que, pour des paramètres l et k fixés, P_k^l est : polynomial quand l = 1 et NP-complet quand l ≠ 1 sur la classe des hypergraphes ; NP-complet quand l = 1 et linéaire quand l ≠ 1 sur la classe des hypergraphes avec des hyperarêtes disjointes. Cette inversion de complexité est possible car les hypergraphes avec des hyperarêtes disjointes peuvent être encodés de manière plus compacte, en l'occurence Θ(m log(n)) au lieu de Θ(mn) bits (n et m sont les nombres de sommets et arêtes de l'hypergraphe).

Il y a 25 ans, Valiant a introduit un modèle algébrique de calcul afin d'étudier la complexité de l'évaluation de familles de polynômes. Cette théorie fut introduite avec les classes de complexité VP et VNP qui sont des analogues algébriques des classes P et NP. Parmi les familles de polynômes qui sont difficiles à évaluer (c.-à-d. VNP-complètes) figurent le permanent et le polynôme hamiltonien. Dans un article précédent, les auteurs avec P. Koiran ont étudié l'expressivité du permanent et de l'hamiltonien de matrices de largeur arborescente bornée, ainsi que l'expressivité des couplages parfaits de graphes planaires. Il fût établi que le permanent et l'hamiltonien de matrices de largeur arborescente bornée sont équivalents aux formules arithmétiques. De plus, il fût démontré que la somme des poids des couplages parfaits des graphes planaires est équivalente aux circuits (faiblements) asymétriques. Dans cet article, nous poursuivons les recherches dans la direction décrite ci-dessus et étudions l'expressivité des permanent, hamiltonien et couplages parfaits des matrices qui sont de largeur linéaire ou de largeur de clique bornée. En particulier, nous prouvons que ces trois familles de polynômes sur les matrices de largeur linéaire bornée sont équivalentes aux formules arithmétiques. C'est une amélioration de notre résultat précédent pour les matrices de largeur arborescente bornée. Enfin, nous démontrons l'appartenance à VP de ces polynômes pour les matrices de largeur de clique bornée.

Valiant a introduit, il y a 25 ans, un modèle algébrique de calcul avec les classes de complexité VP et VNP qui peuvent être vues comme des analogues algébriques des classes P et NP. Les exemples les plus importants de problèmes difficiles (c.-à-d. VNP-complets) dans ce modèle incluent le permanent et le polynôme hamiltonien. Dans cet article, nous étudions l'expressivité de cas spéciaux simples de ces polynômes. Nous montrons que le permanent et l'hamiltonien de matrices de largeur arborescente bornée sont équivalents aux formules arithmétiques. De plus, nous prouvons que les circuits (faiblements) asymétriques sont équivalents à la somme des poids des couplages parfaits des graphes planaires.

Attention, ce résumé comporte un peu d'ironie et d'humour.
Dans ce mémoire, nous défendons l'idée selon laquelle, pour tout modèle de calcul raisonnable, ce n'est plus tant le modèle qui compte pour caractériser les classes de complexité importantes que la complexité de la structure combinatoire sous-jacente et en définitive d'un graphe sous-jacent. Pour prendre l'exemple des circuits booléens ou algébriques comme modèles, tout ce qui importe est la complexité du graphe orienté sous-jacent au circuit. Par modèle de calcul raisonnable, nous entendons, comme il se doit, un modèle qui étudié sur une classe de graphes standard nous donne la classe de complexité standard attendue afin de satisfaire aux règles élémentaires des tautologies. On pourrait aussi choisir comme modèles raisonnables les modèles Turing-complet (ou une autre notion de complétude plus adaptée selon les objets calculés), formalisables dans une logique simple (afin d'éviter les «tricheries» et les modèles conçus spécialement pour faire échouer la belle idée défendue). Néanmoins, cette seconde option n'étant pas sans risque, nous nous contentons de la proposer.
La thèse défendue est une version un peu plus formalisée et précise mathématiquement de cette idée aux contours un peu flous et qui est donc nécessairement un peu fausse telle quelle.

Dans ce mémoire, nous étudions la complexité du calcul de la largeur de branche des graphes de cordes. Nous montrons qu'une borne supérieure peut être calculée en temps polynomial. Nous étudions par ailleurs un problème de partitionnement d'hypergraphes lié et montrons qu'il peut lui aussi être résolu en temps polynomial.

Dans un article récent, Amini et al. ont introduit un cadre de travail général pour prouver des théorèmes de dualité entre divers types de décompositions arborescentes et leurs objets combinatoires duaux. Ils unifient toutes les preuves particulières en un théorème de dualité basé sur les fonctions de partition sous-modulaires. Ce théorème général reste néanmoins un peu technique et surtout reste limité à cette propriété de sous-modularité. Au lieu de fonctions de partition, nous proposons ici une propriété combinatoire simple sur les ensembles de partitions qui a pour conséquence ces résultats de dualité. Notre approche est à la fois plus simple et un petit peu plus générale. Nous montrons aussi que, sous une hypothèse raisonnable, l'existence de cette dualité a pour conséquence la propriété combinatoire mise en évidence.

Il y a 25 ans, Valiant a introduit un modèle algébrique de calcul afin d'étudier la complexité de l'évaluation de familles de polynômes. Cette théorie fut introduite avec les classes de complexité VP et VNP qui sont des analogues algébriques des classes P et NP. Parmi les familles de polynômes qui sont difficiles à évaluer (c.-à-d. VNP-complètes) figurent le permanent et le polynôme hamiltonien. Dans un article précédent, les auteurs avec P. Koiran ont étudié l'expressivité du permanent et de l'hamiltonien de matrices de largeur arborescente bornée, ainsi que l'expressivité des couplages parfaits de graphes planaires. Il fût établi que le permanent et l'hamiltonien de matrices de largeur arborescente bornée sont équivalents aux formules arithmétiques. De plus, il fût démontré que la somme des poids des couplages parfaits des graphes planaires est équivalente aux circuits (faiblements) asymétriques. Dans cet article, nous poursuivons les recherches dans la direction décrite ci-dessus et étudions l'expressivité des permanent, hamiltonien et couplages parfaits des matrices qui sont de largeur linéaire ou de largeur de clique bornée. En particulier, nous prouvons que ces trois familles de polynômes sur les matrices de largeur linéaire bornée sont équivalentes aux formules arithmétiques. C'est une amélioration de notre résultat précédent pour les matrices de largeur arborescente bornée. Enfin, nous démontrons l'appartenance à VP de ces polynômes pour les matrices de largeur de clique bornée.

Valiant a introduit, il y a 25 ans, un modèle algébrique de calcul avec les classes de complexité VP et VNP qui peuvent être vues comme des analogues algébriques des classes P et NP. Les exemples les plus importants de problèmes difficiles (c.-à-d. VNP-complets) dans ce modèle incluent le permanent et le polynôme hamiltonien. Dans cet article, nous étudions l'expressivité de cas spéciaux simples de ces polynômes. Nous montrons que le permanent et l'hamiltonien de matrices de largeur arborescente bornée sont équivalents aux formules arithmétiques. De plus, nous prouvons que les circuits (faiblements) asymétriques sont équivalents à la somme des poids des couplages parfaits des graphes planaires.

Cet article présente une famille infinie de problèmes combinatoires qui montre des changements de complexité extrêmement brusques entre problèmes voisins. Nous définissons le problème P_k^l qui est une variante du partitionnement d'hypergraphes seulement exprimé sous forme de contraintes avec les paramètres k et l comme suit : Étant donnés un hypergraphe à n sommets et k tailles de couleurs t₁, ..., t_k de somme n, peut-on colorer les sommets avec k couleurs ayant les tailles spécifiées de telle sorte que chaque hyperarête intersecte au plus l couleurs ? Nous montrons que, pour des paramètres l et k fixés, P_k^l est : polynomial quand l = 1 et NP-complet quand l ≠ 1 sur la classe des hypergraphes ; NP-complet quand l = 1 et linéaire quand l ≠ 1 sur la classe des hypergraphes avec des hyperarêtes disjointes. Cette inversion de complexité est possible car les hypergraphes avec des hyperarêtes disjointes peuvent être encodés de manière plus compacte, en l'occurence Θ(m log(n)) au lieu de Θ(mn) bits (n et m sont les nombres de sommets et arêtes de l'hypergraphe).

Dans ce cadeau bonux, nous caractérisons les familles de parties d’un ensemble qu'on peut définir comme le niveau 0 d’une fonction sous-modulaire.

Dans ce cadeau bonux, nous caractérisons les familles de parties d’un ensemble qu'on peut définir comme la pré-image en 0 d’une fonction modulaire.

Un élément simple de vérité pour ceux qui s'en préoccupent. L'idéal est, à mon avis, de lire le résumé de ma thèse sur cette page quand on survole l'élément, puis de lire «Tout est explicite» et enfin de lire ma thèse (ou juste l'introduction et la conclusion, du tapuscrit original ou bien du résumé en anglais).
Sylvain Périfel a eu la gentillesse de me faire un retour sur ce texte et il m'a confirmé que le sens modèle de calcul vers problème peut être considéré comme «presque explicite / folklore».