Las contribuciones que ha hecho Valiant son bastante notables y ha recibido los más altos honores por sus logros. Fue miembro del Guggenheim en 1985-86 y recibió el premio Nevanlinna en 1986. Fue elegido miembro de la Royal Society of London en 1991 y, al año siguiente, miembro de la Asociación Estadounidense de Inteligencia Artificial. Fue galardonado con el Premio Knuth del Grupo de Interés Especial de la Asociación de Maquinaria de Computación sobre Algoritmos y Teoría de la Computación y el Comité Técnico sobre los Fundamentos Matemáticos de la Computación del Instituto de Ingenieros Eléctricos y Electrónicos en 1997.18 septiembre 2021