A symmetric recursive algorithm for mean-payoff games
El artículo propone un nuevo algoritmo recursivo determinista y simétrico para resolver juegos de pago medio.
💻 Category
cs.DS
87 artículos
Succinct QUBO formulations for permutation problems by sorting networks
Este artículo presenta una nueva formulación QUBO para problemas de permutación basada en redes de ordenamiento que, a diferencia de la codificación estándar de matrices de permutación, utiliza significativamente menos variables (), ofrece un grafo de interacción más disperso y permite el muestreo imparcial así como la imposición de restricciones adicionales y operaciones algebraicas sobre las permutaciones.
Structured Gossip: A Partition-Resilient DNS for Internet-Scale Dynamic Networks
El artículo presenta un sistema de DNS basado en gossip estructurado que utiliza tablas de dedos de DHT y operaciones conmutativas para lograr consistencia eventual y escalabilidad en redes dinámicas masivas, reduciendo la complejidad de mensajes y eliminando la necesidad de coordinación global ante particiones de red.
The Theory and Practice of Computing the Bus-Factor
Este artículo presenta un marco unificado y agnóstico al dominio para calcular el "factor autobús" mediante la modelización de proyectos como grafos bipartitos, formalizando dos interpretaciones complementarias (redundancia y criticidad), demostrando que su cálculo exacto es NP-duro y proponiendo una nueva medida basada en la robustez de la red que captura tanto la pérdida de cobertura como la fragmentación del proyecto, junto con algoritmos de aproximación eficientes y una validación empírica que confirma su superioridad frente a enfoques existentes.
The Li-Chao Tree: Algorithm Specification and Analysis
Este artículo presenta la primera especificación formal y el análisis completo del árbol de Li-Chao, una estructura de datos ampliamente utilizada en programación competitiva para el mantenimiento dinámico de envolventes inferiores, incluyendo sus demostraciones de corrección, complejidad teórica y caracterización de rendimiento.
Permutation Match Puzzles: How Young Tanvi Learned About Computational Complexity
Este artículo caracteriza la resolubilidad de los acertijos de coincidencia de permutaciones mediante la aciclicidad de un grafo de restricciones, proporciona una fórmula de longitud de gancho para contar las soluciones, ofrece un algoritmo lineal para reparar puzzles no resolubles y demuestra que la generalización con permutaciones arbitrarias es NP-completa.
Sampling Colorings with Fixed Color Class Sizes
Este artículo presenta un algoritmo de muestreo en tiempo polinómico para coloraciones equitativas (o con pequeñas desviaciones) en grafos con colores, utilizando la geometría de polinomios multivariados para demostrar un Teorema Central del Límite local y establecer la existencia de tales coloraciones.
Bayesian inference of planted matchings: Local posterior approximation and infinite-volume limit
Este trabajo demuestra que, en el caso de emparejamientos parciales en una dimensión, la inferencia bayesiana de un emparejamiento oculto entre conjuntos de puntos correlacionados permite una aproximación local del posterior y un límite bien definido en el volumen infinito gracias a la decaimiento de correlaciones, mientras que para el emparejamiento exacto se requiere un ordenamiento global y una indexación cuidadosa basada en el flujo para definir dicho límite.
A note on approximating the average degree of bounded arboricity graphs
Este artículo presenta una versión completa y optimizada del algoritmo de Eden, Ron y Seshadhri para aproximar el grado promedio de grafos con arboricidad acotada, eliminando factores logarítmicos innecesarios y logrando una complejidad de consultas de .
Faster shortest-path algorithms using the acyclic-connected tree
Este artículo presenta un método de preprocesamiento lineal basado en un nuevo tipo de descomposición gráfica llamada árbol acíclico-conectado (A-C), que permite mejorar la complejidad temporal de los algoritmos de camino más corto desde un origen (SSSP) en grafos con estructuras modulares, logrando tiempos lineales para grafos acíclicos y reduciendo la dependencia del número de vértices al ancho de anidamiento del grafo.
Computational Complexity in Property Testing
Este trabajo inicia un estudio sistemático de la complejidad computacional en la prueba de propiedades, estableciendo teoremas de jerarquía entre consultas y tiempo, y demostrando mediante conjeturas de complejidad que la aproximación de la distancia a semiespacios requiere un tiempo significativamente mayor que el número de consultas, revelando así una brecha fundamental entre ambas complejidades.
Hallucination is a Consequence of Space-Optimality: A Rate-Distortion Theorem for Membership Testing
Este artículo demuestra teóricamente y valida empíricamente que las alucinaciones en los modelos de lenguaje son una consecuencia inevitable de la optimización de la memoria bajo capacidad limitada, donde la estrategia óptima de compresión de información requiere asignar alta confianza a hechos no reales para minimizar la pérdida de información.
DRESS and the WL Hierarchy: Climbing One Deletion at a Time
Este artículo proporciona la justificación teórica de que el marco -DRESS distingue pares CFI para todo y demuestra condicionalmente que su poder de discriminación es al menos equivalente al de la jerarquía -WL para todos los grafos.
Transposition is Nearly Optimal for IID List Update
Este artículo demuestra que la regla de transposición en el problema de actualización de listas bajo el modelo i.i.d. logra un costo de acceso esperado que excede en a lo sumo 1 al óptimo, confirmando así una conjetura de Rivest de hace 50 años mediante una prueba combinatoria que descompone el costo excedente.
Reconstructing Bounded Treelength Graphs with Linearithmic Shortest Path Distance Queries
El artículo presenta un algoritmo determinista que reconstruye grafos conexos con grado acotado y longitud arbórea acotada utilizando consultas de distancia, mejorando el estado del arte en un factor logarítmico y igualando la cota inferior conocida para grafos de acotada cordalidad.
Density-Dependent Graph Orientation and Coloring in Scalable MPC
Este artículo presenta algoritmos de computación masivamente paralela (MPC) en el régimen de memoria fuertemente sublineal que orientan y colorean grafos en rondas en función de la densidad de su subgrafo más denso, superando así la barrera de complejidad de rondas de establecida por trabajos anteriores.
Intermittent Cauchy walks enable optimal 3D search across target shapes and sizes
Este artículo demuestra matemáticamente que en tres dimensiones, la estrategia de caminata de Lévy con exponente (caminata de Cauchy) es óptima y escala-invariante para la detección de objetivos de diversas formas y tamaños, revelando una sensibilidad a la geometría del objetivo que es única en esta dimensión.
Polynomial-size encoding of all cuts of small value in integer-valued symmetric submodular functions
El artículo presenta una representación de tamaño polinómico para la familia de todos los cortes de valor en funciones submodulares simétricas enteras, junto con un algoritmo eficiente para construirla y su aplicación para encontrar conjuntos con cardinalidad prescrita.
Sublinear-Time Reconfiguration of Programmable Matter with Joint Movements
Este artículo demuestra que es posible reconfigurar sublinealmente cualquier estructura de materia programable en una línea canónica en rondas utilizando movimientos conjuntos centralizados, resolviendo así una cuestión abierta sobre la viabilidad de algoritmos universales sin suposiciones auxiliares.
Sample-and-Search: An Effective Algorithm for Learning-Augmented k-Median Clustering in High dimensions
Este artículo presenta el algoritmo "Sample-and-Search", un método de aprendizaje aumentado para el problema de clustering -medianas en altas dimensiones que, mediante una técnica de muestreo, reduce significativamente la complejidad computacional y la dependencia exponencial de la dimensión en comparación con enfoques existentes.