45 artículos
Este trabajo presenta SCORE, un lenguaje diseñado para manipular variables y pilas, y demuestra mediante un asistente de prueba que sus operaciones pueden interpretarse como biyecciones totales, superando así las limitaciones de las estrategias de reversibilización convencionales que generan funciones parciales.
Este trabajo demuestra que cualquier código localmente decodificable relajado (RLDC) con error de sonido suficientemente bajo y un decodificador no adaptativo puede transformarse en un código localmente decodificable (LDC) estándar con parámetros comparables, generalizando resultados previos al eliminar la restricción de linealidad y derivar mejores cotas inferiores para RLDCs, RLCCs y pruebas de cercanía verificables probabilísticamente (PCPPs).
Este libro ofrece una visión general de los avances recientes en la lista de decodificación de códigos de Reed-Solomon y otras familias de códigos polinómicos, destacando el desarrollo de algoritmos eficientes que alcanzan la capacidad teórica de información con listas óptimas y tiempos de ejecución casi lineales o sublineales.
Este trabajo presenta un algoritmo aleatorio de tiempo polinomial que resuelve el problema de aprendizaje de determinantes de lectura única (ROD) al demostrar su equivalencia con una versión de caja negra del Problema de Asignación de Menores Principales (PMAP) y resolver este último mediante la propiedad de extensión de rango uno.
Este artículo propone un algoritmo cuántico basado en caminatas cuánticas MNRS para la prueba de isomorfismo aproximado de grafos que alcanza una complejidad de consulta de O(n^{3/2} log n/ε), demostrando una ventaja polinomial genuina sobre los métodos clásicos mediante un límite inferior de Ω(n^2).