알렉산더 라즈보로프

Alexander Razborov
알렉산더 라즈보로프
태어난 (1963-02-16) 1963년 2월 16일(59세)
벨로보, 러시아 SFSR, 소련
국적.미국, 러시아
모교모스크바 주립 대학교
로 알려져 있다그룹 이론, 컴퓨터 과학 논리, 이론 컴퓨터 과학
어워드
과학 경력
필드수학자
기관시카고 대학교, 스테클로프 수학 연구소, 시카고 도요타 기술 연구소
박사 어드바이저세르게이 아디안

Aleksandr Aleksandrovich Razborov (Russian: Алекса́ндр Алекса́ндрович Разбо́ров; born February 16, 1963), sometimes known as Sasha Razborov, is a Soviet and Russian mathematician and computational theorist.그는 시카고 대학의 Andrew McLeish Distinguished Service 교수입니다.

조사.

Steven Rudich와 공동으로 가장 잘 알려진 그의 연구에서, 그는 계산 복잡성의 근본적인 하한을 증명하기 위해 사용되는 전략의 클래스인 자연 증명의 개념을 도입했습니다.특히, Razborov와 Rudich는 특정 종류의 단방향 함수가 존재한다는 가정 하에 이러한 증명은 P=NP 문제를 해결할 수 없으므로, 이 문제를 해결하기 위해서는 새로운 기술이 필요하다는 것을 보여주었다.

어워드

참고 문헌

  • Razborov, A. A. (1985). "Lower bounds for the monotone complexity of some Boolean functions" (PDF). Soviet Mathematics - Doklady. 31: 354–357.
  • Razborov, A. A. (June 1985). "Lower bounds on monotone complexity of the logical permanent". Mathematical Notes of the Academy of Sciences of the USSR. 37 (6): 485–493. doi:10.1007/BF01157687. S2CID 120875831.
  • Разборов, Александр Александрович (1987). О системах уравнений в свободной группе (PDF) (in Russian). Московский государственный университет. (박사논문 32.56MB)
  • Razborov, A. A. (April 1987). "Lower bounds on the size of bounded depth circuits over a complete basis with logical addition". Mathematical Notes of the Academy of Sciences of the USSR. 41 (4): 333–338. doi:10.1007/BF01137685. S2CID 121744639.
  • Razborov, Alexander A. (May 1989). "Proceedings of the twenty-first annual ACM symposium on Theory of computing - STOC '89". Proceedings of the 21st Annual ACM Symposium on the Theory of Computing. Seattle, Washington, United States. pp. 167–176. doi:10.1145/73007.73023. ISBN 0897913078.
  • Razborov, A. A. (December 1990). "Lower bounds of the complexity of symmetric boolean functions of contact-rectifier circuits". Mathematical Notes of the Academy of Sciences of the USSR. 48 (6): 1226–1234. doi:10.1007/BF01240265. S2CID 120703863.
  • Razborov, Alexander A.; Rudich, Stephen (May 1994). "Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94". Proceedings of the 26th Annual ACM Symposium on the Theory of Computing. Montreal, Quebec, Canada. pp. 204–213. doi:10.1145/195058.195134. ISBN 0897916638.
  • Razborov, Alexander A. (December 1998). "Lower Bounds for the Polynomial Calculus" (PostScript). Computational Complexity. 7 (4): 291–324. CiteSeerX 10.1.1.19.2441. doi:10.1007/s000370050013. S2CID 8130114.
  • Razborov, Alexander A. (January 2003). "Propositional proof complexity" (PostScript). Journal of the ACM. 50 (1): 80–82. doi:10.1145/602382.602406. S2CID 17351318. (JACM 창립 50주년 조사지)

「 」를 참조해 주세요.

메모들

  1. ^ "International Mathematical Union: Rolf Nevanlinna Prize Winners". Archived from the original on 2007-12-17.
  2. ^ "Russian Academy of Sciences: Razborov Aleksandr Aleksandrovich: General info: History".
  3. ^ "Russian Genealogy Agencies Tree: R" (in Russian). Archived from the original on 2007-12-21. Retrieved 2008-01-15.
  4. ^ "ACM-SIGACT Awards and Prizes: 2007 Gödel Prize".
  5. ^ "EATCS: Gödel Prize - 2007". Archived from the original on 2007-12-01.
  6. ^ "Gödel Lecturers – Association for Symbolic Logic". Retrieved 2021-11-10.
  7. ^ "AAAS Fellows Elected" (PDF). Notices of the American Mathematical Society.

외부 링크