A symmetric recursive algorithm for mean-payoff games
Ce papier propose un nouvel algorithme récursif symétrique et déterministe pour résoudre les jeux à moyenne de gain.
💻 Category
cs.DS
87 articles
Succinct QUBO formulations for permutation problems by sorting networks
Cet article propose une nouvelle formulation QUBO pour les problèmes de permutation basée sur des réseaux de tri, qui réduit considérablement le nombre de variables et la densité du graphe d'interaction par rapport aux encodages classiques tout en permettant un échantillonnage non biaisé et la vérification de propriétés algébriques complexes.
Structured Gossip: A Partition-Resilient DNS for Internet-Scale Dynamic Networks
Ce papier présente le DNS Structured Gossip, une solution résiliente aux partitions pour les réseaux dynamiques à l'échelle d'Internet qui utilise la stabilisation passive et des vecteurs de version pour garantir une cohérence éventuelle avec une complexité de message réduite, éliminant ainsi le besoin de coordination globale.
The Theory and Practice of Computing the Bus-Factor
Cet article propose un cadre unifié et agnostique du domaine pour estimer le facteur de bus en le modélisant comme un problème d'optimisation combinatoire sur des graphes bipartis, prouvant la complexité NP-difficile des formulations exactes et introduisant une nouvelle mesure de robustesse normalisée qui capture à la fois la perte de couverture et la fragmentation du projet, tout en offrant des algorithmes d'approximation efficaces.
The Li-Chao Tree: Algorithm Specification and Analysis
Cet article présente la première spécification formelle et l'analyse complète de l'arbre de Li-Chao, une structure de données largement utilisée en programmation compétitive pour la maintenance dynamique d'enveloppes inférieures, en y ajoutant des preuves de correction, une analyse de complexité et des caractérisations de performances empiriques.
Permutation Match Puzzles: How Young Tanvi Learned About Computational Complexity
Cet article caractérise la résolubilité et le nombre de solutions des puzzles de correspondance de permutations sur grille, fournit un algorithme linéaire pour corriger les instances non résolubles, et démontre que la généralisation du problème à des permutations arbitraires est NP-complète.
Sampling Colorings with Fixed Color Class Sizes
Cet article présente un algorithme d'échantillonnage polynomial pour les colorations équitables d'un graphe avec couleurs, en utilisant la géométrie des polynômes multivariés pour établir un théorème central limite local multivarié sur la taille des classes de couleurs.
Bayesian inference of planted matchings: Local posterior approximation and infinite-volume limit
Cet article établit que l'inférence bayésienne d'un couplage planté entre deux ensembles de points corrélés en dimension un admet une approximation locale et une limite infinie bien définie pour le couplage partiel grâce à la décroissance des corrélations, tandis que le cas du couplage exact nécessite un tri global et une indexation spécifique basée sur un flot pour définir sa limite asymptotique.
A note on approximating the average degree of bounded arboricity graphs
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 .
Faster shortest-path algorithms using the acyclic-connected tree
Cet article propose une méthode de décomposition graphique appelée arbre acyclique-connecté (A-C), calculable en temps linéaire, qui permet d'améliorer la complexité temporelle des algorithmes de plus court chemin à source unique en exploitant la structure modulaire des graphes via un paramètre de largeur d'imbrication.
Computational Complexity in Property Testing
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.
Hallucination is a Consequence of Space-Optimality: A Rate-Distortion Theorem for Membership Testing
Ce papier démontre que les hallucinations des grands modèles de langage sont une conséquence inévitable de l'optimisation de l'espace mémoire, car la compression d'informations dans un univers de faits clairsemés force théoriquement le modèle à attribuer une haute confiance à certains non-facts pour minimiser la perte d'information.
DRESS and the WL Hierarchy: Climbing One Deletion at a Time
Cet article établit théoriquement que le cadre -DRESS distingue systématiquement les paires CFI et atteint au moins le niveau de la hiérarchie WL, confirmant ainsi par des preuves inconditionnelles et conditionnelles la puissance discriminante de cette méthode itérative basée sur les sous-graphes.
Transposition is Nearly Optimal for IID List Update
Cet article confirme la conjecture de Rivest vieille de 50 ans en démontrant que la règle de transposition, une procédure sans mémoire, atteint un coût d'accès espéré dans la distribution stationnaire d'au plus OPT + 1 pour le problème de mise à jour de liste en modèle i.i.d.
Reconstructing Bounded Treelength Graphs with Linearithmic Shortest Path Distance Queries
Cet article présente un algorithme déterministe qui reconstruit les graphes connexes à degré et longueur arborescente bornés en utilisant un nombre de requêtes de distance , améliorant ainsi les résultats précédents d'un facteur logarithmique et atteignant la borne inférieure connue pour les graphes à chordalité bornée.
Density-Dependent Graph Orientation and Coloring in Scalable MPC
Cet article présente des algorithmes de calcul massivement parallèle (MPC) en mémoire sous-linéaire qui orientent et colorent les graphes en fonction de la densité de leurs sous-graphes en un nombre de tours polylogarithmique double, brisant ainsi la barrière de complexité de des méthodes précédentes.
Intermittent Cauchy walks enable optimal 3D search across target shapes and sizes
Ce papier démontre mathématiquement que la marche de Cauchy (exposant ) constitue une stratégie de recherche intermittente optimale et invariante d'échelle pour détecter des cibles de formes et de tailles variées en trois dimensions, révélant ainsi une sensibilité spécifique à la géométrie absente dans les dimensions inférieures.
Polynomial-size encoding of all cuts of small value in integer-valued symmetric submodular functions
Les auteurs montrent que la famille de tous les ensembles de valeur d'une fonction de connectivité entière symétrique admet une représentation de taille polynomiale et proposent un algorithme efficace pour la construire, généralisant ainsi des résultats antérieurs sur les fonctions de rang de coupe aux fonctions de connectivité générales.
Sublinear-Time Reconfiguration of Programmable Matter with Joint Movements
Cet article démontre que le modèle de mouvement conjoint des amoebots permet une reconfiguration universelle sublinéaire en temps vers une structure canonique, résolvant ainsi une question ouverte sur l'efficacité de la réorganisation sans hypothèses auxiliaires.
Sample-and-Search: An Effective Algorithm for Learning-Augmented k-Median Clustering in High dimensions
Cet article présente l'algorithme « Sample-and-Search », une méthode d'apprentissage augmenté pour le clustering -médiane en haute dimension qui améliore significativement la complexité temporelle et réduit la dépendance exponentielle à la dimensionnalité par rapport aux approches existantes.