Markus Hecher : les algorithmes et la complexité pour des problèmes difficiles en informatique

Quel est votre domaine de recherche ?

Markus Hecher : Je me concentre principalement sur les algorithmes et la complexité pour des problèmes difficiles en informatique, à la fois en théorie et en pratique. Cela signifie que je ne suis pas aligné avec certaines hypothèses de complexité computationnelle : pour moi, la solvabilité polynomiale ne signifie pas qu’un problème peut être résolu efficacement. En effet, dans la pratique il y a une énorme différence entre les problèmes qui peuvent être résolus en temps linéaire ou quadratique.

Actuellement, j’aimerais comprendre à quel point nous pouvons compter les solutions efficacement et il y a une facette intéressante liée à mes recherches : le comptage n’est pas l’énumération ! En théorie comme en pratique, nous pouvons souvent compter les solutions beaucoup plus rapidement que de simplement les énumérer. Mais qu’est-ce qui est ouvert si la plupart des résultats de complexité montrent de la dureté ? Dans le comptage il y a beaucoup de problèmes ouverts qui sont liés à quelques limitations fondamentales comme l’espace logarithmique. Récemment, j’ai fait des progrès [LICS 2025] en montrant l’impact du post-traitement après le comptage de l’espace logique : même un simple post-traitement arithmétique des comptes rend souvent le comptage difficile !

Qu’avez-vous fait avant d’entrer au CNRS ? Pourquoi avoir choisi le CNRS ?

M.H. : Auparavant, j’étais chercheur postdoctoral au MIT, où je travaillais avec Erik Demaine, sur la base de mon projet FWF Erwin Schroedinger sur le raisonnement quantitatif. La recherche et la vie aux États-Unis sont très différentes qu'en France, mais j’espère pouvoir m’adapter à toutes les différences et tous les défis. J’ai choisi le CNRS, parce que je crois vraiment à leur mission. En effet, tant de gens m’ont aidé avec le sujet et ont essayé de comprendre mes recherches et comment ils pourraient s’y intégrer. Je crois que le CNRS et la communauté scientifique française font les choses bien. Il semble que le CNRS ait compris qu’il est préférable d’offrir un environnement inclusif et favorable, exempt de nombreuses limitations liées à d’autres environnements académiques typiques.

Qu’est-ce que qui vous a amené à faire des sciences informatiques ?

M.H. : J’ai toujours été attiré par l’informatique, car elle peut mettre en avant des perspectives fondamentalement nouvelles à la fois dans les domaines théoriques comme les mathématiques, mais aussi dans les domaines appliqués et applications (ML). J’aime étudier les problèmes avec deux yeux, mon point de vue théorique et mon point de vue pratique. Je pense qu’il est irréfléchi de ne se soucier que de la théorie ou des applications. Je veux faire de la recherche qui compte dans la pratique. Bien que cela signifie que quelqu’un pourrait avoir des sentiments étranges à votre sujet, parce qu’ils pourraient penser que vous ne correspondez pas à la théorie ou que vous ne correspondez pas à la pratique. Cependant, ce sont précisément de tels points de vue différents qui m’ont finalement permis de faire de nouveaux résultats théoriques. En effet, si vous avez un point de vue différent et novateur par rapport à d'autres dans votre domaine, cela peut être une grande chance de dériver vers des résultats novateurs ! Qu’est-ce que j’attends des sciences informatiques ? J’espère une plus grande ouverture vers les nouvelles approches et techniques qui pourraient sembler étranges au premier abord. Après tout, ce sont des idées bizarres qui ont fait des sciences informatiques ce qu’elles sont aujourd’hui. Je suis toujours partant pour en discuter.