45 artículos
Este artículo demuestra que el problema de decisión de aproximación del radio de cobertura en retículos bajo la norma es NP-duro para una función explícita de factor de aproximación cuando supera un umbral de aproximadamente 35.31, estableciendo así la primera prueba de dureza para este problema en normas explícitas.
Este trabajo cierra la brecha de complejidad en el problema d-QBF con pocas variables existenciales demostrando que la dependencia doblemente exponencial es óptima bajo la conjetura ETH para fórmulas generales, mientras que para el caso restringido de dos bloques cuantificadores se presenta un algoritmo casi óptimo con una dependencia exponencial simple.
El artículo presenta resultados mejorados para cinco números de Ramsey clásicos y demuestra la eficacia de AlphaEvolve, un agente de mutación de código basado en modelos de lenguaje, como un metaalgoritmo único capaz de generar algoritmos de búsqueda que superan o igualan los límites inferiores conocidos en este campo.
Este artículo establece explícitamente que el tamaño óptimo de un circuito cambia como máximo en ante una perturbación de un punto en su tabla de verdad, extendiendo el resultado a distancias de Hamming generales y verificando su optimalidad exhaustiva para mediante un análisis SAT en la base AIG.
Este artículo propone un marco unificador que clasifica los problemas de conteo no resueltos en redes tensoriales booleanas en nueve casos basados en grupos finitos, resolviendo el caso de grupos cíclicos de orden superior y avanzando en la comprensión de las barreras algebraicas que impiden una dicotomía completa.
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.
El artículo argumenta que la ventaja cuántica ya se ha logrado, respaldando esta afirmación con experimentos previos y proponiendo los siguientes pasos para la teoría y la experimentación en este campo.
Este artículo demuestra que el problema de despejar o sobrevivir en Tetris es NP-duro para cualquier tipo de tetrominó excepto el cuadrado (O) bajo el sistema de rotación estándar, refutando una conjetura de 23 años sobre el caso de las piezas I, mientras que presenta algoritmos de tiempo polinómico para dominós y piezas de 1×k bajo ciertas condiciones.
Bajo la suposición de la seguridad del problema de Aprendizaje con Errores (LWE), el artículo demuestra que ningún algoritmo cuántico puede automatizar débilmente el sistema de prueba -Frege, estableciendo así la primera conexión entre la computación cuántica y la búsqueda de pruebas proposicionales.
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.
El artículo presenta un algoritmo de tiempo polinómico para probar el isomorfismo de extensiones de grupos abelianos por grupos generados por elementos, generalizando resultados previos sobre extensiones coprimas y centrales, y destacando una nueva técnica para calcular el grupo de unidades de un anillo finito.
Este artículo compara tres semánticas de satisfacibilidad para la lógica cuántica en espacios de Hilbert de dimensión fija, demostrando que la semántica estándar es estrictamente más expresiva que las semánticas de proyectores conmutantes globales y parcial-booleanas, y proporcionando una fórmula explícita que separa estas clases.
Este artículo establece un marco de cambio de base que permite extender resultados sobre funciones tensoriales a cuerpos generales, demostrando que el rango de corte para tensores 3D está acotado linealmente por el rango geométrico y es cuasisupermultiplicativo sobre cualquier cuerpo.
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 trabajo presenta algoritmos deterministas eficientes para encontrar y recuperar factores dispersos de polinomios con grado individual acotado, estableciendo nuevas cotas estructurales y mejorando los tiempos de ejecución anteriores en diversos contextos de campos.
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.
Este artículo presenta una propuesta alternativa para demostrar una ventaja en información cuántica basada en juegos CHSH repetidos en paralelo, que utiliza una medida de memoria informacional en lugar del recuento de qubits y ofrece un verificador eficiente y un probador cuántico robusto al ruido superior al protocolo experimental previo de Kretschmer et al.
El artículo demuestra que la brecha entre el tamaño mínimo de un circuito booleano y el de una fórmula en la base AIG es siempre 0 o 1, estableciendo que el uso compartido de puertas solo es necesario cuando hay al menos variables esenciales y que, cuando la brecha es 1, surge exclusivamente de un único nodo con fan-out 2.
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.
El artículo demuestra que ciertos problemas de decisión polinomial con especificaciones de ejecución causal intrínseca requieren tiempo lineal y no admiten aceleración asintótica mediante computación paralela, estableciendo así una brecha fundamental entre el paralelismo lógico y la ejecutabilidad causal.