Los resultados más influyentes de Lipton

Richard J. Lipton ha sido seleccionado como el ganador del Premio Knuth 2014 "por Introducción de nuevas ideas y técnicas".

¿Cuáles son para usted las principales ideas y técnicas nuevas que desarrolló Lipton?

Nota. Esta pregunta se convertirá en wiki de la comunidad, por favor ponga una idea, técnica o resultado por respuesta

El teorema del separador plano establece que en cualquier gráfico -vertex plano G existe un conjunto de O ( $n$$G$vértices cuya eliminación deja el gráfico desconectado en al menos dos componentes más o menos equilibrados. Además, tal conjunto se puede encontrar en tiempo lineal. Este resultado (ajustado),probado por Lipton y Tarjan(mejorando en un resultado anterior de Ungar) es una herramienta poderosa para diseñar algoritmos en gráficos planos. Proporciona muchos algoritmos exactos de tiempo subexponencial para problemas NP-hard y algoritmos de aproximación de tiempo polinomial mejorados. Mirar lapágina de Wikipediaes un buen punto de partida para explorar las numerosas aplicaciones. Lipton y Tarjan escribieronunaencuesta inicialcon detalles de varias aplicaciones en 1980.$O(\sqrt{n})$

El teorema de Karp-Lipton establece que no puede tener circuitos booleanos de tamaño polinómico a menos que la jerarquía polinómica se colapse a su segundo nivel.$\mathsf{NP}$

Dos implicaciones de este teorema para la teoría de la complejidad:

• probablemente no tiene circuitos booleanos de tamaño polinómico; probar límites inferiores en los tamaños de circuito es, por lo tanto, un enfoque posible para separar las clases de complejidad.$\mathsf{NP}$
• Varios resultados se basan en este teorema para probar las separaciones de clases de complejidad (por ejemplo, el teorema de Kannan).

Auto-reducibilidad aleatoria del permanente . Lipton demostró que si existe un algoritmo que calcule correctamente la fracción permanente de de todo F n × n , donde F es un campo finito de tamaño de al menos 3 n , entonces este algoritmo puede usarse como una caja negra para calcular el permanente de cualquier matriz con alta probabilidad.$1-1/(3n)$$\mathbb{F}^{n\times n}$$\mathbb{F}$$3n$

La idea principal es que el permanente es un polinomio de bajo grado, por lo que su composición con una función afín univariada es un polinomio univariado de bajo grado (en x ) y se puede aprender exactamente de un pequeño número de valores mediante interpolación . Puede elegir un B aleatorio para que la composición se distribuya como el permanente de una matriz aleatoria para cualquier x . En x = 0 el polinomio univariado es sólo la permanente de una . Los detalles se pueden encontrar en el Capítulo 8 de Arora Barak .$A + xB$$x$$B$$x$$x = 0$$A$

Este enfoque algebraico ha sido extremadamente influyente en la teoría de la complejidad. Las ideas de Lipton condujeron eventualmente a la prueba del teorema IP = PSPACE, la prueba del teorema PCP y a resultados en códigos locales de corrección de errores.

No estoy 100% seguro de si la explicación a continuación es históricamente precisa. Si no es así, no dude en editar o eliminar.

Las pruebas de mutación fueron inventadas por Lipton. Las pruebas de mutación pueden verse como una forma de medir la calidad o efectividad de un conjunto de pruebas. La idea clave es inyectar fallas en el programa que se va a probar (es decir, mutar el programa), preferiblemente los tipos de fallas que un programador humano puede cometer, y ver si el conjunto de pruebas encuentra las fallas introducidas. Un ejemplo típico del tipo de prueba de mutación de falla que podría introducirse sería reemplazar x> 0 por x <0, o reemplazar x por x + 1 o x-1. La fracción de fallas detectadas por el conjunto de pruebas es el "puntaje de adecuación de mutación" de un conjunto de pruebas. Hablando muy libremente, uno puede pensar en esto como un método de Monte-Carlo para calcular el puntaje de adecuación de la mutación.

De manera más abstracta, se podría decir que las pruebas de mutación ponen de manifiesto una simetría o dualidad entre un programa y sus conjuntos de pruebas: no solo se puede usar el conjunto de pruebas para tener más confianza en la exactitud de un programa, sino que, a la inversa, un programa puede solía ganar confianza sobre la calidad de un conjunto de pruebas.

A la luz de esta dualidad, las pruebas de mutación también están conceptualmente cerca de la inyección de falla . Ambos son técnicamente similares pero tienen diferentes propósitos. Las pruebas de mutación buscan medir la calidad del conjunto de pruebas, mientras que la inyección de fallas busca establecer la calidad del programa, generalmente la calidad de su manejo de errores.

Recientemente, las ideas de las pruebas de mutación se han utilizado para probar (formalizaciones de) teorías lógicas. Parafraseando el resumen de (4): Al desarrollar formalizaciones no triviales en un probador de teoremas, se dedica una cantidad considerable de tiempo a "depurar" las especificaciones y teoremas. Por lo general, se descubren especificaciones o teoremas incorrectos durante los intentos de prueba fallidos. Esta es una forma costosa de depuración. Por lo tanto, a menudo es útil probar conjeturas antes de embarcarse en una prueba. Una posible forma de hacerlo es asignar valores aleatorios a las variables libres de la conjetura y luego evaluarla. (4) utiliza mutaciones para evaluar la calidad de los generadores de casos de prueba utilizados.

Historia . De (1): La historia de las pruebas de mutación se remonta a 1971 en un artículo estudiantil de Richard Lipton [...] El nacimiento del campo también se puede identificar en otros documentos publicados a finales de la década de 1970 por Lipton et al. (2) así como Hamlet (3).

1. Repositorio de prueba de mutación: Teoría de prueba de mutación .

2. RA DeMillo, RJ Lipton, FG Sayward, Consejos sobre la selección de datos de prueba: Ayuda para el programador practicante .

3. RG Hamlet, Programas de prueba con la ayuda de un compilador .

4. S. Berghofer, T. Nipkow, Pruebas aleatorias en Isabelle / HOL. .

Schwartz - Zippel - DeMillo-Lipton Lemma es una herramienta fundamental en la complejidad aritmética: básicamente establece que si desea saber si un circuito aritmético representa el polinomio cero, todo lo que necesita es evaluar el circuito en una entrada. Entonces obtendrá un valor distinto de cero con buena probabilidad si el circuito no representa el polinomio cero.

Este es un lema particularmente importante ya que no se conoce un algoritmo determinista de tiempo polinómico para este problema.

El lema generalmente se conoce como Lema de Schwartz-Zippel . Se puede encontrar una historia de este lema en el blog de Lipton .

La cobertura en los sistemas de adición de vectores es EXPSPACE-hard : en RJ Lipton, El problema de accesibilidad requiere espacio exponencial , Informe de investigación 63, Universidad de Yale, 1976.

$d$$\langle v_0,A\rangle$$v_0$$\mathbb{N}^d$$A$$\mathbb{Z}^d$$\mathbb{N}^d$$v\to v'$$u$$A$$v'=v+u$$v'$$v$$\mathbb{N}^d$$v_0\to v_1\to\cdots\to v_n$$v_n\geq v$$\mathbb{N}^d$$v_n(i)\geq v(i)$$1\leq i\leq d$. Combinado con un límite superior EXPSPACE probado por C. Rackoff en 1978 , el resultado de Lipton muestra la integridad de EXPSPACE.

$v_n=v$

Multiparty complejidad de la comunicación y el modelo Número-on-frente fueron introducidos por Ashok K. Chandra , Merrick L. Furst y Richard J. Lipton en Multiparty Protocolos , STOC 1983, doi: 10.1145 / 800,061.808737 .

El modelo multiparte es una extensión natural del modelo bipartidista de complejidad de comunicación de Yao , donde Alice y Bob tienen mitades no superpuestas de los bits de entrada y desean comunicarse para calcular una función predeterminada de toda la entrada. Sin embargo, extender la partición de los bits de entrada a más partes a menudo no es muy interesante (para los límites inferiores, generalmente se pueden considerar las dos primeras partes).

$k$$k$$n$

$n$

$N$$k$$N$$k=3$$N$$O(\sqrt{\log N})$$N \le k(2^n-1)$$O(\sqrt{n})$

$^0$

$N$