45 artículos
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 .
Este trabajo establece nuevas separaciones entre circuitos cuánticos de profundidad constante (incluyendo aquellos con Toffoli de control ilimitado y consejos cuánticos) y circuitos clásicos , demuestra que los circuitos cuánticos de profundidad constante con conjuntos de puertas infinitos pueden implementar puertas umbral, y prueba que los sistemas de dimensión superior no ofrecen ventajas adicionales en este contexto.
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.
El artículo demuestra que determinar si una estrategia computable es ganadora en el juego de cartas Yu-Gi-Oh! es un problema indecidible y, de hecho, completo para la clase , mediante reducciones que utilizan mazos legales del juego.
Este artículo presenta una nueva visión unificada de la asimetría entre generación y reconocimiento en la teoría de lenguajes formales, identificando seis dimensiones divergentes (incluyendo dos nuevas: direccionalidad y temporalidad) para desmitificar la noción de que la generación es siempre fácil y el análisis siempre difícil, y conectando estas diferencias con el marco de la sorpresa en el procesamiento del lenguaje natural y las arquitecturas de los modelos de lenguaje grandes.
Esta tesis de habilitación presenta algoritmos eficientes en tiempo y espacio para el cálculo polinómico, abordando tanto la complejidad de operaciones fundamentales bajo restricciones de memoria como el desarrollo del primer algoritmo cuasi-lineal para la interpolación de polinomios dispersos y el estudio de problemas de factorización en este contexto.
Este artículo establece una condición necesaria y suficiente para la simulabilidad clásica de circuitos cuánticos seguidos de un procesamiento posterior clásico disperso, demostrando que ciertos circuitos cuánticos intrínsecamente difíciles de simular se vuelven simulables bajo estas condiciones y proporcionando un algoritmo probabilístico eficiente para el caso de profundidad constante.
Este artículo reinterpreta la búsqueda de testigos en NP desde una perspectiva de teoría de la información, demostrando que en un modelo de sondeo de igualdad sin estructura, la acumulación de información es insuficiente para la recuperación fiable, lo que revela un origen informacional fundamental para la complejidad exponencial de la búsqueda.
Este artículo demuestra que el problema de Máximo List H-Coloreo Parcial es resoluble en tiempo polinómico en grafos libres de para cualquier grafo fijo , resolviendo así una cuestión abierta y mejorando algoritmos previos.
Este artículo estudia la complejidad de la representación de fórmulas CNF en Decision DNNF restringido, estableciendo límites inferiores para modelos como -OBDD, analizando la operación Apply e introduciendo el modelo Structured -FBDD como una alternativa eficiente para fórmulas de ancho de árbol de incidencia acotado.
Este artículo presenta algoritmos clásicos eficientes para los problemas y de Solución Entera Constrained, demostrando que no existe una ventaja cuántica exponencial sobre los métodos clásicos, lo que invalida el hallazgo previo de Chen, Liu y Zhandry.
Este artículo presenta un algoritmo de aproximación con una relación de $4/3O(m\sqrt{n})$ que supera a los métodos anteriores basados en programación lineal.
Este artículo presenta una clasificación completa de la complejidad computacional distribuida para problemas de optimización local en ciclos dirigidos, identificando cuatro clases de complejidad posibles tanto para modelos deterministas como aleatorizados, y ofrece un metaalgoritmo eficiente para determinar automáticamente la clase de complejidad y sintetizar un algoritmo distribuido óptimo para cualquier problema de este tipo.
Este artículo establece que las RNN lineales son altamente paralelizables porque equivalen a circuitos aritméticos de profundidad logarítmica, mientras que las RNN no lineales enfrentan barreras fundamentales de paralelización al poder resolver problemas completos en P, ofreciendo así una base teórica para equilibrar expresividad y eficiencia en arquitecturas de modelos de lenguaje.
Este trabajo aborda la generalización de la selección justa de los mejores candidatos a múltiples grupos protegidos y la minimización de la disparidad respecto a una función de referencia, demostrando la complejidad computacional del problema pero proponiendo una solución eficiente y robusta para casos con pocos grupos y valores pequeños de , que incluye una nueva medida de pérdida de utilidad y valida su eficacia mediante experimentos en conjuntos de datos reales.
Este artículo presenta la implementación y simulación de algoritmos cuánticos basados en la búsqueda de Grover para resolver el problema de coordinación de señales de red (NSC) y su variante robusta, logrando una aceleración cuadrática incluso cuando la precisión de robustez decae polinomialmente con el tamaño de la red.
Este artículo presenta un algoritmo eficiente basado en resultantes que explota la dispersión estructurada de un sistema polinómico sobre un cuerpo finito para resolverlo significativamente más rápido que los métodos de fuerza bruta o las bases de Gröbner estándar.
El artículo establece una correspondencia exacta entre el poder computacional de las redes neuronales gráficas recurrentes y los circuitos aritméticos recurrentes sobre números reales, demostrando que ambos modelos pueden simularse mutuamente.
Este artículo presenta un algoritmo de tiempo $2^{O(k \log k)} nk$, y demuestra que esta dependencia es óptima bajo la Hipótesis del Tiempo Exponencial (ETH).
Este trabajo demuestra que la conjetura de Aaronson-Ambainis es cierta para una fracción no despreciable de restricciones aleatorias de polinomios de grado con varianza suficiente, al probar que existe una coordenada con influencia significativa bajo dichas restricciones.