부정 제한 회로 하한 증폭

하위 정보 2

이 자료에 대한 질의 · 보완 · 반론 · 관련 자료 · 메모를 글이나 파일로 더합니다.

보완 2

• 보완#55사실 검토 — 보완 필요
  • 관리자
  • 2026-10-07 13:04
  • AI 도움

  2026-10-07 에 이 글에 적힌 사실(인용한 정리·결과·추측·장벽 서술)을 원 논문·서베이와 대조한 검토입니다. 아이디어가 옳은지가 아니라 사실이 정확한지와, 알려진 결과와 이 글의 제안·판단이 문장에서 갈려 있는지를 봤습니다.

  판정: 보완 필요

  근거(요약):

  1. 4단계의 「자연 증명 장벽이 켜지는 t 의 문턱」은 이미 알려져 있다 — Guo–Malkin–Oliveira–Rosen(TCC 2015)이 PRF 는 log n − O(1) 개의 부정 게이트가 필요하다(Markov 상한과 덧셈 상수 차)를 증명했다. 글은 이를 미해결 조사 과제·독립 결과로 제시하고, 「저부정 회로에는 PRF 가 있다고 믿을 근거가 희박」을 믿음으로 적었다. 실제로는 t < log n − O(1) 에서 PRF 가 없다는 것은 정리이고, 문턱은 사실상 Markov 한계(⌈log₂(n+1)⌉) 바로 아래다 — 「문턱 위 구간」은 상수 개 차이뿐이고 그 구간은 Fischer 에 의해 일반 회로와 같다. 그림 설명(점선 상자 = 4단계에서 추정할 문턱)과 「두 트랙의 나눔」 구도가 이 사실과 맞지 않는다.
  2. 우회 트랙(Williams 의 알고리즘적 방법)이 주는 것은 NEXP·NQP 같은 큰 클래스의 하한이지 NP 완전 문제의 하한이 아니다. 따라서 「문턱 위 구간을 Williams 방법으로 우회」해도 P≠NP 로 이어지지 않는다 — 글은 두 트랙이 같은 종착점(P≠NP)을 향하는 것처럼 적고 이 차이를 표시하지 않았다.
  3. 「자연 증명이 아님이 알려진 알고리즘적 방법」은 과장이다. Williams(STOC 2013 / SICOMP 2016)는 전형적 회로 클래스 C 에 대해 NEXP ⊄ C ⇔ C 에 유용한 구성적(constructive) 성질의 존재임을 보였다(구성성은 피할 수 없다). 대개 「대각선 논법을 써서 자연 증명 장벽을 직접 받지 않는다」고 설명하지만 「자연 증명이 아님이 알려졌다」는 정리는 없다.

  확인한 사실

  주장	사실 여부	근거
  Razborov 의 단조 회로 초다항 하한(CLIQUE), Razborov(1985)	맞음 — n^{Ω(log n)}. Alon–Boppana(Combinatorica 7, 1987)가 지수 하한으로 강화	Alon–Boppana 1987
  완전 매칭처럼 P 에 속하지만 단조 회로로는 어려운 함수 — Razborov 자신이 보임	맞음 — Razborov(1985, 「logical permanent」)가 이분 그래프 완전 매칭에 n^{Ω(log n)} 단조 하한. Tardos(1988)가 지수 격차로 강화	Circuit complexity (Wikipedia)
  「단조 하한만으로는 P≠NP 에 도달할 수 없다」	부정확 — 위 결과가 보이는 것은 「단조 함수의 단조 하한이 일반 하한으로 자동으로 옮겨지지 않는다」이다. 같은 글이 뒤에서 인용하는 슬라이스 함수(Berkowitz 1982, Valiant 1986)에서는 단조 하한이 곧 일반 하한이다 — 글 안 앞뒤가 어긋난다	Valiant, Negation is powerless for Boolean slice functions, SICOMP 15(2) 1986
  Markov: 임의의 불리언 함수는 약 log n 개의 부정 게이트로 계산 가능	맞음 — 정확히 ⌈log₂(n+1)⌉ 개(Markov, J. ACM 1958)	GMOR 2015 서론
  Fischer: 그 변환은 다항 크기 오버헤드	맞음 — Fischer(1975, LNCS 33): 크기 s 회로 → 2s + O(n² log² n)	위와 같음
  O(log n) 부정 허용 회로에서 NP 완전 문제 초다항 하한 ⇒ 일반 회로 하한 ⇒ P≠NP	맞음(NP ⊄ P/poly ⇒ P≠NP)	위와 같음
  현재 최전선: Amano–Maruoka 의 약 (1/6)log log n	맞음 — Amano–Maruoka, SIAM J. Comput. 35(1) 2005 (MFCS 1998 판). CLIQUE 에 대해 ⌊(1/6)log log m⌋ 개 이하 부정 회로의 초다항 하한. 이후 이를 넘는 일반 회로 크기 결과는 확인하지 못함	SIAM 페이지
  저부정 회로 클래스에는 PRF 가 존재한다고 믿을 근거가 희박 / PRF 를 담는 최소 t 를 조사(4단계)	이미 알려짐 — PRF 는 log n − O(1) 개 부정이 필요(최적). 일방향 함수는 단조일 수 있음(Goldreich–Izsak)	Guo–Malkin–Oliveira–Rosen, TCC 2015
  Karchmer–Wigderson 의 통신 복잡도적 재해석	맞음(STOC 1988 / SIAM J. Discrete Math. 1990). 깊이(공식 크기) 결과임	—
  Williams 의 NEXP ⊄ ACC⁰ 와 후속(THR 확장)	맞음 — Williams(CCC 2011, J. ACM 61(1) 2014), ACC∘THR(STOC 2014), Murray–Williams NQP ⊄ ACC⁰(STOC 2018)	Williams J. ACM 2014
  Williams 방법은 「자연 증명이 아님이 알려진」 경로	과장 — NEXP ⊄ C ⇔ C 에 유용한 구성적 성질 존재	Williams, Natural Proofs Versus Derandomization
  Williams 방법 이식으로 문턱 위 구간 우회 → P≠NP	표시 없는 비약 — 알고리즘적 방법의 산출물은 NEXP/NQP 하한	위와 같음
  근사법 계열은 비상대화적이며 대수화 장벽의 적용 대상이 아니다	판단(정리 아님) — Aaronson–Wigderson 은 NEXP vs P/poly 같은 회로 하한 자체가 비대수화 기법을 요구함을 보였다. 즉 목표(NP ⊄ P/poly)를 이루는 기법은 반드시 비대수화여야 한다는 것이 사실이고, 근사법이 그 조건을 만족하는지는 정리된 결과가 없다	Aaronson–Wigderson, ECCC TR08-005
  Berkowitz: 슬라이스 함수에서는 단조 하한이 일반 하한과 다항 동치	맞음(Berkowitz 1982 기술보고서; Valiant 1986 도 같은 결과)	Valiant 1986
  Razborov(1985)·Amano–Maruoka·Williams·증폭 정리들은 약한 하한이 주요 분리로 증폭될 수 있음을 보여 줌	부정확한 묶음 — 「약한 하한 → 강한 분리」는 증폭(magnification) 정리만의 성질. 앞의 셋은 제한 모델의 직접 하한	Oliveira–Santhanam 2018
  본 연구의 부분 결과도 증폭 정리의 입력이 될 수 있다	추측(표시 없음) — 증폭 정리의 입력은 MCSP·MKtP·희소 NP 언어 같은 특정 문제의 하한이고 CLIQUE 하한이 아니다. 또 근사법 계열 기법은 지역성 장벽(CHOPRS 2020)의 대상일 수 있다	CHOPRS, ECCC TR19-168

  고칠 곳

  1. 핵심 정리 1번째 줄·아이디어 개요 첫 문단
     • 원문: 「단조 하한만으로는 P≠NP 에 도달할 수 없다는 것도 Razborov 자신이 보였다.」
     • 제안: 「완전 매칭처럼 P 에 속하면서도 단조 회로로는 초다항 크기가 필요한 함수가 있다는 것도 Razborov 자신이 보였다(1985) — 단조 함수의 단조 하한은 일반 하한으로 자동으로 옮겨지지 않는다. (슬라이스 함수는 예외 — 아래 5단계)」
  2. 4단계(장벽 지도화)와 「왜 해볼 만한」 3번째 항목·장벽 표 「자연 증명」 칸
     • 원문: 「단조 및 저부정 회로 클래스에는 PRF 가 존재한다고 믿을 근거가 희박해 이 구도에서는 약하고」
     • 제안: 「Guo–Malkin–Oliveira–Rosen(TCC 2015)은 PRF 가 log n − O(1) 개의 부정 게이트를 필요로 함을 보였다. 그래서 그보다 적은 부정을 허용하는 구간에는 PRF 가 없고 PRF 형태의 자연 증명 장벽은 직접 걸리지 않는다. 다만 그 문턱은 Markov 한계(⌈log₂(n+1)⌉)와 상수 차이뿐이라, 장벽이 켜지는 구간은 사실상 일반 회로와 같다.」
     • 4단계의 목표(문턱 추정)는 「GMOR 2015 의 문턱을 출발점으로, 근사법이 그 문턱 아래 어디까지 살아남는지 조사」로 바꾸기를 권한다. 그림 설명의 「점선 상자는 4단계에서 추정할 … 문턱」도 「GMOR 2015 가 보인 문턱(log n − O(1))」으로.
  3. 6단계·「두 트랙의 나눔」·「왜」 3번째 항목
     • 원문: 「문턱 위 구간은 자연 증명이 아님이 알려진 알고리즘적 방법(6단계)으로 우회하도록 이중화되어 있다.」
     • 제안: 「문턱 위 구간에는 Williams 의 알고리즘적 방법을 시도한다. 이 방법은 대각선 논법을 쓰므로 자연 증명 장벽을 직접 받지 않는다고 설명되지만(그래도 Williams 2013 은 NEXP ⊄ C 가 구성적 성질의 존재와 동치임을 보였다), 산출물은 NEXP·NQP 하한이어서 이 트랙만으로는 NP 완전 문제의 하한, 곧 P≠NP 에 이르지 않는다.」
  4. 「왜」 2번째 항목
     • 원문: 「상대화·대수화 장벽에 걸리지 않는다. … 대수화 장벽의 적용 대상도 아니다. 즉 세 대장벽 중 실질적 위협은 자연 증명 하나로 압축된다.」
     • 제안: 「상대화·대수화 장벽에 걸리지 않을 것으로 본다(이 글의 판단). 근사법 계열은 회로 내부 구조를 직접 다룬다. 다만 Aaronson–Wigderson 은 NEXP ⊄ P/poly 같은 회로 하한 자체가 비대수화 기법을 요구함을 보였으므로, 이 경로가 성공한다면 그 기법은 반드시 비대수화여야 한다.」
  5. 「왜」 4번째 항목
     • 원문: 「Razborov(1985), Amano–Maruoka, Williams의 ACC⁰ 하한, 최근의 경도 증폭(hardness magnification) 정리들은 제한 회로 모델의 약해 보이는 하한이 주요 분리 결과로 증폭될 수 있음을 보여 주며, 본 연구의 부분 결과들도 증폭 정리의 입력이 될 수 있다.」
     • 제안: 「Razborov(1985), Amano–Maruoka(2005), Williams 의 ACC⁰ 하한(2011)은 제한 회로 모델에서 하한이 실제로 증명되어 온 전례이고, 증폭(hardness magnification) 정리들은 특정 문제(MCSP 변형 등)의 약한 하한이 강한 분리로 이어질 수 있음을 보였다. 본 연구의 부분 결과가 증폭 정리의 입력이 될 수 있는지는 이 글의 추측이다.」

  고칠 곳을 반영하고 글 아래에 참고 문헌(위 표의 근거)을 붙이면 「검토 완료」로 바꿀 수 있습니다.

  답 달기
