미할리스 야나카키스

미할리스 야나카키스(Mihalis Yannakakis)가 1975년 아테네 국립 기술 대학교에서 전기공학 학사 학위를 받은 것은 계산 복잡도 이론 분야에서의 긴 경력의 시작을 알렸습니다. 1953년 아테네에서 태어난 그는 나중에 프린스턴 대학에서 컴퓨터 과학 박사 학위를 취득했으며, 이후 데이터베이스 이론, 검증, 알고리즘 그래프 이론에 영향을 미쳤습니다.

복잡도의 기초

야나카키스는 20년 이상 산업 연구에 종사했으며, 1978년 벨 연구소에서 근무를 시작했습니다. 1991년부터 2001년까지 이곳에서 컴퓨팅 원리 연구부의 디렉터로 재직했습니다. 이 기간 동안 그는 1988년 크리스토스 파파디미트리우와 협력하여 Max-NP 및 Max-SNP 복잡도 클래스를 정의했으며, 외판원 문제 및 3SAT과 같은 NP-hard 문제의 근사화에서 관찰되는 한계에 대해 엄격한 설명을 제공했습니다. 1993년 카스텐 룬드와 함께 한 연구는 그래프 채색과 같은 최소화 문제에 대한 근사해를 계산하는 데 내재된 어려움을 더욱 명확히 했습니다.

데이터베이스 혁신

데이터베이스 이론에 대한 그의 기여는 비순환 스키마 연구를 통한 쿼리 처리 최적화에 초점을 맞추었습니다. 그는 비순환 결합 쿼리를 위한 야나카키스 알고리즘을 도입하여 이러한 구조가 다항 시간에 해결될 수 있음을 입증했습니다. 쿼리 최적화를 넘어 그는 락킹 정책을 조사하여, 데이터의 하이퍼그래프 구조와 트랜잭션 일관성 제약을 활용하여 교착 상태를 방지함으로써 2단계 락킹의 엄격한 제약 외에서도 데이터베이스의 안전성이 유지될 수 있음을 증명했습니다.

검증 및 학술적 리더십

학계로 진출한 야나카키스는 2002년 스탠퍼드 대학교에서 교수로 재직한 후 2004년 컬럼비아 대학교에 합류했습니다. 현재 퍼시 K. 및 비다 L. W. 허드슨 컴퓨터 과학 교수로 재직 중입니다. 컴퓨터 보조 검증 분야의 그의 연구는 선형 시간 시제 논문(선형 시간 시제 논리)과 메시지 시퀀스 차트를 테스트하기 위한 알고리즘적 기초를 마련했습니다. 또한 알렉스 그로스와 도로 페레드와 함께 검증 결과를 바탕으로 시스템 모델을 정제하는 방법인 적응형 모델 검사를 개발했습니다.

무료 테스트

당신은 얼마일까요?

스무 문제, 8분 제한 시간, 그리고 응시자 전체와 비교한 백분위. 가입 없음.

IQ 테스트 하기 →

전문적 인정

야나카키스는 1998년부터 2003년까지 SIAM Journal on Computing의 편집장을 역임하는 등 상당한 편집 활동을 이어왔습니다. 그의 학문적 지위는 미국 국립과학아카데미, 미국 국립공학아카데미, 미국 예술과학아카데미, 유럽 아카데미의 회원 자격에 반영되어 있습니다. 그의 수상 경력으로는 2005년 누스 상(크누스상)과 2023년 존 폰 노이만 이론상이 있습니다.