[1] Adi Akavia, Andrej Bogdanov, Siyao Guo, Akshay Kamath, Alon Rosen. AC$^0 circ mathsf{MOD}_2$에서 약한 의사 난수 함수 후보. 이론 컴퓨터 과학의 혁신에 관한 제5차 회의 회보, ITCS '14, 251–260페이지, 2014.
https : / /doi.org/ 10.1145 / 2554797.2554821

[2] Miklos Ajtai와 Michael Ben-Or. 확률적 상수 깊이 계산에 대한 정리. 컴퓨팅 이론에 관한 제16회 연례 ACM 심포지엄, STOC '84, 페이지 471–474, 1984.
https : / /doi.org/ 10.1145 / 800057.808715

[3] Andris Ambainis, Andrew M. Childs, Ben W. Reichardt, Robert Špalek, Shengyu Zhang 크기가 $N$인 AND-OR 공식은 양자 컴퓨터에서 $N^{1/ 2 + o(1)}$ 시간에 계산할 수 있습니다. 컴퓨팅에 관한 SIAM 저널, 39(6):2513–2530, 2010.
https : / /doi.org/ 10.1137 / 080712167

[4] Charles H. Bennett, Ethan Bernstein, Gilles Brassard, Umesh Vazirani. 양자 컴퓨팅의 강점과 약점. 컴퓨팅에 관한 SIAM 저널, 26(5):1510–1523, 1997.
https : / /doi.org/ 10.1137 / S0097539796300933

[5] 로버트 빌스, 해리 버먼, 리처드 클리브, 미셸 모스카, 로날드 드 울프. 다항식에 의한 양자 하한. ACM 저널, 48(4):778–797, 2001.
https : / /doi.org/ 10.1145 / 502090.502097

[6] Michel Boyer, Gilles Brassard, Peter Høyer 및 Alain Tapp. 양자 검색의 엄격한 경계. Fortschritte der Physik, 46(4-5):493–505, 1998.
[7] 해리 버먼, 리처드 클리브, 로날드 드 울프, 크리스토프 잘카. 작은 오류와 오류가 없는 양자 알고리즘의 경계. 40년, 컴퓨터 과학 기초에 관한 358차 연례 심포지엄, 368–1999페이지.
https:// / doi.org/ 10.1109/ sffcs.1999.814607

[8] Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler 및 Prashant Nalini Vasudevan. 통계적 제로 지식의 힘. 제58회 컴퓨터 과학 기초에 관한 연례 심포지엄(FOCS 2017), 페이지 708–719, 2017.
https : / /doi.org/10.1109/focs.2017.71

[9] 해리 버먼과 로날드 드 울프. 복잡성 측정 및 의사 결정 트리 복잡성: 설문 조사. 이론 컴퓨터 과학, 288(1):21–43, 2002.
https:/​/​doi.org/​10.1016/​S0304-3975(01)00144-X

[10] 마크 번, 로빈 코타리, 저스틴 탈러. 다항식 방법의 역습: 이중 다항식을 통한 엄격한 양자 쿼리 경계. 컴퓨팅 이론에 관한 제50회 연례 ACM SIGACT 심포지엄, STOC 2018, 297–310페이지, 2018년 회보.
https : / /doi.org/ 10.1145 / 3188745.3188784

[11] 마크 번, 로빈 코타리, 저스틴 탈러. 공유 입력으로 구성된 함수에 대한 양자 알고리즘 및 근사 다항식. 이산 알고리즘(SODA)에 대한 2019 연례 ACM-SIAM 심포지엄 회보, 662–678페이지, 2019.
https : / /doi.org/ 10.1137 / 1.9781611975482.42

[12] 폴 빔과 위다드 마흐무치. AC$^0$의 양자 쿼리 복잡성. 양자 정보 및 계산, 12(7-8):670–676, 2012.

[13] Harry Buhrman, Ilan Newman, Hein Röhrig, Ronald de Wolf. 강력한 다항식 및 양자 알고리즘. 컴퓨팅 시스템 이론, 40(4):379–395, 2007.
https : / /doi.org/ 10.1007 / s00224-006-1313-z

[14] 여호슈아 브룩과 로만 스몰렌스키. 다항식 임계값 함수, AC$^0$ 함수 및 스펙트럼 규범. 컴퓨팅에 관한 SIAM 저널, 21(1):33–42, 1992.
https : / /doi.org/ 10.1137 / 0221003

