랜스 포트나우

Lance Fortnow
랜스 포트나우
태어난1963년 8월 15일 (1963-08-15) (58세)
국적미국인의
모교코넬 대학교
매사추세츠 공과대학교
로 알려져 있다.대화형 교정쇄
수상ACM 펠로우, NSF 총장교직원 펠로우, 풀브라이트 스콜라, 네로드상
과학 경력
필드컴퓨터 공학
기관일리노이 공과대학교
조지아 테크
노스웨스턴 대학교
시카고의 대학교
박사학위 자문위원마이클 시퍼
박사과정 학생카스텐 룬드
웹사이트http://lance.fortnow.com/
http://blog.computationalcomplexity.org/

랜스 제레미 포트나우(Lance Jeremy Fortnow, 1963년 8월 15일 출생)는 컴퓨터 과학자로 계산 복잡성과 상호 작용 증명 시스템의 주요 결과로 알려져 있다. 그는 현재 일리노이 공과대학교 컴퓨터대학 학장을 맡고 있다.

전기

랜스 포트나우는 1989년 마이클 시퍼(Michael Sipser)의 감독으로 MIT로부터 응용수학 박사학위를 받았다.[1] 졸업 후, 그는 시카고 대학교(1989–1999, 2003–2007), 노스웨스턴 대학교(2008–2012), 조지아 공과대학교(2012–2019)의 교수진으로 재직했다.[2][3]

Fortnow는 ACM Transactions on Computing Ironics 저널의 창립 편집장이었다.[4] 그는 ACM SIGACT의[5] 회장이었고 폴 베임(Paul Beame)의 뒤를 이었다. 그는 2000년부터 2006년까지 IEEE 컴퓨터 복잡성에[6] 관한 회의의 회장을 맡았다. 2002년에 포트나우는 이론 컴퓨터 과학에[7] 헌신한 최초의 블로그 중 하나를 시작했고 그 이후로 그것을 위해 글을 썼다; 2007년 이후로 그는 공동 블로거인 윌리엄 가스아치를 가지고 있다. 2009년 9월, 포트나우는 컴퓨터 기계 협회의 통신에 있어서의 P 대 NP 문제의 진전 상황을 조사한 기사를 발표하면서 복잡성 이론에 주류를 이루었다.[8][9]

일

그의 많은 출판물에서, Fortnow는 계산 복잡성의 분야에 중요한 결과를 기여했다. 아직 MIT 대학원생인 포르트노우는 다항식 계층 구조가 붕괴되지 않는 한 NP 완성 언어에 대한 완벽한 제로 지식 프로토콜은 없다는 것을 보여주었다.[10] 마이클 시퍼와 함께, 그는 또한 특정 신탁에 관해서도 상호 작용적인 프로토콜이 없는 co-NP에 언어가 존재한다는 것을 증명했다.[11]

1989년 11월, Fortnow는 노암 니산으로부터 co-NP가 다중 프로베라 쌍방향 증명(MIP)을 가지고 있다는 이메일을 받았다. 카스텐 룬드, 하워드 카를로프 등과 함께, 그는 이 결과를 쌍방향 증명 시스템의 구축을 위한 대수적 기법을 개발하고 다항식 시간 계층 구조의 모든 언어가 쌍방향 증명 시스템을 가지고 있음을 증명하는 데 이용했다.[12] 그들의 작업은 IP=PSPACE를 증명하기 위해 Adi Shamir가 그것을 사용했을 때 거의 2주가 되지 않았다.[13] 이에 대한 빠른 후속 조치(1990년 1월 17일, 니산의 이메일을 받은 지 두 달도 안 된 후) 포트노우는 라슬로 바바이, 카스텐 룬드와 함께 MIP=NExP라는 사실을 증명했다.[14] 이러한 대수적 기법들은 포르트노우, 바바이, 레오니드 레빈, 마리오 스제기에 의해 더욱 확장되어 연산을 확인하는 새로운 일반적 메커니즘을 제시하였다.[15]

이때부터 포트나우는 디랜도마이즈, 희박한 언어, 오라클 머신 등 계산 복잡성의 분야에서 다양한 주제에 대해 계속 발표해 왔다. Fortnow는 양자 컴퓨팅, 게임 이론, 게놈 염기서열 분석, 경제학에 대해서도 출판했다.

