접근서지만 확인
Pseudorandomness and the Minimum Circuit Size ProblemRahul Santhanam · 2020ITCS 2020 (11th Innovations in Theoretical Computer Science Conference), LIPIcs 151, 68:1–68:26일방향 함수의 존재를 최소 회로 크기 문제(MCSP)의 평균 경우 어려움 위에 세울 수 있는지를 탐구한 논문이다. 저자가 내놓은 보편성 추측 아래에서는 일방향 함수의 존재, 자연 증명의 부재, 회로 학습의 어려움, MCSP 의 무오류 평균 경우 어려움이 서로 같아진다. 암호·학습·자연 증명 장벽이 메타 복잡도에서 만난다는 그림을 인용하려는 글에 맞다. 무조건적인 동치는 liu-pass-2020 을 본다.
확인:DataCite 의 DOI 등록 기록으로 제목·저자·총서 권·쪽을 확인하고 같은 기록의 초록을 읽었다.