87 articles
Cet article propose un schéma générique pour l'estimation des moments dans le modèle de flux tournant en utilisant un hachage vers des processus de Lévy, unifié par le théorème de représentation de Lévy-Khintchine, qui explique et généralise de nombreuses constructions existantes tout en étendant la tractabilité à des fonctions presque périodiques et à des cas multidimensionnels.
Cet article introduit un nouveau type de sous-gradient basé sur les fonctions de Busemann pour les espaces de Hadamard, permettant d'étendre les méthodes de sous-gradient stochastiques et incrémentales avec des garanties de complexité à des problèmes d'optimisation non linéaires tels que le calcul de médianes dans l'espace des arbres BHV.
Les auteurs démontrent qu'une méthode exacte simple résout la quasi-totalité des instances classiques du problème du voyageur de commerce avec fenêtres de temps en moins de dix secondes, révélant ainsi que ces benchmarks ne sont plus représentatifs pour évaluer les performances des algorithmes.
Cet article propose l'algorithme de déformation temporelle élastique, qui résout le problème d'appariement de séries temporelles dans un espace métrique arbitraire avec une pénalité de déformation basée sur le noyau de Hellinger, le tout avec une complexité computationnelle cubique.
Ce papier présente bsort, un algorithme de tri non basé sur la comparaison pour les entiers et les nombres à virgule flottante, qui atteint une complexité temporelle de et une complexité spatiale de tout en offrant des performances compétitives pour les petits mots de données.
Cet article présente un algorithme de streaming à un passage pour le problème de sélection d'intervalles unitaires dans un ordre aléatoire, atteignant un facteur d'approximation attendu de 0,7401 avec un espace linéaire par rapport à la solution optimale, tout en établissant des limites inférieures démontrant que toute amélioration significative nécessite un espace linéaire par rapport à la taille de l'entrée.
Cet article présente un schéma d'approximation polynomial (PTAS) pour le problème du 2-matching pondéré sans triangle, résolvant ainsi un problème ouvert en offrant une approximation par le biais d'un algorithme de recherche locale et d'une analyse non triviale.
Cet article présente un nouvel algorithme de minage de sous-chaînes fréquentes sous garantie de confidentialité différentielle qui conserve les erreurs quasi-optimales des travaux récents tout en réduisant drastiquement la complexité spatiale et temporelle pour permettre une mise à l'échelle efficace.
Ce papier propose un nouveau protocole pour le problème des experts distribués qui améliore les bornes précédentes en réduisant la communication nécessaire pour atteindre un regret donné, en fonction du nombre d'experts, de serveurs et de la norme des pertes.
Cet article étudie le problème de couplage non croisé pondéré en ligne dans le plan euclidien, démontrant l'impossibilité d'un rapport de compétitivité non trivial pour les algorithmes déterministes tout en établissant l'existence d'un rapport constant grâce à la randomisation, et en fournissant des bornes pour diverses variantes ainsi qu'une amélioration de la complexité en conseils nécessaire pour l'optimalité.
Cet article présente et prouve la correction d'un algorithme automatisé qui énumère exhaustivement les paires critiques pour les systèmes de réécriture de diagrammes de chaînes dans les catégories monoïdales symétriques sans structure de Frobenius, en utilisant la manipulation concrète d'hypergraphes.
Ce papier améliore le temps d'exécution des algorithmes d'approximation pour les problèmes de -médiane et -means en espaces euclidiens de faible dimension et établit une borne inférieure presque correspondante sous l'hypothèse du temps exponentiel.
Cet article propose un algorithme d'approximation polynomial de ratio 2/3 pour trouver un couplage critique et relaxément stable de cardinalité maximale dans un problème d'appariement many-to-many avec préférences comportant des égalités et des quotas inférieurs, tout en démontrant que le problème de maximisation exacte est NP-difficile.
Cet article démontre qu'une séparation prouvée persiste entre les algorithmes quantiques efficaces et les algorithmes classiques basés sur des états gaussiens pour l'approximation de l'état fondamental du modèle SYK clairsemé, tant que la probabilité de conservation des termes est supérieure à .
Cet article propose un schéma différentiellement privé pour estimer les statistiques de fonctions boîte noire en arbitrant entre l'efficacité statistique et l'efficacité oracle, tout en établissant des bornes inférieures démontrant la quasi-optimalité de cette approche.
Cet article présente la Théorie de l'Espace d'Exploration (EST), un cadre formel fondé sur la théorie des espaces de connaissances qui modélise les dépendances prérequis entre lieux d'intérêt via des treillis distributifs, permettant ainsi de concevoir un système de recommandation géolocalisée garantissant mathématiquement la validité structurelle de chaque étape d'exploration.
Cet article propose le premier cadre formel et des algorithmes à garanties théoriques pour l'apprentissage par renforcement multi-agents coopératif avec des récompenses sous-modulaires, surmontant ainsi la malédiction de la dimensionnalité grâce à une complexité polynomiale.
Cet article propose et étudie les réseaux phylogénétiques non enracinés -découpables, une nouvelle classe reconnaissable en temps polynomial et permettant de résoudre efficacement le problème de la contenance d'arbre, comblant ainsi le vide laissé par les réseaux orientables en arbre-enfant dont la reconnaissance est NP-difficile.
Ce papier présente une nouvelle méthode combinant substitution et recherche par backtracking pour prouver que la complexité bilinéaire de la multiplication de matrices 3×3 sur le corps fini est d'au moins 20, améliorant ainsi la borne inférieure précédente de 19.
Cet article présente la première méthode permettant d'approximer la contraction de réseaux de tenseurs arbitraires, y compris cycliques, et propose une seconde approche pour les réseaux acycliques dont la complexité temporelle et spatiale dépend uniquement polynomialement du nombre de contractions.