랜스 포츠노우의 경제학 연구에는 게임 이론, 최적의 전략, 예측 등이 포함된다. 포트나우는 듀크 팡과 함께 죄수의 딜레마라는 고전적인 게임 이론 문제를 조사하여, 그 딜레마가 무한히 순차적으로 제기되도록 문제를 확장시켰다. 이들은 선수들이 계산적으로 경계가 정해진 세트에서 전략을 이끌어내고 복수 전략의 우세를 막기 위해 '그레이스 기간'을 도입하는 제약을 감안해 어떤 전략을 취해야 하는지 조사했다.[16] 포트나우도 시장조사업체와 함께 로그시장 채점규칙(LMSR)을 점검했다. 그는 LMSR 가격이 #P-hard라는 것을 보여주고 순열 시장의 가격을 결정하는 근사 기법을 제안하는 것을 도왔다.[17] 그는 또한 LMSR 시장 제작자들과 함께 일하는 정보에 입각한 거래자들의 행동에 대한 연구에 기여했다.[18]

Fortnow는 또한 그가 2009년에 CACM을 위해 이전에 쓴 기사에 기초하여 느슨하게 기초하고 있는 "황금 티켓: P, NP, 불가능한 것을 찾아라"라는 제목의 인기 과학 책을 저술했다.[19][20] Fortnow는 그의 저서에서 P 대 NP 문제와 그 알고리즘적 한계에 대한 비기술적인 소개를 제공한다. 그는 자신의 저서에 대해 더 자세히 설명하고 NP 문제가 왜 그렇게 중요한지 데이터 회의론 팟캐스트에서 설명한다.[21]

수상 및 수상

참조

  1. ^ 수학 계보 프로젝트의 랜스 포스노우
  2. ^ "College of Computing Hires Fortnow, Anton to Lead Schools" (Press release). Georgia Tech College of Computing. March 19, 2012. Retrieved October 4, 2012.
  3. ^ 노스웨스턴 대학교 전기공학과 컴퓨터과학부 교수진
  4. ^ 계산이론에 의한 ACM거래
  5. ^ ACM SIGACT
  6. ^ IEEE 계산 복잡성 회의
  7. ^ 계산 복잡성 웹로그
  8. ^ J. 마코프. P-NP 퍼즐러에게는 상 외에도 결과가 있다. 뉴욕 타임즈 2009년 10월 7일.
  9. ^ L. 포트나우. P 대 NP 문제의 상태. ACM 9(2009)의 통신.
  10. ^ L. 포트나우. 완벽한 제로 지식의 복잡성. S. Micali, 편집자, Randomness and Computing, Computing Research의 제5권 327-343페이지. 1989년 그리니치 JAI 프레스
  11. ^ L. Fortnow와 M. 사이퍼. 공동 NP 언어를 위한 대화형 프로토콜이 있는가? 정보처리편지, 28:249-251, 1988.
  12. ^ C. 룬드, L. 포트나우, H. 카를로프, N. 니산. 쌍방향 증명 시스템을 위한 대수적 방법. ACM 저널, 39 (4):859-868, 1992.
  13. ^ A. 샤미르. IP = PSpace. ACM 39(4):869-877, 1992.
  14. ^ L. Babai, L. Fortnow, C. 룬드. 비결정론적 지수 시간에는 2-프로버 인터랙티브 프로토콜이 있다. 계산 복잡성, 1:1:3-40, 1991.
  15. ^ L. Babai, L. Fortnow, L. Levin, M. Szegedy. 다변량 시간에서의 계산 확인. 제23회 ACM 이론 심포지엄의 진행, 21-31페이지. ACM, 뉴욕 1991.
  16. ^ L. 포트나우와 D. 와우. 경계된 선수들과의 반복된 경기에서의 최적성과 지배력. 제26회 ACM 이론 심포지엄의 진행에서 741-749페이지. ACM, 뉴욕 1994년
  17. ^ Y. Chen, L. Fortnow, N. Lambert, D. 페노크, J. 워트먼. 결합형 시장 제조자의 복잡성. 전자상거래에 관한 제9차 ACM 회의의 절차서, 190-199페이지. ACM, 2008년 뉴욕.
  18. ^ Y. Chen, S. Dimitrov, R. Sami, D. 리브스, D. 페녹, R. Hanson, L. Fortnow, R. 고넨. 게임예측시장 : 시장 메이커와의 균형전략. 2009년 알로니카
  19. ^ 포트나우, 랜스 골든 티켓: P, NP, 그리고 불가능을 찾아라. 프린스턴 대학교 출판부, 2013년
  20. ^ 포트나우, 랜스 P 대 NP 문제의 상태. ACM 통신, 52(9): 78-86. 2009년 9월. 검토 기사
  21. ^ P 대 NP 데이터 회의론, 2017년

외부 링크