Salil Vadhan es un informático estadounidense. Es profesor Vicky Joseph de Ciencias de la Computación y Matemáticas Aplicadas en la Universidad de Harvard . [1] Después de completar su licenciatura en Matemáticas e Informática en Harvard en 1995, obtuvo su doctorado en Matemáticas Aplicadas en el Instituto Tecnológico de Massachusetts en 1999, donde su asesor fue Shafi Goldwasser . [2] Su investigación se centra en la interfaz entre la teoría de la complejidad computacional y la criptografía . Se centra en los temas de pseudoaleatoriedad y pruebas de conocimiento cero . Su trabajo sobre el producto en zig-zag , con Omer Reingold y Avi Wigderson , recibió el Premio Gödel 2009 . [3]
Una de las principales aportaciones de su trabajo es un nuevo tipo de producto gráfico, llamado producto en zig-zag .
Tomando el producto de un gráfico grande por un gráfico pequeño, el gráfico resultante hereda (aproximadamente) su tamaño del gráfico grande, su grado del gráfico pequeño y sus propiedades de expansión de ambos. La iteración produce construcciones explícitas simples de expansores de grado constante de cada tamaño, a partir de un expansor de tamaño constante.
Crucial para la intuición y el análisis simple de las propiedades del producto en zig-zag es la visión de los expansores como funciones que actúan como propagadores de "ondas de entropía": transforman distribuciones de probabilidad en las que la entropía se concentra en un área en distribuciones en las que esa concentración es mayor. disipado. En estos términos, el producto gráfico proporciona la interferencia constructiva de dos de esas ondas.
Se puede aplicar una variante de este producto a los extractores, dando los primeros extractores explícitos cuya longitud de la semilla depende (poli)logarítmicamente únicamente de la deficiencia de entropía de la fuente (en lugar de su longitud) y que extraen casi toda la entropía de la entropía mínima alta. fuentes. Estos extractores de alta entropía mínima tienen varias aplicaciones interesantes, incluidos los primeros expansores explícitos de grado constante que superan el "límite de valor propio".
A Vadhan también se le ocurrió otro enfoque simplificado [4] para el problema de la conectividad ST no dirigida tras el revolucionario resultado de Reingold. Además , el producto en zig-zag fue útil en la prueba de Omer Reingold de que SL = L.
Su trabajo en esta área consiste en utilizar métodos de teoría de la complejidad para comprender el poder y las limitaciones de las pruebas de conocimiento cero. En una serie de artículos con Oded Goldreich y Amit Sahai , obtuvieron una comprensión profunda de la clase SZK de problemas que poseen pruebas estadísticas de conocimiento cero, caracterizaron la clase SZK y demostraron que SZK es cerrado bajo varias operaciones. Recientemente, su trabajo consistió en intentar trabajar en la prueba de conocimiento cero más allá de los límites de la clase SZK.
Con Lu, Omer Reingold y Avi Wigderson , dio la primera construcción de extractores de aleatoriedad que son "óptimos hasta factores constantes", alcanzando un hito en una década de trabajo sobre el tema.
Con Trevisan, Zuckerman, Kamp y Rao, desarrolló una teoría de extracción aleatoria (y compresión de datos) de fuentes muestreables, que son fuentes aleatorias generadas por un algoritmo eficiente (desconocido).
Vadhan fue elegido miembro de ACM en 2018 por "promover la complejidad computacional y la criptografía, y por promover el apoyo público a la informática teórica". [5]