Leslie Valiant
Leslie Gabriel Valiant (nascido em 28 de março de 1949 em Budapeste , Hungria ) é um cientista da computação britânico e vencedor do Prêmio Turing .
Estudo e Pesquisa
Valiant estudou na University of Cambridge ( King's College ), Imperial College London e na University of Warwick , onde recebeu seu PhD em ciência da computação com Michael Paterson em 1974 ( Procedimentos de decisão para famílias de autômatos de pushdown determinísticos ). Ele então foi para a Carnegie Mellon University , a University of Leeds e a University of Edinburgh . A partir de 1982, ele lecionou na Harvard University , onde atualmente é Professor T. Jefferson Coolidge de Ciência da Computação e Matemática Aplicada.
Valiant lidou em particular com a teoria da complexidade (introdução de Sharp-P 1979), teoria de aprendizagem computacional (introdução do modelo PAC de aprendizagem de máquina: Aprendizagem Provavelmente Aproximadamente Correta ), computação paralela, computação neural, modelos de evolução e inteligência artificial . Ele veio com o conceito de algoritmos holográficos.
Em 1985 ele e Vijay Vazirani provaram um resultado importante da teoria da complexidade (teorema de Valiant-Vazirani) que se UNIQUE- SAT está em P , as classes de complexidade NP e RP (polinômio aleatório) são idênticas.
Mark Jerrum é um de seus alunos de doutorado .
Prêmios
Em 1986, ele recebeu o Prêmio Nevanlinna , o Prêmio Knuth de Ciência da Computação em 1997 , o Prêmio EATCS em 2008 e o Prêmio Turing em 2010 . É Fellow da Royal Society , membro da National Academy of Sciences e membro da Academia Europaea desde 2019 . Em 1983 foi orador convidado no Congresso Internacional de Matemáticos em Varsóvia ( Uma abordagem algébrica para a complexidade computacional ).
Fontes
- Circuitos da mente . Oxford University Press, 1994, 2000
Evidência individual
- ^ Valiant: The Complexity of Computing the Permanent, Theoretical Computer Science, Volume 8, 1979, pp. 189-201
- ^ Valiant, Vazirani NP é tão fácil quanto detectar soluções únicas , Proceedings of the décimo sétimo Simpósio ACM anual em Teoria de Computação, 1985, pp. 458-463.
Links da web
- Página inicial em Harvard (inglês)
- Vídeos por e sobre Leslie Valiant no portal AV da Biblioteca de Informações Técnicas
dados pessoais | |
---|---|
SOBRENOME | Valiant, Leslie |
NOMES ALTERNATIVOS | Valiant, Leslie G.; Valiant, Leslie Gabriel (nome completo) |
PEQUENA DESCRIÇÃO | Cientista da computação britânico |
DATA DE NASCIMENTO | 28 de março de 1949 |
NATURALIDADE | Budapeste , Hungria |