부분 결과서지만 확인
Monotone Circuits for Connectivity Require Super-Logarithmic DepthMauricio Karchmer, Avi Wigderson · 1990SIAM Journal on Discrete Mathematics 3(2), 255–265쪽 (1990) · 학회 발표 STOC 1988 (Proceedings of the 20th Annual ACM Symposium on Theory of Computing), 539–550쪽그래프의 두 꼭짓점이 이어져 있는지를 판정하는 단조 회로의 깊이가 Ω(log² n) 이어야 함을 보인 논문이다. 회로의 깊이를 두 사람이 주고받는 통신의 양으로 바꿔 재는 방법(Karchmer–Wigderson 게임)이 여기서 나온다. 통신 복잡도로 회로 하한에 다가가는 접근을 소개하는 글의 출전이다.
확인:학술지판과 학회판 모두 Crossref 의 DOI 등록 기록으로 확인하고 학술지판 기록의 초록을 읽었다.