Liptons einflussreichste Ergebnisse

Richard J. Lipton wurde zum Gewinner des Knuth-Preises 2014 für die Einführung neuer Ideen und Techniken gewählt.

Was sind für Sie die wichtigsten neuen Ideen und Techniken, die Lipton entwickelt hat?

Hinweis. Diese Frage wird zum Community-Wiki. Bitte geben Sie eine Idee, Technik oder ein Ergebnis pro Antwort an.

Der Planar Separator Theorem besagt, dass in jedem planaren Vertex-Graphen eine Menge von Vertices existiert, deren Entfernung den Graphen in mindestens zwei grob ausgeglichene Komponenten zerlegt. Darüber hinaus kann eine solche Menge in linearer Zeit gefunden werden. Dieses (enge) Ergebnis, das von Lipton und Tarjan (gegenüber einem früheren Ergebnis von Ungar) bewiesen wurde, ist ein leistungsfähiges Werkzeug zum Entwerfen von Algorithmen für planare Graphen. Es gibt viele exakte subexponentielle Zeitalgorithmen für NP-harte Probleme und verbesserte Algorithmen zur Polynomzeitnäherung. Ein Blick auf die Wikipedia-Seite bietet einen guten Ausgangspunkt, um die zahlreichen Anwendungen zu erkunden. Eine frühe UmfrageG O ( $n$$G$$O(\sqrt{n})$ mit Details einer Reihe von Anwendungen wurde von Lipton und Tarjan im Jahr 1980 geschrieben.

Karp-Lipton Theorem besagtdass nicht Polynom-size Boolesche Schaltungen haben kannwenn die Polynomial Hierarchie in die zweite Ebene zusammenbricht.$\mathsf{NP}$

Zwei Implikationen dieses Theorems für die Komplexitätstheorie:

• wahrscheinlich keine polynomgroßen Booleschen Schaltkreise; Der Nachweis der unteren Schranken der Schaltungsgrößen ist daher ein möglicher Ansatz zur Trennung von Komplexitätsklassen.$\mathsf{NP}$
• Mehrere Ergebnisse basieren auf diesem Theorem, um die Trennung von Komplexitätsklassen zu beweisen (zum Beispiel Kannans Theorem).

Zufällige Selbstreduzierbarkeit der bleibenden . Lipton zeigte, dass, wenn es einen Algorithmus gibt, der die bleibende Zahl von aller F n × n korrekt berechnet , wobei F ein endliches Feld mit einer Größe von mindestens 3 n ist , dieser Algorithmus als verwendet werden kann eine Blackbox, um die bleibende Zahl einer Matrix mit hoher Wahrscheinlichkeit zu berechnen .$1-1/(3n)$$\mathbb{F}^{n\times n}$$\mathbb{F}$$3n$

Die Hauptidee ist, dass die bleibende Karte ein Polynom mit niedrigem Grad ist, daher ist ihre Zusammensetzung mit einer univariaten affinen Funktion ein univariates Polynom mit niedrigem Grad (in x ) und kann durch Interpolation aus einer kleinen Anzahl von Werten genau gelernt werden . Sie können ein zufälliges B auswählen, sodass die Komposition als permanente einer zufälligen Matrix für ein beliebiges x verteilt wird . Bei x = 0 das univariate Polynom ist nur die permanent von A . Details finden Sie in Kapitel 8 von Arora Barak .$A + xB$$x$$B$$x$$x = 0$$A$

Dieser algebraische Ansatz war in der Komplexitätstheorie äußerst einflussreich. Liptons Ideen führten schließlich zum Beweis des IP = PSPACE-Theorems, zum Beweis des PCP-Theorems und zu Ergebnissen lokaler Fehlerkorrekturcodes.

Ich bin nicht zu 100% sicher, ob die folgende Erklärung historisch korrekt ist. Ist dies nicht der Fall, können Sie sie jederzeit bearbeiten oder entfernen.

Mutationstests wurden von Lipton erfunden. Mutationstests können als ein Weg gesehen werden, die Qualität oder Wirksamkeit einer Testsuite zu messen. Die Schlüsselidee besteht darin, Fehler in das zu testende Programm einzufügen (dh das Programm zu mutieren), vorzugsweise die Arten von Fehlern, die ein menschlicher Programmierer wahrscheinlich macht, und zu prüfen, ob die Testsuite die eingeführten Fehler findet. Ein typisches Beispiel für die Art der Fehlermutationstests könnte darin bestehen, x> 0 durch x <0 oder x durch x + 1 oder x-1 zu ersetzen. Der Bruchteil der von der Testsuite festgestellten Fehler ist der "Mutations-Angemessenheits-Score" einer Testsuite. Man kann sich dies, wenn man sehr locker spricht, als Monte-Carlo-Methode zur Berechnung des Mutations-Angemessenheits-Scores vorstellen.

Abstrakter könnte man sagen, dass Mutationstests eine Symmetrie oder Dualität zwischen einem Programm und seinen Testsuiten in den Vordergrund stellen: Die Testsuite kann nicht nur verwendet werden, um mehr Vertrauen in die Korrektheit eines Programms zu gewinnen, sondern auch umgekehrt verwendet, um Vertrauen in die Qualität einer Testsuite zu gewinnen.

Angesichts dieser Dualität stehen Mutationstests auch konzeptionell kurz vor der Fehlerinjektion . Beide sind technisch ähnlich, haben aber unterschiedliche Zwecke. Beim Mutationstest wird versucht, die Qualität der Testsuite zu messen, während bei der Fehlerinjektion die Qualität des Programms ermittelt werden soll, normalerweise die Qualität der Fehlerbehandlung.

Vor kurzem wurden Ideen aus Mutationstests verwendet, um logische Theorien zu testen (zu formalisieren). Um die Zusammenfassung von (4) zu paraphrasieren: Bei der Entwicklung nicht-trivialer Formalisierungen in einem Theorembeweiser wird viel Zeit für das „Debuggen“ von Spezifikationen und Theoremen aufgewendet. In der Regel werden bei fehlgeschlagenen Beweisversuchen falsche Angaben oder Sätze entdeckt. Dies ist eine teure Form des Debuggens. Daher ist es oft nützlich, Vermutungen zu testen, bevor Sie sich auf einen Beweis einlassen. Eine Möglichkeit besteht darin, den freien Variablen der Vermutung Zufallswerte zuzuweisen und diese auszuwerten. (4) verwendet Mutationen, um die Qualität der verwendeten Testfallgeneratoren zu testen.

Geschichte . Zu (1): Die Geschichte des Mutationstests lässt sich in einer Arbeit von Richard Lipton aus dem Jahr 1971 nachvollziehen. [...] Die Geburt des Feldes lässt sich auch in anderen Arbeiten nachweisen, die Ende der 1970er Jahre von Lipton et al. Veröffentlicht wurden. (2) sowie Hamlet (3).

1. Repository für Mutationstests: Theorie der Mutationstests .

2. RA DeMillo, RJ Lipton, FG Sayward, Hinweise zur Auswahl der Testdaten: Hilfe für den übenden Programmierer .

3. RG Hamlet, Testen von Programmen mit Hilfe eines Compilers .

4. S. Berghofer, T. Nipkow, Stichproben in Isabelle / HOL. .

Schwartz-Zippel-DeMillo-Lipton-Lemma ist ein grundlegendes Werkzeug für die arithmetische Komplexität: Wenn Sie wissen möchten, ob eine arithmetische Schaltung das Nullpolynom darstellt, müssen Sie die Schaltung nur an einem Eingang auswerten. Dann erhalten Sie mit hoher Wahrscheinlichkeit einen Wert ungleich Null, wenn die Schaltung nicht das Nullpolynom darstellt.

Dies ist ein besonders wichtiges Lemma, da für dieses Problem kein polynomzeitdeterministischer Algorithmus bekannt ist.

Die Deckspelze ist üblicherweise als Schwartz-Zippel-Deckspelze bekannt . Eine Geschichte dieses Lemmas finden Sie in Liptons eigenem Blog .

Die Bedeckbarkeit in Vektoradditionssystemen ist EXPSPACE-schwer : In RJ Lipton erfordert das Erreichbarkeitsproblem exponentiellen Raum , Forschungsbericht 63, Yale University, 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$. In Kombination mit einer von C. Rackoff 1978 nachgewiesenen EXPSPACE-Obergrenze zeigt Liptons Ergebnis die Vollständigkeit für EXPSPACE.

$v_n=v$

Multiparty Communication Complexity und das Number-on-Forehead-Modell wurden von Ashok K. Chandra , Merrick L. Furst und Richard J. Lipton in Multi-Party Protocols , STOC 1983, doi: 10.1145 / 800061.808737, vorgestellt .

Das Mehrparteienmodell ist eine natürliche Erweiterung von Yaos Zwei-Parteien-Modell der Kommunikationskomplexität, bei dem Alice und Bob jeweils nicht überlappende Hälften der Eingabebits haben und kommunizieren möchten, um eine vorbestimmte Funktion der gesamten Eingabe zu berechnen. Das Erweitern der Partition der Eingabebits auf mehrere Parteien ist jedoch oft nicht sehr interessant (für Untergrenzen kann man normalerweise nur die ersten beiden Parteien berücksichtigen).

$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$