Daily Arxiv

Esta página recopila y organiza artículos sobre inteligencia artificial publicados en todo el mundo.
La información aquí presentada se resume utilizando Google Gemini y el sitio se gestiona sin fines de lucro.
Los derechos de autor de los artículos pertenecen a sus autores y a las instituciones correspondientes; al compartir el contenido, basta con citar la fuente.

Generación reforzada de estructuras combinatorias: aplicaciones a la teoría de la complejidad

Created by
  • Haebom

Autor

Ansh Nagda, Prabhakar Raghavan, Abhradeep Thakurta

Describir

Este artículo explora el uso de la tecnología de IA para descubrir nuevas estructuras combinatorias que mejoran las limitaciones existentes de los algoritmos eficientes. Específicamente, utilizamos AlphaEvolve (un agente de codificación LLM) para estudiar la dureza promedio de los casos para MAX-CUT y los Conjuntos MAX-Independientes, así como la dureza aproximada del peor caso para MAX-k-CUT. De esta manera, mejoramos los límites superior e inferior del algoritmo de autenticación para MAX-CUT y los Conjuntos MAX-Independientes, y obtenemos nuevos resultados de probabilidad no aproximada para MAX-4-CUT y MAX-3-CUT. Además, proponemos un método para mejorar eficientemente el proceso de verificación utilizando AlphaEvolve.

Takeaways, Limitations

Takeaways:
Aprovechar la tecnología de IA (AlphaEvolve) para producir nuevos resultados que amplíen los límites de los algoritmos existentes.
Mejoras de límites para MAX-CUT y MAX-Independent Set.
Presentamos nuevos resultados de viabilidad no aproximados para MAX-4-CUT y MAX-3-CUT.
Proporcionar criterios para evaluar cómo la IA contribuye al desarrollo de pruebas.
Limitations:
Se necesita una cantidad significativa de tiempo para verificar los resultados generados por AlphaEvolve.
Los resultados de MAX-3-CUT están por debajo del mejor rendimiento (en comparación con el método PCP personalizado).
👍