91 articles
Cet article présente une structure de données entièrement dynamique qui maintient un sparsificateur spectral d'un graphe géométrique sous des mises à jour de points avec un temps de mise à jour quasi-linéaire, tout en étant robuste face à des adversaires adaptatifs et en permettant des opérations matricielles rapides via un sketch randomisé.
Cet article propose une approche novatrice et symétrique pour résoudre les jeux à paiement actualisé en minimisant la somme des erreurs d'inéquations via une amélioration objective itérative, défiant ainsi la dichotomie traditionnelle entre l'amélioration de stratégie et l'itération de valeur.
Cet article établit que la détection de la corrélation entre deux graphes stochastiques en blocs subsampelés est possible par des polynômes de bas degré si et seulement si le taux d'échantillonnage dépasse le minimum entre la constante d'Otter et le seuil de Kesten-Stigum, définissant ainsi la frontière entre les régimes facile et difficile pour ce problème.
Cet article propose une définition relaxée de la dimension autoroutière qui englobe les espaces doubles comme les grilles et le plan euclidien, permettant ainsi de construire un PTAS pour le problème du voyageur de commerce et de développer un ensemble d'outils métriques fondamentaux.
Cet article propose deux algorithmes généralisés et efficaces pour calculer l'inverse modulaire pour tout entier , en étendant une méthode basée sur les expansions -adiques de Koç et en généralisant les techniques de relèvement de Hensel de Dumas et Hurchalla aux puissances de .
Ce papier propose des algorithmes plus rapides pour des tâches d'algèbre linéaire sur les matrices de noyau en utilisant l'estimation de densité par noyau, améliorant ainsi la dépendance en la taille des données et l'erreur par rapport aux méthodes existantes, tout en établissant des bornes inférieures sur la complexité de ces problèmes.
Cet article présente le premier algorithme itératif déterministe pour construire un coreset de taille optimale sans facteurs logarithmiques, garantissant une intégration de sous-espace pour tout et permettant ainsi de résoudre de manière déterministe le problème de régression .
Cet article présente le premier algorithme offrant une amélioration multiplicative par rapport à l'algorithme glouton pour la maximisation d'une fonction sous-modulaire monotone sous une intersection de contraintes de matroïdes, atteignant un rapport d'approximation de grâce à une approche hybride combinant le glouton et la recherche locale.
Cet article présente des algorithmes à espace polylogarithmique pour la diffusion continue de statistiques sur des flux de type « turnstile » dans un cadre privé, démontrant que l'ajout d'une erreur multiplicative permet de contourner les bornes inférieures d'erreur additive de pour l'estimation du nombre d'éléments distincts et du moment .
Cet article propose une méthode de « capping » de longueur pour les structures de mouvement dans les permutations RLBWT, qui améliore à la fois le temps de construction et de requête tout en réduisant significativement l'espace de stockage, offrant ainsi des algorithmes optimaux pour l'inversion du BWT et l'énumération des tableaux de suffixes.
Le papier présente DRESS, un cadre déterministe et sans paramètre qui affine itérativement la similarité structurelle des arêtes d'un graphe pour générer une empreinte numérique isomorphe-invariante, dont la version étendue -DRESS démontre une expressivité supérieure surpassant les tests de Weisfeiler-Leman sur des benchmarks complexes.