Richard Jay Lipton (nacido el 6 de septiembre de 1946) es un científico informático estadounidense que es decano asociado de investigación, profesor y catedrático de Computación Frederick G. Storey en la Facultad de Computación del Instituto de Tecnología de Georgia . Ha trabajado en teoría de la informática , criptografía y computación del 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 Sobre sistemas primitivos de sincronización . Después de graduarse, Lipton enseñó en Yale (1973–1978), en Berkeley (1978–1980) y luego en Princeton (1980–2000). Desde el año 2000, Lipton ha estado en Georgia Tech . Mientras estuvo en Princeton, Lipton trabajó en el campo de la computación del ADN . Desde 1996, Lipton ha sido el científico consultor jefe de Telcordia . En 1999, Lipton fue elegido miembro de la Academia Nacional de Ingeniería para la aplicación de la teoría de la informática 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 polinómico de puertas lógicas , entonces la jerarquía polinómica 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 mediante un tipo de reducción y análisis, se puede demostrar que el programa reducido tiene esa propiedad si y sólo si el programa original tiene la propiedad. [2] Si la reducción se realiza tratando las operaciones interrumpibles como una gran acción ininterrumpida, incluso con estas condiciones relajadas se pueden probar las propiedades para un programa P. Por lo tanto, las pruebas de corrección de un sistema paralelo a menudo se pueden simplificar enormemente.
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 manera 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 genera inseguridad. Al limitar la "superposición" y el número de consultas, se puede lograr una base de datos segura.
Richard Lipton con Andrew Tomkins introdujo un algoritmo de programación de intervalos en línea aleatorio , siendo la versión de 2 tamaños fuertemente competitiva y la versión de tamaño k logrando 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 .
Al presentarse un evento, el usuario debe decidir si incluye o no el evento en el cronograma. El algoritmo virtual de 2 tamaños se describe por cómo reacciona ante los intervalos de 1 o k presentados por el adversario:
Nuevamente, se demuestra que este algoritmo de 2 tamaños 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, dado que el problema satisface ciertas propiedades. [5] Probar la corrección de un programa es uno de los problemas más importantes que se presentan en informática. Normalmente, en las pruebas aleatorias, para lograr una probabilidad de error de 1/1000, se deben ejecutar 1000 pruebas. Sin embargo, Lipton muestra que si un problema tiene subpartes "fáciles", las pruebas repetidas de caja negra pueden alcanzar una tasa de error c r , siendo c una constante menor que 1 y r el número de pruebas. Por lo tanto, la probabilidad de error llega 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 ámbito de la teoría de juegos , más concretamente de los juegos no cooperativos , Lipton junto con E. Markakis y A. Mehta demostraron [6] la existencia de estrategias de equilibrio épsilon con apoyo logarítmico en el número de estrategias puras . Además, los resultados de tales estrategias pueden aproximarse en forma épsilon a los resultados de los equilibrios exactos de Nash . El tamaño limitado (logarítmico) del soporte proporciona un algoritmo cuasipolinomial 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 cuyas respuestas 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 el número de muestras necesarias, su algoritmo decide el número de muestras en función de sus tamaños y tiende a mantener constante el tiempo de ejecución (en lugar de lineal en el número de muestras).
DeMillo , Lipton y Perlis [9] criticaron la idea de verificación formal de programas y argumentaron que
Chandra, Furst y Lipton [10] generalizaron la noción de protocolos de comunicación bipartitos a protocolos de comunicación multipartitas. Propusieron un modelo en el que una colección de procesos ( ) tiene acceso a un conjunto de números enteros ( , ) excepto uno de ellos, por lo 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 la 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 suman N?) y obtuvieron un límite inferior utilizando el método de mosaico. Además, aplicaron 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 un tiempo exponencial (o al menos superpolinomial) (este es el famoso problema P versus NP ), o lineal (o al menos superlogarítmico) espacio para resolver. 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 puede calcularse 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 su lectura. –escribir cintas.
