부분 결과서지만 확인
An Average-Case Depth Hierarchy Theorem for Boolean CircuitsBenjamin Rossman, Rocco A. Servedio, Li-Yang Tan · 2015FOCS 2015 (56th Annual IEEE Symposium on Foundations of Computer Science), 1030–1048쪽 · 학술지판: Johan Håstad, Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan, Journal of the ACM 64(5), 2017 (같은 제목 · 논문별 쪽 1–27) · arXiv:1504.03398깊이 d 의 작은 식으로 계산되지만 깊이 d−1 회로로는 절반을 조금 넘는 입력에서 맞히기조차 지수 크기가 드는 명시적 함수가 있음을 보인 논문이다. 따름 결과로, 무작위 오라클에 대해 다항 위계가 확률 1 로 무한하다는 오랜 추측이 확인되었다. 상대화된 세계에서 무엇이 성립하는지(2-2)와 상수 깊이 회로 하한(2-4)을 다루는 글이 인용한다.
확인:학회판과 학술지판(DOI 10.1145/3095799)은 Crossref 등록 기록으로, 초록은 Crossref 와 arXiv 초록 페이지로 확인했다.