[15] 마크 번과 저스틴 탈러. AC$^0$의 대략적인 정도에 대한 거의 최적의 하한입니다. IEEE 58th Annual Symposium on Foundations of Computer Science(FOCS 2017), 1년 12~2017페이지.
https : / /doi.org/10.1109/FOCS.2017.10

[16] 마크 번과 저스틴 탈러. 게스트 칼럼: 고전 및 양자 컴퓨팅의 대략적인 학위. SIGACT 뉴스, 51(4):48–72, 2021년 XNUMX월.
https : / /doi.org/ 10.1145 / 3444815.3444825

[17] Andrew M. Childs, Richard Cleve, Stephen P. Jordan, David Yonge-Mallo. NAND 트리를 위한 이산 쿼리 양자 알고리즘. 컴퓨팅 이론, 5:119–123, 2009.
https : / /doi.org/ 10.4086 / toc.2009.v005a005

[18] Mahdi Cherghchi, Elena Grigorescu, Brendan Juba, Karl Wimmer, Ning Xie. 부울 내부 곱의 AC0 $circ$ MOD2 하한. LIPIcs-Leibniz International Proceedings in Informatics, 55권. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016.
https : / /doi.org/10.4230/LIPIcs.ICALP.2016.35

[19] 크리스 칼라브로, 러셀 임팔리아조, 라마모한 파투리. 작은 깊이 회로의 만족 가능성의 복잡성. 매개변수화된 정확한 계산에 대한 국제 워크숍, 75–85페이지, 2009년.
https:/​/​doi.org/​10.1007/​978-3-642-11269-0_6

[20] 앤드류 M. 차일즈, 쉘비 키멜, 로빈 코타리. 다 읽기 수식의 양자 쿼리 복잡성. 알고리즘에 관한 제20회 유럽 연례 심포지엄(ESA 2012), 337–348페이지, 2012.
https:/​/​doi.org/​10.1007/​978-3-642-33090-2_30

[21] Shiva Chaudhuri와 Jaikumar Radhakrishnan. 회로 복잡성의 결정론적 제한. 컴퓨팅 이론에 관한 제96회 연례 ACM 심포지엄의 회보, STOC '30, 36년 1996-XNUMX페이지.
https : / /doi.org/ 10.1145 / 237814.237824

[22] 길 코헨과 이고르 신카르. 패리티 DNF의 복잡성. 이론 컴퓨터 과학의 혁신에 관한 2016 ACM 회의 회보, 47년 58~2016페이지.
https : / /doi.org/ 10.1145 / 2840728.2840734

[23] Ning Ding, Yanli Ren, Dawu Gu. PAC 학습 깊이-3 AC$^0$ 경계 상위 패닌 회로. 알고리즘 학습 이론에 관한 제28회 국제 회의 회보, 기계 학습 연구 회보 76권, 667–680페이지, 2017. URL: http:// / proceedings.mlr.press/ v76/ ding17a.html.
http:// / proceedings.mlr.press/ v76/ ding17a.html

[24] 마이클 에즈라와 론 D. 로스블럼. 작은 회로는 효율적인 Arthur-Merlin 프로토콜을 의미합니다. 기술 보고서 ​​TR21-127, ECCC(Electronic Colloquium on Computational Complexity), 2021. URL: https:// / eccc.weizmann.ac.il/ report/ 2021/ 127/ .
https : / /eccc.weizmann.ac.il/ 보고서 / 2021 / 127 /

[25] 에드워드 파리, 제프리 골드스톤, 샘 거트만. Hamiltonian NAND 트리를 위한 양자 알고리즘. 컴퓨팅 이론, 4(1):169–190, 2008.
https : / /doi.org/ 10.4086 / toc.2008.v004a008

[26] 유발 필무스, 하메드 하타미, 스티븐 하일만, 엘캐넌 모셀, 라이언 오도넬, 수샨트 사크데바, 앤드류 완, 칼 위머. 컴퓨터 과학의 실제 분석: 미해결 문제 모음, 2014. URL: https:// / simons.berkeley.edu/ sites/ default/ files/ openprobsmerged.pdf.
https:// / simons.berkeley.edu/ sites/ default/ files/ openprobsmerged.pdf

[27] 로브 K. 그로버. 데이터베이스 검색을 위한 빠른 양자 역학 알고리즘. 컴퓨팅 이론에 관한 제 96회 연례 ACM 심포지엄의 회보, STOC '212, 219–1996페이지, XNUMX.
https : / /doi.org/ 10.1145 / 237814.237866

[28] Peter Høyer, Troy Lee, Robert Špalek. 음수 가중치는 적을 더 강하게 만듭니다. 제39회 컴퓨팅 이론 심포지엄의 회보(STOC 2007), 526–535페이지, 2007.
https : / /doi.org/ 10.1145 / 1250790.1250867

