장벽서지만 확인
Beyond Natural Proofs: Hardness Magnification and LocalityLijie Chen, Shuichi Hirahara, Igor Carboni Oliveira, Ján Pich, Ninad Rajgopal, Rahul Santhanam · 2022Journal of the ACM 69(4), 2022 (논문별 쪽 1–49) · 학회 발표 ITCS 2020 (LIPIcs 151), 70:1–70:48약한 회로에 대한 작은 하한을 큰 분리로 키우는 「어려움 증폭」 접근이 자연 증명 장벽은 비켜 갈 수 있어도 「국소성 장벽」에 걸림을 보인 논문이다. 증폭 정리가 다루는 문제들은 입력 수가 작은 오라클 문을 단 아주 효율적인 회로를 가지는데, 기존 하한 기법은 그런 오라클이 달린 회로에도 그대로 통한다는 것이 장벽의 내용이다. 세 장벽 뒤에 나온 새 장애를 다루려는 글(2-2)과 메타 복잡도 접근(2-3)을 다루는 글이 인용한다.
확인:학술지판은 Crossref 등록 기록(초록 포함)으로, 학회판은 DataCite 의 DOI 등록 기록으로 확인했다.