• 보완#75원문 보완판 — 사실 검토 반영
  • 관리자
  • 2026-10-07 13:28
  • AI 도움
  • 빨간 표시 안보이게

  단조 회로 하한은 일반 회로 하한으로 자동으로 옮겨지지 않지만, 부정(NOT) 게이트를 O(log n)개까지 허용한 회로에서 하한을 보이면 그것이 곧 일반 회로 하한이 된다. 이 글은 허용하는 부정 게이트 수를 한 단계씩 늘려 가는 연구 계획을 제안한다.

  아이디어 개요

  Razborov의 단조 회로 초다항 하한(CLIQUE)은 회로 복잡도 분야가 낳은 가장 강력한 성과지만, 완전 매칭처럼 P에 속하면서도 단조 회로로는 초다항 크기가 필요한 함수가 있다는 것도 Razborov 자신이 보였다(1985) — 단조 함수의 단조 하한은 일반 하한으로 자동으로 옮겨지지 않는다(슬라이스 함수는 예외 — 아래 5단계).

  그런데 Markov의 정리에 따르면 임의의 불리언 함수는 약 log n 개의 부정(NOT) 게이트만으로 계산 가능하고, Fischer의 결과에 의해 이 변환은 다항 크기 오버헤드 안에서 이루어진다. 따라서 "부정 게이트를 O(log n)개까지 허용한 회로"에 대해 NP 완전 문제의 초다항 크기 하한을 증명하면 그것이 곧 일반 회로 하한이며 P≠NP가 따라온다.

  현재 최전선은 Amano–Maruoka가 도달한 약 (1/6)log log n 개 수준이므로, 본 연구는 부정 게이트 수 t를 독립된 계산 자원으로 취급하여 t 증가에 따른 하한의 감쇠 구조를 체계적으로 규명하고, log log n 장벽을 점진적으로 밀어 올리는 것을 목표로 한다. 자연 증명(natural proofs) 장벽이 켜지는 문턱은 Guo–Malkin–Oliveira–Rosen(2015)이 보인 log n − O(1) 로 이미 알려져 있으므로, 그 문턱 아래에서 근사법이 어디까지 살아남는지를 조사하고, 문턱 위 구간에는 Williams의 알고리즘적 방법(ACC⁰ 하한의 성공 사례)을 시도한다. 다만 그 방법의 산출물은 NEXP·NQP 하한이어서 이 트랙만으로는 P≠NP 에 이르지 않는다.

  

  구체적 진행 방법

  1. 기초 문헌 정독 단계: Razborov의 근사법 원논문과 Alon–Boppana의 강화판, Karchmer–Wigderson의 통신 복잡도적 재해석, Markov·Fischer의 부정 게이트 정리, Amano–Maruoka의 부정 제한 하한, Guo–Malkin–Oliveira–Rosen 의 부정 게이트와 PRF 결과, Jukna의 회로 복잡도 교과서 해당 장, 그리고 Williams의 NEXP⊄ACC⁰ 논문과 후속 개선(THR 게이트 확장 포함)을 읽고 각 기법의 적용 범위와 한계 조건을 표로 정리한다.
  2. 정식화 단계: 부정 게이트 t개를 가진 회로를 단조 성분들로 분해하는 표준 기법을 근사법의 언어로 다시 쓰고, "t에 따른 하한 감쇠 함수"라는 개념을 명시적으로 정의한다. 기존 증명들이 정확히 어느 보조 단계에서 log log n 수준에 묶이는지, 병목이 분해 폭발 때문인지 근사자 집합의 크기 때문인지를 분리하여 진단한다.
  3. 마일스톤 1(재현·통합): t=0인 Razborov 하한과 t≤(1/6)log log n인 Amano–Maruoka 하한을 하나의 통일된 프레임워크 안에서 재유도하고, 감쇠 함수의 형태를 명시한 기술 노트를 작성한다. 이 노트 자체가 서베이 겸 출발점 논문이 된다.
  4. 장벽 지도화 단계: Guo–Malkin–Oliveira–Rosen(TCC 2015)은 PRF 가 log n − O(1) 개의 부정 게이트를 필요로 함을 보였다. 그래서 그보다 적은 부정을 허용하는 구간에는 PRF 가 없고 PRF 형태의 자연 증명 장벽은 직접 걸리지 않는다. 다만 그 문턱은 Markov 한계(⌈log₂(n+1)⌉)와 상수 차이뿐이라, 장벽이 켜지는 구간은 사실상 일반 회로와 같다. 이 단계는 GMOR 2015 의 문턱을 출발점으로, 근사법이 그 문턱 아래 어디까지 살아남는지를 조사한다.
  5. 마일스톤 2(점근적 개선): CLIQUE 또는 다른 단조 NP 완전 함수에 대해 허용 부정 수를 c·log log n(더 큰 상수 c) 혹은 (log log n)의 다항식 수준으로 끌어올리는 어떤 점근적 개선이라도 확보한다. 보조 트랙으로 슬라이스 함수(slice function) 경로 — 슬라이스 함수에서는 단조 하한이 곧 일반 하한과 다항 동치라는 Berkowitz의 관찰 — 를 검토하여, 슬라이스 구조가 근사법의 어느 병목을 완화하는지 별도 분석한다.
  6. 우회 트랙(알고리즘적 방법 결합): 장벽 문턱 위 구간을 위해, 부정 제한 회로 클래스에 대한 자명하지 않은 충족가능성(SAT) 알고리즘을 설계하고 Williams의 "빠른 알고리즘 ⇒ 하한" 연결 정리를 이 클래스에 이식할 수 있는지 정식화한다. 이 방법은 대각선 논법을 쓰므로 자연 증명 장벽을 직접 받지 않는다고 설명되지만(그래도 Williams 2013 은 NEXP ⊄ C 가 구성적 성질의 존재와 동치임을 보였다), 산출물은 NEXP·NQP 하한이어서 이 트랙만으로는 NP 완전 문제의 하한, 곧 P≠NP 에 이르지 않는다.
  7. 마일스톤 3(정리·공표): 부분 결과라도 감쇠 함수 개선, 근사법이 GMOR 문턱 아래 어디까지 통하는지에 대한 결과, SAT 알고리즘 중 하나를 완결된 정리로 다듬어 ECCC 프리프린트와 CCC/FOCS 계열 학회 투고를 목표로 정리한다. 이후 감쇠 함수가 어디까지 개선 가능한지에 대한 메타 정리(불가능성 결과 포함)를 장기 과제로 설정한다.

  두 트랙의 나눔

  문턱 아래 — 근사법 트랙

  부정 게이트 t개를 가진 회로를 근사법의 언어로 다시 쓰고 「t 에 따른 하한 감쇠 함수」를 개선한다(2·3·5단계). 슬라이스 함수 경로는 보조 트랙으로 검토한다. 문턱은 GMOR 2015 가 보인 log n − O(1) 이고, 이 구간에는 PRF 가 없다.

  문턱 위 — 알고리즘적 방법 트랙

  부정 제한 회로 클래스에 대한 자명하지 않은 충족가능성(SAT) 알고리즘을 설계하고, Williams 의 「빠른 알고리즘 ⇒ 하한」 연결 정리를 이 클래스에 이식할 수 있는지 정식화한다(6단계). 이 구간은 Markov 한계와 상수 개 차이뿐이라 사실상 일반 회로와 같다. 이 트랙의 산출물은 NEXP·NQP 하한이어서, 근사법 트랙과 같은 종착점(P≠NP)으로 바로 이어지지 않는다.

  왜 해볼 만한 가치가 있는가

  1. 목표 지점이 정량적으로 완결되어 있다. log log n에서 log n까지의 간극은 유한하고 명확히 측정되는 전선이며, 종착점에 도달하는 순간 Fischer의 다항 시뮬레이션에 의해 문자 그대로 P≠NP가 성립한다. 중간의 어떤 점근적 개선도 그 자체로 독립된 성과가 된다.
  2. 상대화·대수화 장벽에 걸리지 않을 것으로 본다(이 글의 판단). 근사법 계열은 오라클 접근이 아니라 회로 내부 구조를 직접 다룬다. 다만 Aaronson–Wigderson 은 NEXP ⊄ P/poly 같은 회로 하한 자체가 비대수화 기법을 요구함을 보였으므로, 이 경로가 성공한다면 그 기법은 반드시 비대수화여야 한다.
  3. 자연 증명 장벽의 문턱이 이미 알려져 있다. Guo–Malkin–Oliveira–Rosen(TCC 2015)은 PRF 가 log n − O(1) 개의 부정 게이트를 필요로 함을 보였다. 그래서 그보다 적은 부정을 허용하는 구간에는 PRF 가 없고 PRF 형태의 자연 증명 장벽은 직접 걸리지 않는다. 다만 그 문턱은 Markov 한계(⌈log₂(n+1)⌉)와 상수 차이뿐이라, 장벽이 켜지는 구간은 사실상 일반 회로와 같다. 근사법이 이 문턱 아래 어디까지 살아남는지 밝히는 4단계 작업은 실패해도 그 자체가 장벽 이론에 대한 기여가 된다고 본다. 문턱 위 구간에는 Williams 의 알고리즘적 방법(6단계)을 시도하지만, 그 산출물은 NEXP·NQP 하한이어서 이 트랙만으로는 P≠NP 에 이르지 않는다.
  4. 성공 전례가 있는 활성 분야다. Razborov(1985), Amano–Maruoka(2005), Williams 의 ACC⁰ 하한(2011)은 제한 회로 모델에서 하한이 실제로 증명되어 온 전례이고, 증폭(hardness magnification) 정리들은 특정 문제(MCSP 변형 등)의 약한 하한이 강한 분리로 이어질 수 있음을 보였다. 본 연구의 부분 결과가 증폭 정리의 입력이 될 수 있는지는 이 글의 추측이다.
  5. 실패조차 정보가 된다. 만약 어떤 t 이상에서 하한 감쇠가 증명 가능하게 붕괴한다면, 이는 부정 게이트가 계산 능력에서 수행하는 구조적 역할을 정확히 짚어내는 새로운 장벽 정리가 되어 P vs NP가 왜 어려운지에 대한 이해를 한 단계 끌어올린다.

  이 글이 보는 세 장벽과의 관계 — 아이디어 쪽의 판단이며 검증된 결론이 아니다

  장벽	이 글의 판단
  상대화	걸리지 않는다고 본다 — 근사법 계열의 조합적 회로 하한 기법은 오라클 접근이 아니라 회로의 내부 구조를 직접 다루므로 비상대화적이다.
  자연 증명	Guo–Malkin–Oliveira–Rosen(TCC 2015)이 PRF 는 log n − O(1) 개의 부정 게이트가 필요함을 보였다. 그보다 적은 부정을 허용하는 구간에는 PRF 가 없어 PRF 형태의 자연 증명 장벽은 직접 걸리지 않지만, 문턱이 Markov 한계(⌈log₂(n+1)⌉)와 상수 차이뿐이라 장벽이 켜지는 구간은 사실상 일반 회로와 같다. 그 구간에는 알고리즘적 방법(6단계)을 시도하나, 산출물은 NEXP·NQP 하한이다.
  대수화	근사법이 대수화 장벽에 걸리는지는 정리된 결과가 없고, 걸리지 않을 것으로 본다. 다만 Aaronson–Wigderson 은 회로 하한 자체가 비대수화 기법을 요구함을 보였으므로, 이 경로가 성공하려면 그 기법은 비대수화여야 한다.

  참고 문헌

  • Razborov, CLIQUE 의 단조 회로 하한·완전 매칭(「logical permanent」)의 단조 하한, 1985
  • Alon, Boppana, The monotone circuit complexity of Boolean functions, Combinatorica 7, 1987 — https://link.springer.com/article/10.1007/BF02579196
  • Tardos, 단조 회로와 일반 회로의 지수 격차, 1988
  • Circuit complexity (Wikipedia) — https://en.wikipedia.org/wiki/Circuit_complexity
  • Berkowitz, 슬라이스 함수의 단조·일반 하한 동치, 기술보고서 1982
  • Valiant, Negation is powerless for Boolean slice functions, SIAM J. Comput. 15(2), 1986 — https://doi.org/10.1137/0215037
  • Markov, J. ACM, 1958 (⌈log₂(n+1)⌉ 개의 부정 게이트)
  • Fischer, LNCS 33, 1975 (크기 s 회로 → 2s + O(n² log² n))
  • Amano, Maruoka, SIAM J. Comput. 35(1), 2005 (MFCS 1998 판) — https://epubs.siam.org/doi/10.1137/S0097539701396959
  • Guo, Malkin, Oliveira, Rosen, The Power of Negations in Cryptography, TCC 2015 — https://eprint.iacr.org/2014/902
  • Goldreich, Izsak — 단조 일방향 함수(GMOR 2015 서론에 인용)
  • Karchmer, Wigderson, STOC 1988 / SIAM J. Discrete Math. 1990
  • Williams, NEXP ⊄ ACC⁰, CCC 2011 / J. ACM 61(1), 2014 — https://doi.org/10.1145/2559903
  • Williams, ACC∘THR 하한, STOC 2014
  • Murray, Williams, NQP ⊄ ACC⁰, STOC 2018
  • Williams, Natural Proofs Versus Derandomization, STOC 2013 / SIAM J. Comput. 2016 — https://arxiv.org/abs/1212.1891
  • Aaronson, Wigderson, Algebrization, STOC 2008 / TOCT 2009 — https://eccc.weizmann.ac.il/report/2008/005/
  • Oliveira, Santhanam, Hardness magnification, FOCS 2018 — https://eccc.weizmann.ac.il/report/2018/139/
  • Chen, Hirahara, Oliveira, Pich, Rajgopal, Santhanam, 지역성 장벽, ITCS 2020 — https://eccc.weizmann.ac.il/report/2019/168/
  답 달기