[29] Adam Tauman Kalai, Adam R. Klivans, Yishay Mansour 및 Rocco A. Servedio. 불가지론적으로 하프스페이스를 학습합니다. 컴퓨팅에 관한 SIAM 저널, 37(6):1777–1805, 2008.
https : / /doi.org/ 10.1137 / 060649057

[30] Adam Klivans, Pravesh Kothari 및 Igor C. Oliveira. 학습 알고리즘을 사용하여 하드 함수를 구성합니다. IEEE Conference on Computational Complexity(CCC 2013), 86년 97~2013페이지.
https : / /doi.org/10.1109/CCC.2013.18

[31] Michal Kouckky, Clemens Lautemann, Sebastian Poloczek, Denis Therien. Ehrenfeucht-Fraisse 게임을 통한 회로 하한. 계산 복잡성에 관한 제21회 IEEE 연례 회의(CCC 2006), 페이지 190–201, 07년 2006월.
https : / /doi.org/10.1109/CCC.2006.12

[32] 스와스틱 코파티. AC0 하한 및 의사 난수. Rutgers 대학의 "Topics in Complexity Theory and Pseudorandomness(2013년 봄)" 강의 노트. http:// / sites.math.rutgers.edu/ sk1233/ courses/ topics-S13/ lec4.pdf (12년 2018월 2013일에 검색), XNUMX년.
http:// / sites.math.rutgers.edu/ ~sk1233/ courses/ topics-S13/ lec4.pdf

[33] 미할 쿠키. 일반 언어의 회로 복잡성. 컴퓨팅 시스템 이론, 45(4):865–879, 2009.
https : / /doi.org/ 10.1007 / s00224-009-9180-z

[34] Adam R. Klivans 및 Rocco A. Servedio. $2^{{tilde O}(n^{1/ 3})}$ 시간에 DNF 학습. 컴퓨터 및 시스템 과학 저널, 68(2):303–318, 2004.
https : / /doi.org/ 10.1016 / j.jcss.2003.07.007

[35] Michael J. Kearns, Robert E. Schapire, Linda M. Sellie. 효율적인 불가지론적 학습을 향하여. 기계 학습, 17(2-3):115–141, 1994.
https : / //doi.org/ 10.1007 / bf00993468

[36] 이위선, 피터 L. 바틀렛, 로버트 C. 윌리엄슨. 기본 함수의 선형 조합에 대한 효율적인 불가지론적 학습. 계산 학습 이론에 관한 제369차 연례 회의의 회보, 376–1995페이지, XNUMX.
https : / /doi.org/ 10.1145 / 225298.225343

[37] 트로이 리. T. Lee, F. Magniez, M. Santha의 "삼각형 찾기 및 연관성 테스트를 위한 향상된 양자 쿼리 알고리즘" 논문용 슬라이드. http:// / research.cs.rutgers.edu/ troyjlee/ troy_triangle.pdf (11년 2018월 2012일에 검색), XNUMX년에서 볼 수 있습니다.
http:// / research.cs.rutgers.edu/ ~troyjlee/ troy_triangle.pdf

[38] 트로이 리와 아디 슈라이브먼. 통신 복잡성의 하한. 이론적 컴퓨터 과학의 기초 및 추세, 3(4):263–399, 2009.
https : / /doi.org/ 10.1561 / 0400000040

[39] 노암 니산. $n$ 기간의 모노톤 CNF에 대한 가장 짧은 공식입니다. Theoretical Computer Science Stack Exchange, 2011. https:// / cstheory.stackexchange.com/ q/ 7087(버전: 2011-06-23).
https:// / cstheory.stackexchange.com/ q/ 7087

[40] 노암 니산과 마리오 세게디. 부울 함수의 정도에서 실수 다항식으로 기능합니다. 계산 복잡성, 4:301–313, 1994.
https : / /doi.org/ 10.1007 / BF01263419

[41] Igor C. Carboni Oliveira 및 Rahul Santhanam. 학습 알고리즘, 회로 하한 및 의사 난수 간의 음모. 제32회 전산복잡성회의(CCC 2017), 라이프니츠 국제 정보학 회보(LIPIcs) 79권, 18:1–18:49, 2017년.
https : / /doi.org/10.4230/ LIPIcs.CCC.2017.18

[42] 알렉산더 라즈보로프. 논리적 추가가 포함된 완전한 기준에 대한 제한된 깊이 회로의 크기에 대한 하한. 소련 과학 아카데미의 수학 노트, 41(4):333–338, 1987.

