Richard 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.

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.[1] 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.

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.[2] 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.

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${\displaystyle \vartriangle ^{1+\epsilon }}$), además de demostrar un límite inferior teórico de O (log${\displaystyle \vartriangle }$).[3] 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${\displaystyle \vartriangle ^{1+\epsilon }}$).

Lipton demostró que las pruebas aleatorias pueden ser demostrablemente útiles, dado que el problema satisface ciertas propiedades.[4] 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 ${\displaystyle 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.

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[5] 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.

Lipton y J. Naughton presentaron un algoritmo de muestreo aleatorio adaptativo para consultas de bases de datos[6][7] 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).

DeMillo, Lipton y Perlis[8] 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.

Chandra, Furst y Lipton[9] 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 (${\displaystyle P_{0},P_{1},\ldots ,P_{k-1}}$) tiene acceso a un conjunto de enteros (${\displaystyle a_{0}}$, ${\displaystyle a_{1},\ldots ,a_{k-1}}$) excepto a uno de ellos, de modo que a ${\displaystyle P_{i}}$ se le niega el acceso a ${\displaystyle 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 ${\displaystyle 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.

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[10] 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.