Richard Jay Lipton (nacido el 6 de septiembre de 1946) es un científico informático estadounidense , decano asociado de investigación, profesor y titular de la cátedra Frederick G. Storey de informática en la Facultad de Informática del Instituto de Tecnología de Georgia . Ha trabajado en teoría de la informática , criptografía y computación de ADN .
En 1968, Lipton recibió su licenciatura en matemáticas de la Universidad Case Western Reserve . En 1973, recibió su doctorado de la Universidad Carnegie Mellon ; su disertación, supervisada por David Parnas , se titula On Synchronization Primitive Systems . Después de graduarse, Lipton enseñó en Yale 1973-1978, en Berkeley 1978-1980 y luego en Princeton 1980-2000. Desde 2000, Lipton ha estado en Georgia Tech . Mientras estaba en Princeton, Lipton trabajó en el campo de la computación de ADN . Desde 1996, Lipton ha sido el científico consultor jefe en Telcordia . En 1999, Lipton fue elegido miembro de la Academia Nacional de Ingeniería para la aplicación de la teoría de la ciencia de la computación a la práctica.
En 1980, junto con Richard M. Karp , Lipton demostró que si SAT puede resolverse mediante circuitos booleanos con un número polinomial de puertas lógicas , entonces la jerarquía polinomial colapsa a su segundo nivel.
Demostrar que un programa P tiene alguna propiedad es un proceso simple si las acciones dentro del programa son ininterrumpibles. Sin embargo, cuando la acción es interrumpible, Lipton demostró que a través de un tipo de reducción y análisis, se puede demostrar que el programa reducido tiene esa propiedad si y solo si el programa original tiene la propiedad. [2] Si la reducción se realiza tratando las operaciones interrumpibles como una gran acción ininterrumpible, incluso con estas condiciones relajadas se pueden demostrar propiedades para un programa P. Por lo tanto, las pruebas de corrección de un sistema paralelo a menudo se pueden simplificar en gran medida.
Lipton estudió y creó modelos de seguridad de bases de datos sobre cómo y cuándo restringir las consultas realizadas por los usuarios de una base de datos de modo que no se filtre información privada o secreta. [3] Por ejemplo, consultar una base de datos de donaciones de campaña podría permitir al usuario descubrir las donaciones individuales a candidatos u organizaciones políticas. Si se le da acceso a promedios de datos y acceso a consultas sin restricciones, un usuario podría explotar las propiedades de esos promedios para obtener información ilícita. Se considera que estas consultas tienen una gran "superposición" que crea la inseguridad. Al limitar la "superposición" y el número de consultas, se puede lograr una base de datos segura.
Richard Lipton y Andrew Tomkins introdujeron un algoritmo de programación de intervalos en línea aleatorio , cuya versión de tamaño 2 es fuertemente competitiva y la versión de tamaño k logra O(log ), además de demostrar un límite inferior teórico de O(log ). [4] Este algoritmo utiliza una moneda privada para la aleatorización y una elección "virtual" para engañar a un adversario mediano .
Cuando se le presenta un evento, el usuario debe decidir si lo incluye o no en el cronograma. El algoritmo virtual de 2 tamaños se describe por cómo reacciona a intervalos de 1 o k que le presenta el adversario:
Nuevamente, se demuestra que este algoritmo de tamaño 2 es fuertemente competitivo . Luego, se demuestra que el algoritmo generalizado de tamaño k , que es similar al algoritmo de tamaño 2, es O(log )-competitivo.
Lipton demostró que las pruebas aleatorias pueden ser demostrablemente útiles, siempre que el problema satisfaga ciertas propiedades. [5] Probar la corrección de un programa es uno de los problemas más importantes que se presentan en la ciencia informática. Normalmente, en las pruebas aleatorias, para alcanzar una probabilidad de error de 1/1000, se deben ejecutar 1000 pruebas. Sin embargo, Lipton demuestra que si un problema tiene subpartes "fáciles", las pruebas de caja negra repetidas pueden alcanzar una tasa de error de c r , donde c es una constante menor que 1 y r es el número de pruebas. Por lo tanto, la probabilidad de error se acerca a cero exponencialmente rápido a medida que r crece.
Esta técnica es útil para comprobar la corrección de muchos tipos de problemas.
En el área de la teoría de juegos , más específicamente de los juegos no cooperativos , Lipton junto con E. Markakis y A. Mehta demostraron [6] la existencia de estrategias de equilibrio épsilon con soporte logarítmico en el número de estrategias puras . Además, el pago de tales estrategias puede aproximarse en épsilon a los pagos de los equilibrios de Nash exactos . El tamaño limitado (logarítmico) del soporte proporciona un algoritmo cuasi-polinomial natural para calcular los equilibrios épsilon .
Lipton y J. Naughton presentaron un algoritmo de muestreo aleatorio adaptativo para consultas de bases de datos [7] [8] que es aplicable a cualquier consulta para la cual las respuestas a la consulta se puedan dividir en subconjuntos disjuntos [ aclaración necesaria ] . A diferencia de la mayoría de los algoritmos de estimación de muestreo, que determinan estáticamente la cantidad de muestras necesarias, su algoritmo decide la cantidad de muestras en función de los tamaños de las muestras y tiende a mantener constante el tiempo de ejecución (en lugar de lineal en la cantidad de muestras).
DeMillo , Lipton y Perlis [9] criticaron la idea de la verificación formal de los programas y argumentaron que
Chandra, Furst y Lipton [10] generalizaron la noción de protocolos de comunicación entre dos partes a protocolos de comunicación entre múltiples partes. Propusieron un modelo en el que una colección de procesos ( ) tienen acceso a un conjunto de enteros ( , ) excepto uno de ellos, de modo que se le niega el acceso a . A estos procesos se les permite comunicarse para llegar a un consenso sobre un predicado. Estudiaron la complejidad de comunicación de este modelo, definida como el número de bits transmitidos entre todos los procesos. Como ejemplo, estudiaron la complejidad de un protocolo de k partes para Exactamente- N (¿todos los suman N?), y obtuvieron un límite inferior utilizando el método de teselado. Aplicaron además este modelo para estudiar programas de ramificación generales y obtuvieron un límite inferior de tiempo para programas de ramificación de espacio constante que calculan Exactamente- N .
No tenemos forma de demostrar que el problema de satisfacibilidad booleano (a menudo abreviado como SAT), que es NP-completo , requiere tiempo exponencial (o al menos superpolinomial) (este es el famoso problema P versus NP ), o espacio lineal (o al menos superlogarítmico) para resolverse. Sin embargo, en el contexto del equilibrio espacio-tiempo , se puede demostrar que SAT no se puede calcular si aplicamos restricciones tanto al tiempo como al espacio. L. Fortnow , Lipton, D. van Melkebeek y A. Viglas [11] demostraron que SAT no se puede calcular mediante una máquina de Turing que toma como máximo O( n 1,1 ) pasos y como máximo O( n 0,1 ) celdas de sus cintas de lectura-escritura.
