87 artículos
Este trabajo presenta un esquema genérico para la estimación de momentos en flujos de datos multidimensionales que utiliza el teorema de representación de Lévy-Khintchine y procesos de Lévy para unificar construcciones existentes y demostrar la tratabilidad de funciones casi periódicas previamente no clasificadas.
Este artículo introduce un nuevo tipo de subgradiente basado en funciones de Busemann para espacios de Hadamard, permitiendo la generalización de métodos estocásticos e incrementales de subgradiente con garantías de complejidad para problemas de optimización convexa en espacios métricos no lineales como el espacio de árboles BHV.
El artículo demuestra que un método exacto sencillo resuelve casi todas las instancias clásicas de referencia del problema del viajante con ventanas de tiempo en menos de diez segundos, lo que indica que estas ya no son representativas para evaluar algoritmos ni para diseñar conjuntos de entrenamiento difíciles para aprendizaje automático.
Este artículo presenta el algoritmo de Alineamiento Temporal Elástico, que resuelve el problema de emparejamiento de series temporales en espacios métricos arbitrarios utilizando una penalización de estiramiento basada en el núcleo de Hellinger y logra una complejidad computacional cúbica.
El artículo presenta bsort, un algoritmo de ordenamiento no basado en comparaciones para enteros y números de punto flotante que unifica estos casos mediante una derivación del quicksort binario, logrando un tiempo de ejecución asintótico de y un espacio auxiliar de , con un rendimiento competitivo en datos de tamaño de palabra pequeño.
Este trabajo presenta un algoritmo de flujo de datos de una sola pasada que logra un factor de aproximación esperado de 0.7401 para el problema de selección de intervalos unitarios bajo un orden de entrada aleatorio, superando la barrera de 2/3 establecida para el orden adversario, mientras demuestra que mejorar más allá de 8/9 o lograr una aproximación superior a 2/3 con alta probabilidad requiere espacio lineal en el tamaño de la entrada.
Este artículo presenta un algoritmo de aproximación en tiempo polinomial (PTAS) para el problema de la 2-matching ponderada sin triángulos, superando la mejor aproximación previa de 2/3 mediante un método de búsqueda local y un análisis no trivial.
Este trabajo presenta un nuevo algoritmo de minería de subcadenas frecuentes con privacidad diferencial que mantiene garantías de error cercanas a la óptima mientras reduce drásticamente la complejidad de tiempo y espacio en comparación con enfoques anteriores, haciendo el proceso escalable.
Este artículo presenta un nuevo protocolo para el problema de expertos distribuidos que mejora los límites anteriores al lograr un arrepentimiento reducido con una cantidad mínima de comunicación entre servidores.
Este artículo estudia el problema de emparejamiento no cruzado ponderado en línea en el plano euclidiano, demostrando que aunque los algoritmos deterministas no logran una razón competitiva no trivial, es posible alcanzar una razón constante mediante aleatorización, además de analizar variantes con revocabilidad, puntos colineales y complejidad de asesoramiento.
Este trabajo presenta y demuestra la corrección de un algoritmo automatizado que enumera exhaustivamente todos los pares críticos en sistemas de reescritura de diagramas de cadenas dentro de categorías monoidales simétricas sin estructura de Frobenius, utilizando la manipulación concreta de hipergrafos.
Este trabajo mejora el tiempo de ejecución de los algoritmos de aproximación para los problemas de -mediana y -medias en espacios euclídeos de baja dimensión a $2^{\tilde{O}(1/\varepsilon)^{d-1}} \cdot n \cdot \text{polylog}(n)$ y demuestra que este límite es casi óptimo bajo la Hipótesis del Tiempo Exponencial con Brecha para 3-SAT.
Este trabajo demuestra que siempre existe un emparejamiento crítico y relajadamente estable en el escenario de muchos-a-muchos con empates y cuotas, y presenta un algoritmo de aproximación de en tiempo polinomial para maximizar su cardinalidad, a pesar de que encontrar el máximo es NP-duro.
Este trabajo demuestra que, al espaciar el modelo SYK, existe una separación probada entre la complejidad clásica y cuántica para encontrar estados fundamentales aproximados, ya que los algoritmos cuánticos de Hastings-O'Donnell siguen logrando una aproximación constante mientras que los estados gaussianos clásicos fallan en hacerlo cuando el parámetro de espaciamiento es suficientemente grande.
Este trabajo presenta un esquema para la estimación diferencialmente privada de funciones de caja negra que equilibra la eficiencia estadística y la eficiencia de oráculo, complementado con cotas inferiores que demuestran su cercanía a la optimalidad.
Este artículo presenta la Teoría del Espacio de Exploración (EST), un marco formal basado en retículos que adapta la Teoría del Espacio de Conocimiento para los sistemas de recomendación basados en ubicación, garantizando matemáticamente que las sugerencias respeten las dependencias semánticas y de prerequisitos entre puntos de interés.
Este artículo presenta el primer marco formal para el aprendizaje por refuerzo multiagente cooperativo con recompensas submodulares, proponiendo algoritmos con garantías teóricas que superan la maldición de la dimensionalidad y logran aproximaciones de 1/2 tanto en entornos de dinámica conocida como desconocida.
Este artículo propone las nuevas clases de redes -cortables como una alternativa computacionalmente útil y reconocible en tiempo polinómico a las redes orientables a árbol-hijo, demostrando que permiten resolver eficientemente problemas como la contención de árboles que son intratables en otras clases de redes filogenéticas no enraizadas.
Este artículo presenta un nuevo método automatizado que combina la sustitución con una búsqueda de retroceso para demostrar que la complejidad bilineal de multiplicar matrices de $3 \times 3\mathbb{F}_2$ es al menos 20, superando la antigua cota inferior de 19.
Este artículo presenta el primer método para aproximar contracciones de redes tensoriales arbitrarias, incluidas las cíclicas, y propone una segunda técnica para redes acíclicas que reduce la complejidad computacional de exponencial a polinómica en función del número de contracciones.