[43] 벤 라이차트. 양자 쿼리 알고리즘에 대한 반영. SODA '11: 이산 알고리즘에 관한 제22회 ACM-SIAM 심포지엄의 절차, 560–569페이지, 2011.
https : / /doi.org/ 10.1137 / 1.9781611973082.44

[44] Alexander A. Razborov 및 Alexander A. Sherstov. AC$^0$의 부호 순위. 컴퓨팅에 관한 SIAM 저널, 39(5):1833–1855, 2010.
https : / /doi.org/ 10.1137 / 080744037

[45] Prabhakar Ragde와 Avi Wigderson. 선형 크기 일정 깊이 폴리로그 임계값 회로. 정보 처리 편지, 39(3):143–146, 1991.
https:/​/​doi.org/​10.1016/​0020-0190(91)90110-4

[46] 알렉산더 A. 셔스토프 패턴 매트릭스 방법. 컴퓨팅에 관한 SIAM 저널, 40(6):1969–2000, 2011.
https : / /doi.org/ 10.1137 / 080733644

[47] 알렉산더 A. 셔스토프 양자 통신 및 쿼리 복잡성에 대한 강력한 직접 곱 정리. 컴퓨팅 이론에 관한 제43회 연례 ACM 심포지엄의 회보(STOC 2011), 41년 50~2011페이지.
https : / /doi.org/ 10.1145 / 1993636.1993643

[48] 알렉산더 A. 셔스토프 두 하프스페이스의 교차점은 높은 임계값 차수를 갖습니다. 컴퓨팅에 관한 SIAM 저널, 42(6):2329–2374, 2013.
https : / /doi.org/ 10.1137 / 100785260

[49] 알렉산더 A. 셔스토프 잡음에 강건한 다항식 만들기. 컴퓨팅 이론, 9:593–615, 2013.
https : / /doi.org/ 10.4086 / toc.2013.v009a018

[50] 알렉산더 A. 셔스토프 일정한 깊이의 회로에서 비대칭의 힘. IEEE 56th Annual Symposium on Foundations of Computer Science, 페이지 431–450, 2015.
https : / /doi.org/10.1109/FOCS.2015.34

[51] 알렉산더 A. 셔스토프 알고리즘 다항식. 50년 제2018회 ACM SIGACT 컴퓨팅 이론 심포지엄(STOC 2018)의 회보에서.
https : / /doi.org/ 10.1145 / 3188745.3188958

[52] 라훌 산타남과 스리칸트 스리니바산. 희소화의 한계. Automata, 언어 및 프로그래밍에 관한 국제 콜로키움, 774-785페이지. 스프링거, 2012.
https:/​/​doi.org/​10.1007/​978-3-642-31594-7_65

[53] Rocco A. Servedio 및 Li-Yang Tan. 사소한 비용 절감으로 어떤 회로 등급을 배울 수 있습니까? 8th Innovations in Theoretical Computer Science Conference(ITCS 2017), Leibniz International Proceedings in Informatics(LIPIcs) 67권, 30년 1:30–21:2017.
https : / /doi.org/10.4230/ LIPIcs.ITCS.2017.30

[54] Rocco A Servedio와 에마누엘레 비올라. 강성의 특별한 경우. 기술 보고서 ​​TR12-144, ECCC(Electronic Colloquium on Computational Complexity), 2012. URL: https:// / eccc.weizmann.ac.il/ report/ 2012/ 144/ .
https : / /eccc.weizmann.ac.il/ 보고서 / 2012 / 144 /

[55] 아비샤이 탈. 내적의 이분법 복잡도는 16차입니다. 기술 보고서 ​​TR181-2016, ECCC(Electronic Colloquium on Computational Complexity), 2016. URL: https:// / eccc.weizmann.ac.il/ report/ 181/ XNUMX/ .
https : / /eccc.weizmann.ac.il/ 보고서 / 2016 / 181 /

[56] 아비샤이 탈. 양자 방법을 통한 공식 하한. 컴퓨팅 이론에 관한 제49회 연례 ACM SIGACT 심포지엄(STOC 2017), 1256–1268페이지, 2017.
https : / /doi.org/ 10.1145 / 3055399.3055472

[57] 아비샤이 탈. 개인 커뮤니케이션, 2018.

[58] 레슬리 G. 발리언트. 학습 가능한 이론. ACM 통신, 27(11):1134–1142, 1984년 XNUMX월.
https : / /doi.org/ 10.1145 / 1968.1972