본 논문은 AI 기술을 활용하여 알고리즘의 효율성 한계를 개선하는 새로운 조합 구조를 발견하는 연구를 진행했다. 특히, LLM 코딩 에이전트인 AlphaEvolve를 사용하여 두 가지 설정을 연구하였다. 첫째, 무작위 3-정규 및 4-정규 그래프에서 MAX-CUT 및 MAX-Independent Set에 대한 인증 알고리즘의 평균 케이스 어려움에 대한 거의 최적의 상한 및 (조건부) 하한을 얻기 위해 Kunisky와 Yu의 최근 결과를 개선하였다. 개선된 하한은 AlphaEvolve를 사용하여 최대 163개의 노드에 대해 거의 극단적인 Ramanujan 그래프를 구성함으로써 얻었다. 또한, 분석적 논증을 통해 상한을 강화하여 이러한 문제의 계산 복잡성을 소수점 셋째 자리의 오차까지 해결하였다. 둘째, AlphaEvolve를 사용하여 새로운 가젯 감소를 발견하여 MAX-4-CUT 및 MAX-3-CUT에 대한 새로운 근사 불가능성 결과를 얻었다. MAX-4-CUT 결과는 0.9883의 최첨단 기술을 개선하였고, MAX-3-CUT 결과는 0.9853의 현재 최고 가젯 기반 근사 불가능성 결과를 개선하였지만, 가젯 감소가 아닌 사용자 지정 PCP에 의존하는 16/17의 최첨단 기술을 개선하지는 못했다. AlphaEvolve가 생성한 후보 구조를 검증하는 데는 종종 지수 시간이 필요하여 어려움을 겪었으며, AlphaEvolve 자체를 사용하여 검증 절차를 최대 10,000배까지 가속화하여 이러한 문제를 해결했다. 마지막으로, 증명 개발에서 AI의 지원을 평가하기 위한 기준에 대해 논의한다.
