Richard Lipton

Richard Lipton
Información personal
Nacimiento	6 de septiembre de 1946 (77 años)
Residencia	Atlanta
Nacionalidad	Estadounidense
Educación
Educación	doctorado
Educado en	Universidad Carnegie Mellon
Supervisor doctoral	David Parnas
Información profesional
Ocupación	Informático teórico, profesor universitario y matemático
Empleador	Instituto de Tecnología de Georgia
Estudiantes doctorales	Avi Wigderson
Miembro de	Academia Estadounidense de las Artes y las Ciencias Academia Nacional de Ingeniería Association for Computing Machinery
Sitio web	www.scs.gatech.edu/people/richard-lipton
Distinciones	ACM Fellow Beca Guggenheim Premio Knuth (2014)

Richard Jay Lipton (nacido el 6 de septiembre de 1946) es un informático teórico estadounidense, decano asociado de investigación, profesor y presidente de informática Frederick G. Storey en la Facultad de informática del Instituto de Tecnología de Georgia. Ha trabajado en ciencia computacional teórica, criptografía y computación basada en ADN.

Carrera

En 1968, Lipton recibió su título universitario en matemáticas por la Universidad Case de la Reserva Occidental. En 1973, obtuvo su doctorado por la Universidad Carnegie Mellon; su disertación, supervisada por David Parnas, se tituló Sobre sistemas primitivos de sincronización. Después de graduarse, Lipton enseñó en Yale de 1973 a 1978, en Berkeley de 1978 a 1980 y luego en Princeton de 1980 a 2000. Desde 2000 ha estado trabajando en Georgia Tech. Mientras estuvo en Princeton, Lipton trabajó en el campo de la computación basada en ADN. Desde 1996 ha sido el principal científico consultor de Telcordia. En 1999 fue elegido miembro de la Academia Nacional de Ingeniería por la aplicación práctica de la teoría informática.

Trabajos destacados

Teorema de Karp-Lipton

En 1980, junto con Richard Karp, Lipton demostró que si el problema de satisfacibilidad booleana se puede resolver mediante circuitos booleanos con un número polinomial de puertas lógicas, entonces la jerarquía polinómica colapsa a su segundo nivel.

Algoritmos paralelos

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 comprobar que el programa reducido tiene esa propiedad si y solo si el programa original tiene la propiedad.​ 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 bases 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 para que no se filtre información privada o secreta.​ Incluso cuando el usuario está restringido a solo leer 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 organizaciones o candidatos políticos. Si se le da acceso a promedios de datos y acceso de consulta 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 delimitar 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 aleatorizado, siendo la versión de dos tamaños muy competitiva y la versión de tamaño k logrando O (log$\vartriangle ^{1+\epsilon }$), además de demostrar un límite inferior teórico de O (log$\vartriangle$).​ Este algoritmo utiliza una moneda privada (cara y cruz) para la aleatorización y una opción "virtual" para engañar a un adversario medio.

Ante la presentación de un evento, el usuario debe decidir si incluir o no el evento en la programación. El algoritmo virtual de 2 tamaños se describe por cómo reacciona a los intervalos de 1 o k que presenta el adversario:

• Para un intervalo de 1, lanza una moneda justa

  • Cara

    Tomar el intervalo

    Cruz

    "Prácticamente" toma el intervalo, pero no hace ningún trabajo. No toma un intervalo corto para la siguiente unidad de tiempo.

• Para un intervalo k, toma siempre que sea posible.

Una vez más, se muestra que este algoritmo de 2 tamaños es fuertemente competitivo. El algoritmo de tamaño k generalizado, que es similar al algoritmo de tamaño 2, se muestra entonces como competitivo en O (log$\vartriangle ^{1+\epsilon }$).

Comprobación de programas

Lipton demostró que las pruebas aleatorias pueden ser demostrablemente útiles, dado que el problema satisface ciertas propiedades.​ Demostrar la corrección de un programa es uno de los problemas más importantes que se presentan en 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 de caja negra repetidas pueden alcanzar una tasa de error c^r, con c una constante menor que 1 y r siendo el número de pruebas. Por lo tanto, la probabilidad de error tiende a cero exponencialmente y crece rápidamente a medida que r crece.

