87 artículos
Este artículo presenta la Huffman-Bucket Sketch (HBS), una estructura de datos simple y fusionable que comprime sin pérdidas un HyperLogLog a un espacio óptimo de bits mediante codificación Huffman dinámica, manteniendo actualizaciones de tiempo constante y reduciendo significativamente los requisitos de memoria.
Este artículo presenta un procedimiento lineal para reconocer subconjuntos mínimamente insatisfacibles (MUS) en fórmulas 2-CNF, extiende resultados sobre la complejidad NP de ciertos casos y demuestra que encontrar o decidir la existencia de MUSs que contengan una o dos cláusulas unitarias es resoluble en tiempo polinómico.
Este artículo introduce el boceto de tren tensorial disperso en bloques (BSTT), un operador de proyección aleatoria estructurada que unifica métodos existentes y garantiza propiedades de incrustación e inyección de subespacios con escalado lineal en el orden del tensor, superando así las limitaciones de escalado exponencial de construcciones anteriores.
Este trabajo resuelve una pregunta abierta demostrando la primera separación explícita entre la privacidad diferencial en el modelo de observación continua para los casos no adaptativo y adaptativo, mostrando que un algoritmo no adaptativo puede mantener la precisión durante un número exponencial de pasos temporales mientras que cualquier algoritmo adaptativo falla tras unos pocos pasos.
El artículo presenta IsalGraph, un método que codifica cualquier grafo finito en una cadena compacta mediante un conjunto de instrucciones de nueve caracteres, permitiendo una representación isomórfica, válida y compatible con modelos de lenguaje que facilita la búsqueda de similitud, la generación de grafos y la modelación condicionada.
Este artículo establece límites de complejidad de muestra casi óptimos para probar las propiedades de la existencia de un -clique y la -colorabilidad en grafos densos, demostrando que la extensión del método de contenedores de grafos es una herramienta poderosa para el análisis de algoritmos de prueba de propiedades.
Este artículo presenta un algoritmo 8-competitivo y una cota inferior de 2 para el problema de programación en línea de tiempos ocupados en máquinas heterogéneas con trabajos de longitud uniforme, abordando una generalización teórica clave para servicios de computación en la nube.
Este artículo presenta un algoritmo de tiempo fijo parametrizado (FPT) que extiende el teorema de Gallai-Milgram al demostrar que es posible decidir en tiempo polinómico si un grafo puede cubrirse con menos caminos que su número de independencia, resolviendo así una cuestión abierta y proporcionando la primera solución para problemas como la Hamiltonicidad en grafos con número de independencia pequeño.
El artículo presenta -Motif, un algoritmo acelerado por GPU que reformula el problema del isomorfismo de subgrafos como operaciones de base de datos escalables, logrando aceleraciones de hasta 595 veces frente a métodos tradicionales y facilitando su aplicación en dominios como la compilación de circuitos cuánticos.
Este trabajo presenta y evalúa experimentalmente variantes de árboles B optimizadas para dispositivos embebidos con recursos de memoria limitados, demostrando que estas optimizaciones específicas para almacenamiento permiten un indexado eficiente en dispositivos IoT de pequeño tamaño.
Este artículo presenta los primeros algoritmos de ordenamiento basados en comparaciones que son estrictamente in situ y alcanzan un tiempo de ejecución óptimo en función de la entropía basada en secuencias, utilizando paradigmas simples para adaptar la mezcla natural a sistemas embebidos con memoria limitada.
Este trabajo mejora el análisis de Klivans et al. demostrando que un grado de polinomio de es suficiente para la aproximación bajo distribuciones gaussianas, lo que proporciona límites (casi) óptimos para el aprendizaje agnóstico de funciones umbral polinómicas en el modelo de consultas estadísticas.
Este artículo presenta el primer avance en la resolución del problema abierto sobre la existencia de un algoritmo -competitivo para la retransmisión de paquetes en una red lineal, demostrando que un algoritmo codicioso alcanza una relación de competitividad de $2-2^{1-k}4/3$.
Este artículo presenta un nuevo algoritmo con un "método de anticipación" para reconocer hipergrafos con rango transversal y enumerar sus conjuntos de golpeo mínimos, mejorando la dependencia temporal respecto al número de aristas y estableciendo que una reducción adicional de la complejidad es equivalente a avances fundamentales en la teoría de hipergrafos conformales y la enumeración de conjuntos independientes.
Este artículo demuestra una versión más débil de una conjetura reciente sobre la descomposición arbórea de grafos que excluyen ciertos menores inducidos, estableciendo que tales grafos admiten una descomposición donde la independencia a cierta distancia de cada bolsa está acotada por una función polilogarítmica.
Este artículo propone un método secuencial para generar, enumerar y muestrear grafos bipartitos, dirigidos y no dirigidos con secuencias de grados prescritas, estableciendo condiciones de factibilidad global y demostrando una escalabilidad superior a métodos existentes en instancias grandes.
Este artículo establece una dicotomía de complejidad para el problema de reconfiguración de conjuntos dominantes a distancia , demostrando que es resoluble en tiempo polinómico en grafos divididos para y diseñando un algoritmo lineal en árboles, mientras que se mantiene como completo para PSPACE en grafos planares de grado máximo tres y en grafos bipartitos o cordales.
Este trabajo presenta un nuevo algoritmo de muestreo aleatorio con reemplazo para flujos de datos que permite obtener en una sola pasada una muestra ponderada representativa del conjunto visto hasta el momento, garantizando su corrección y eficiencia mediante pruebas formales y análisis experimental.
Esta carta presenta un método novedoso que utiliza acumuladores en cascada para calcular eficientemente sumas ponderadas con potencias de índices temporales en tiempo real, eliminando la necesidad de almacenar bloques de datos completos y reduciendo drásticamente el costo computacional de multiplicaciones.
Este artículo estudia la complejidad parametrizada del problema del camino más corto con restricciones disyuntivas positivas, estableciendo la NP-completitud de su versión clásica y presentando resultados de kernelización y tractabilidad parametrizada fija para diferentes parámetros estructurales y de tamaño de solución.