부분 결과서지만 확인
Almost optimal lower bounds for small depth circuitsJohan Håstad · 1986STOC 1986 (Proceedings of the 18th Annual ACM Symposium on Theory of Computing), 6–20쪽 · 확장판 Randomness and Computation (Advances in Computing Research 5, S. Micali 엮음, JAI Press, 1989), 143–170쪽상수 깊이 회로가 패리티를 계산하려면 지수에 가까운 크기가 필요함을 보인 논문이다. 무작위로 변수 일부를 고정하면 「작은 OR 들의 AND」를 「작은 AND 들의 OR」로 바꿀 수 있다는 핵심 보조정리(전환 보조정리)가 여기서 나온다. 깊이 k 에서는 다항 크기로 되지만 깊이 k−1 에서는 지수 크기가 필요한 함수가 있음도 보인다. 회로 하한 기법을 직접 배우려는 독자에게 권한다.
확인:저자 공개본 주소를 열어 제목·저자·실린 곳을 확인했으나 본문을 읽었다는 기록은 없음. 내용은 Håstad 학위 논문 1장, Aaronson 2017, Arora–Barak 공개 초고 13장으로 확인.원문 주소 (www.csc.kth.se)이 카드를 붙인 자료 3