45 articles
Cette note présente une version simplifiée et optimisée de l'algorithme d'Eden, Ron et Seshadhri pour approximer le degré moyen d'un graphe d'arboricité bornée, éliminant les facteurs logarithmiques superflus grâce à une analyse complète et une complexité en requêtes de .
Cet article établit de nouvelles séparations entre les circuits quantiques peu profonds (notamment avec des portes Toffoli à contrôle illimité ou des conseils quantiques) et les circuits classiques constants, tout en démontrant que l'utilisation de portes de taille infinie ou d'espaces de Hilbert de dimension supérieure n'offre pas d'avantage computationnel supplémentaire par rapport aux implémentations qubit standard.
Cet article initie une étude systématique de la complexité computationnelle du test de propriétés en établissant des hiérarchies temps-requêtes et en démontrant, via des conjectures de complexité fine, une séparation fondamentale entre la complexité en requêtes et la complexité temporelle pour l'approximation de la distance aux demi-espaces.
Cet article démontre que la décision de l'existence d'une stratégie gagnante dans le jeu de cartes Yu-Gi-Oh! TCG est un problème indécidable et -complet, en réduisant le problème de l'arrêt et l'ensemble des ordres bien fondés dénombrables à ce problème via des decks légaux.
Cet article propose une synthèse unifiée de l'asymétrie fondamentale entre génération et reconnaissance en théorie des langages formels en identifiant six dimensions distinctes, dont deux nouvelles (directionnalité et temporalité), pour démontrer que cette divergence opérationnelle persiste malgré l'unification architecturale des modèles de langage modernes.
Cette thèse d'habilitation présente des algorithmes à la fois rapides et économes en mémoire pour le calcul polynomial, en abordant à la fois les contraintes d'espace lors des opérations fondamentales et le traitement efficace des polynômes creux, notamment via une première méthode d'interpolation quasi-linéaire.
Cet article établit des conditions nécessaires et suffisantes pour la simulabilité classique de circuits quantiques suivis d'un post-traitement classique sparse, démontrant que de tels systèmes, y compris ceux de type IQP ou Clifford Magic, deviennent simulables malgré la difficulté de simuler les circuits seuls, et propose un algorithme probabiliste polynomial pour le cas des circuits de profondeur constante.
En réinterprétant la découverte de témoins NP sous un angle informationnel via le modèle « psocid », ce papier démontre que l'absence de structure dans l'espace de recherche limite l'information acquise par les requêtes d'égalité à un niveau insuffisant pour une récupération fiable, révélant ainsi une origine informationnelle fondamentale de la complexité exponentielle de la recherche.
Cet article démontre que le problème de coloration partielle maximale avec listes sur les graphes sans est soluble en temps polynomial pour tout graphe fixé, résolvant ainsi une question ouverte et améliorant les algorithmes précédents.
Cet article étudie la complexité des fragments restreints du modèle Decision DNNF, en établissant de nouvelles bornes inférieures pour le modèle -OBDD, en démontrant des séparations exponentielles avec d'autres modèles de décision, et en introduisant un modèle relâché, le Structured -FBDD, qui s'avère efficace pour les formules CNF à largeur arborescente d'incidence bornée.
Cet article présente des algorithmes classiques efficaces pour les problèmes et à solutions entières contraintes, réfutant ainsi l'existence d'une accélération quantique exponentielle pour ces problèmes.
Cet article présente un algorithme d'approximation de ratio $4/3O(m\sqrt{n})$ supérieure aux méthodes précédentes.
Cet article établit une classification complète de la complexité computationnelle distribuée des problèmes d'optimisation locale dans les cycles orientés, démontrant que leur résolution se situe dans l'une des quatre classes de complexité distinctes (O(1), Θ(log* n) ou Θ(n)) et fournissant un algorithme centralisé capable d'identifier automatiquement cette classe ainsi que de synthétiser un algorithme distribué asymptotiquement optimal.
Ce papier établit un lien fondamental entre la parallélisabilité des réseaux de neurones récurrents linéaires (LRNN) et les classes de complexité computationnelle, démontrant que leur structure permet une exécution efficace similaire aux transformateurs, contrairement aux RNN non linéaires qui, en raison de leur capacité à résoudre des problèmes P-complets, posent une barrière théorique à une telle parallélisation.
Cet article propose une approche intégrative pour généraliser la sélection équitable top- à plusieurs groupes protégés en minimisant la disparité par rapport à une fonction de référence, en analysant la complexité computationnelle du problème et en introduisant une nouvelle mesure de perte d'utilité pour améliorer la stabilité des résultats sur des données réelles.
Cet article présente la mise en œuvre et l'analyse de complexité d'algorithmes quantiques basés sur la recherche de Grover pour résoudre le problème NP-complet de coordination des signaux réseau, y compris une formulation robuste offrant une accélération quadratique indépendante de la taille de l'espace de recherche.
Ce papier présente une méthode optimisée, baptisée ResultantSolver, qui résout un système d'équations polynomiales sur un corps fini en exploitant sa structure creuse via des calculs successifs de résultants, surpassant ainsi les approches par force brute et les bases de Gröbner standards.
Ce papier établit une correspondance exacte entre la puissance expressive des réseaux de neurones à graphes récurrents et celle des circuits arithmétiques récurrents opérant sur les nombres réels, en démontrant que ces deux modèles peuvent se simuler mutuellement.
Cet article résout la question ouverte sur la dépendance exacte du paramètre de largeur d'arbre pour le problème de l'appariement de Morse optimal en proposant un algorithme en temps $2^{O(k \log k)} n$ et en prouvant, sous l'hypothèse de complexité exponentielle (ETH), qu'aucun algorithme significativement plus rapide n'existe.
Cet article démontre que la conjecture d'Aaronson-Ambainis, qui postule l'existence d'une coordonnée à forte influence pour les polynômes de variance suffisante, est vérifiée pour une fraction non négligeable de restrictions aléatoires appliquées à ces polynômes.