Leslie G. Valiant recebeu o prêmio Turing pelo seu trabalho em teoria de aprendizado computacional e sua contribuição para a ciência da computação em geral. Valiant é professor da Escola de Engenharia e Ciências Aplicadas da Universidade de Harvard, nos EUA. O seu trabalho nos últimos 30 anos foi fundamental para a criação de sistemas como o IBM Watson e vários outros sistemas com capacidade de aprendizado.
Uma das principais contribuições de Valiant é o modelo PAC ("provavelmente aproximadamente correto"), que é usado, por exemplo, para decidir se uma mensagem de email deveria ser considerada spam ou não. Para casos como esse, o algoritmo de aprendizado normalmente usa experiências do passado para formular uma hipótese probabilística como base da decisão. Porém, tais generalizações do passado podem não funcionar corretamente para o futuro, por exemplo devido a uma generalização demasiada. O modelo PAC permite que tais erros de generalização sejam minimizados; por isso é considerado "aproximadamente correto". O modelo de Valiant também teve influência significativa sobre a aprendizagem automática, a inteligência artificial e em muitas áreas de aplicação da computação, como o processamento de linguagem natural, o reconhecimento de caligrafia e a visão computacional.
De acordo com os comentários do Comitê da ACM,
outra grande contribuição para a complexidade computacional foi a teoria de computação algébrica de Valiant, em que estabeleceu as bases para a compreensão de quais fórmulas algébricas podem ser avaliadas eficientemente.
Valiant fez ainda contribuições significativas para a teoria de complexidade, assim como para computação paralela e distribuída. Nos últimos anos, também contribuiu para pesquisas em neurociência computacional, em que desenvolveu um modelo matemático do cérebro, associando sua arquitetura a funções cognitivas complexas. As suas descobertas foram publicadas no livro Circuits of the Mind (sem tradução para o português).
Foi da seguinte maneira que o Comitê da ACM destacou o trabalho de Valiant em suas conclusões:
Raramente se encontra uma combinação tão avassaladora de profundidade e abrangência como ocorre no trabalho de Valiant. Ele é uma figura heróica na ciência teórica da computação. É também um modelo, pela sua coragem e criatividade em tratar alguns dos mais profundos problemas não-resolvidos na ciência.
O Prêmio Turing, o mais prestigioso da ACM, é concedido desde 1966 e já pertenceu a vários ícones da Ciência da Computação, como Donald Knuth, Vinton Cerf e Edsger Dijkstra. Além do reconhecimento mundial, o ganhador recebe 250 mil dólares (cerca de 400 mil reais).