Richard Jay Lipton (nacido el 6 de septiembre de 1946) es un científico informático estadounidense - sudafricano que ha trabajado en la teoría de la informática , la criptografía y la computación del ADN . Lipton es Decano Asociado de Investigación, Profesor y Presidente de Computación Frederick G. Storey en la Facultad de Computación del Instituto de Tecnología de Georgia .
Richard Lipton | |
---|---|
Nació | Richard Jay Lipton 6 de septiembre de 1946 |
alma mater | Carnegie Mellon |
Conocido por | Teorema de Karp-Lipton y teorema del separador plano |
Premios | Premio Knuth (2014) |
Carrera científica | |
Campos | Ciencias de la Computación |
Instituciones | Yale Berkeley Princeton Georgia Tech |
Tesis | Sobre sistemas primitivos de sincronización (1973) |
Asesor de doctorado | David Parnas [1] |
Estudiantes de doctorado | Dan Boneh Avi Wigderson |
Carrera profesional
En 1968, Lipton recibió su licenciatura en matemáticas de la Universidad Case Western Reserve . En 1973, recibió su Ph.D. de la Universidad Carnegie Mellon ; su disertación, dirigida 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 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 .
Teorema de Karp-Lipton
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.
Algoritmos paralelos
Mostrar que un programa P tiene alguna propiedad es un proceso simple si las acciones dentro del programa son ininterrumpidas. 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 solo 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 de un programa P. Por lo tanto, las pruebas de corrección de un sistema paralelo a menudo se pueden simplificar en gran medida.
Seguridad de la base de datos
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] Incluso cuando el usuario está restringido a leer únicamente operaciones en una base de datos, la información segura podría estar en riesgo. 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.
Programación en línea
Richard Lipton con Andrew Tomkins introdujeron un algoritmo de programación de intervalos en línea aleatorio , la versión de 2 tamaños es muy competitiva y la versión de tamaño k logra O (log), así como demostrar un límite inferior teórico de O (log). [4] Este algoritmo utiliza una moneda privada para la aleatorización y una opción "virtual" para engañar a un adversario medio .
Cuando se le presenta un evento, el usuario debe decidir si lo incluye o no en la programación. El algoritmo virtual de 2 tamaños se describe por la forma en que reacciona a los intervalos 1 o k que presenta el adversario:
- Para un intervalo de 1, lanza una moneda justa
- Jefes
- Toma el intervalo
- Cruz
- "Prácticamente" tome el intervalo, pero no haga ningún trabajo. No tome intervalos cortos durante la siguiente unidad de tiempo.
- Para un intervalo k , tome siempre que sea posible.
Una vez más, este algoritmo de dos tamaños se muestra muy competitivo . El algoritmo de tamaño k generalizado que es similar al algoritmo de tamaño 2 se muestra entonces como O (log)-competitivo.
Comprobación del programa
Lipton demostró que las pruebas aleatorias pueden resultar ú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 la informática. Por lo general, 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 , con 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.
- Procesamiento de señales: la transformada rápida de Fourier (FFT) y otras funciones altamente paralelizables son difíciles de verificar manualmente los resultados cuando se escriben en código como FORTRAN , por lo que es muy deseable una forma de verificar rápidamente la corrección.
- Funciones sobre campos finitos y permanentes: supongamos que es un polinomio sobre un campo finito de tamaño q con q > deg ( ƒ ) + 1 . Entonces ƒ se puede probar aleatoriamente de orden deg ( ƒ ) + 1 sobre la base de la función que incluye solo la suma. Quizás la aplicación más importante de esto es la capacidad de verificar de manera eficiente la corrección de la permanente . Cosméticamente similar al determinante, el permanente es muy difícil de verificar si es correcto, pero incluso este tipo de problema satisface las restricciones. Este resultado incluso llevó a los avances de los sistemas de prueba interactivos Karloff-Nisan y Shamir, incluido el resultado IP = PSPACE .
Juegos con estrategias simples
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, los beneficios de tales estrategias pueden aproximarse a los beneficios 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 .
Estimación del tamaño de la consulta
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 pueden 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 del tamaño de las muestras y tiende a mantener el tiempo de ejecución constante (en lugar de lineal en el número de muestras).
Verificación formal de programas
DeMillo , Lipton y Perlis [9] criticaron la idea de verificación formal de programas y argumentaron que
- Las verificaciones formales en informática no desempeñarán el mismo papel clave que las demostraciones en matemáticas.
- La ausencia de continuidad, la inevitabilidad del cambio y la complejidad de la especificación de programas reales harán que la verificación formal de los programas sea difícil de justificar y administrar.
Protocolos multipartitos
Chandra, Furst y Lipton [10] generalizaron la noción de protocolos de comunicación bipartitos a protocolos de comunicación multipartitos. Propusieron un modelo en el que una colección de procesos () tienen acceso a un conjunto de números 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 la comunicación de este modelo, definida como la cantidad de bits transmitidos entre todos los procesos. Como ejemplo, estudiaron la complejidad de un protocolo de k -party para Exactly- N (do all's suma a N?), y obtuvo 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 los programas de ramificación de espacio constante que calculan Exactamente- N .
Compensación de tiempo / espacio SAT
No tenemos forma de probar 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 lineal (o en espacio menos superlogarítmico) para resolver. Sin embargo, en el contexto de la compensación espacio-tiempo , se puede probar 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 ser calculado por 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.
Premios y honores
- Becario Guggenheim , 1981
- Miembro de la Association for Computing Machinery , 1997
- miembro de la Academia Nacional de Ingeniería
- Ganador del premio Knuth , 2014 [12]
Ver también
- SL (complejidad)
- Modelo de protección de aceptación de subvenciones
- Teorema del separador plano
Notas
- ^ Richard Lipton en el Proyecto de genealogía matemática
- ^ Lipton, R (1975) "Reducción: un método para probar las propiedades de los programas paralelos" , Comunicaciones del ACM 18 (12)
- ^ Lipton, R (1979) "Bases de datos seguras: protección contra la influencia del usuario" , "Transacciones ACM en sistemas de bases de datos" 4 (1)
- ^ Lipton, R (1994). Programación de intervalos en línea . Simposio sobre algoritmos discretos . págs. 302–311. CiteSeerX 10.1.1.44.4548 .
- ^ Lipton, R (1991) "Nuevas direcciones en las pruebas", "Computación distribuida DIMACS y criptografía" Vol. 2 página: 191
- ^ Richard Lipton, Evangelos Markakis, Aranyak Mehta (2007) "Jugando con estrategias simples", "EC '03: Actas de la 4ª conferencia ACM sobre comercio electrónico", "ACM"
- ^ Richard J. Lipton, Jeffrey F. Naughton (1990) "Estimación del tamaño de la consulta por muestreo adaptativo", "PODS '90: Actas del noveno simposio ACM SIGACT-SIGMOD-SIGART sobre principios de sistemas de bases de datos"
- ^ Richard J. Lipton, Jeffrey F. Naughton, Donovan A. Schneider (1990) "SIGMOD '90: Actas de la conferencia internacional ACM SIGMOD de 1990 sobre gestión de datos"
- ^ Richard A. DeMillo, Richard J. Lipton, Alan J. Perlis (1979) "Procesos sociales y pruebas de teoremas y programas", "Comunicaciones de la ACM, volumen 22 número 5"
- ^ AK Chandra, ML Furst y RJ Lipton (1983) "Protocolos multipartitos", "En STOC, páginas 94-99. ACM, 25-2"
- ^ L. Fortnow, R. Lipton, D. van Melkebeek y A. Viglas (2005) "Límites inferiores de tiempo-espacio para la satisfacción", "J. ACM, 52: 835–865, 2005. Versión preliminar CCC '2000"
- ^ "ACM concede el premio Knuth al pionero por los avances en algoritmos y teoría de la complejidad" . Asociación para Maquinaria de Computación. 15 de septiembre de 2014. Archivado desde el original el 20 de septiembre de 2014.
Otras lecturas
- " Bodas: Kathryn Farley, Richard Lipton ", The New York Times , 5 de junio de 2016.
enlaces externos
- Su blog personal "La letra perdida de Gödel y P = NP"