Esta técnica es útil para comprobar la corrección de muchos tipos de aplicaciones para la resolución de problemas:

• Procesamiento de señales: la transformada rápida de Fourier y otras funciones altamente paralelizables son difíciles de verificar manualmente cuando se escriben en código como FORTRAN, por lo que se requiere una forma de verificar rápidamente su corrección.
• Funciones sobre cuerpos finitos y permanentes: supóngase que $f(x_{1},\dots ,x_{n})$ es un polinomio sobre un cuerpo finito de tamaño q con q > deg(ƒ) + 1. Entonces ƒ es aleatoriamente comprobable 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 este principio es la capacidad de verificar de manera eficiente la exactitud de un permanente. Con propiedades similares al determinante, el permanente es muy difícil de verificar, pero incluso este tipo de problema satisface las restricciones. Este resultado incluso condujo a los avances en sistemas de prueba interactivos desarrollados por Karloff-Nisan y Shamir, incluido el resultado IP = PSPACE.

Juegos con estrategias simples

En el área de la teoría de juegos, más concretamente de juegos no cooperativos, Lipton junto con E. Markakis y A. Mehta demostraron​ la existencia de estrategias de equilibrio épsilon con soporte logarítmico en el número de estrategias puras. Además, el pago de dichas estrategias puede aproximarse en épsilon a los pagos de un equilibrio de Nash exacto. El tamaño limitado (logarítmico) del soporte proporciona un algoritmo cuasi-polinómico natural para determinar el equilibrio épsilon.

Estimación del tamaño de consulta

Lipton y J. Naughton presentaron un algoritmo de muestreo aleatorio adaptativo para consultas de bases de datos​​ que es aplicable a cualquier consulta cuyas respuestas se pueden dividir en subconjuntos separados. A diferencia de la mayoría de los algoritmos de estimación de muestreo, que determinan de forma estática 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 dependiendo de la cantidad de muestras).

Verificación formal de programas

DeMillo, Lipton y Perlis​ criticaron la idea de verificación formal de programas y argumentaron que:

• Las verificaciones formales en informática no jugará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 gestionar.

Protocolos de múltiples partes

Chandra, Furst y Lipton​ generalizaron la noción de protocolos de comunicación de dos partes a protocolos de comunicación de múltiples partes. Propusieron un modelo en el que una colección de procesos ($P_{0},P_{1},\ldots ,P_{k-1}$) tiene acceso a un conjunto de enteros ($a_{0}$, $a_{1},\ldots ,a_{k-1}$) excepto a uno de ellos, de modo que a $P_{i}$ se le niega el acceso a $a_{i}$. Estos procesos pueden 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 partido k para exactamente N (¿todos los $a_{i}$ suman N?) y obtuvieron un límite inferior utilizando un 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 SAT de tiempo/espacio

No se tiene forma de probar que el problema de satisfacibilidad booleana (a menudo abreviado como SAT), que es NP-completo, requiere un tiempo exponencial (o al menos superpolinómico) (este es el famoso problema P frente a NP) o un espacio lineal (o al menos superlogarítmico) para ser resuelto. Sin embargo, en el contexto de situación de compromiso espacio-tiempo, se puede probar que el SAT no se puede calcular si se aplican restricciones tanto al tiempo como al espacio. L. Fortnow, Lipton, D. van Melkebeek y A. Viglas​ demostraron que no puede ser calculado por una máquina de Turing que emplee como máximo O(n^1.1) pasos y como máximo O(n^0.1) celdas de sus cintas de lectura y escritura.

Premios y distinciones

• Guggenheim Fellow, 1981
• Académico de la Association for Computing Machinery, 1997
• Miembro de Academia Nacional de Ingeniería (Estados Unidos)​
• Ganador del premio Knuth en 2014​

Véase también

• SL (clase de complejidad)
• Modelo Take-Grant
• Teorema del separador plano

Lectura adicional

• "Bodas: Kathryn Farley, Richard Lipton", The New York Times, 5 de junio de 2016.

Enlaces externos

• Su blog personal "La carta perdida de Gödel y P=NP"

• Datos: Q7326742