Richard Lipton

Richard Lipton
Geboren	Richard Jay Lipton 6. September 1946 (Alter 75)
Alma Mater	Carnegie Mellon
Bekannt für	Karp -Lipton -Theorem und Planar -Separator -Theorem
Auszeichnungen	Knuth -Preis (2014)
Wissenschaftliche Karriere
Felder	Informatik
Institutionen	Yale Berkeley Princeton Georgia Tech
These	Auf Synchronisation primitive Systeme (1973)
Doktorand	David Parnas[1]
Doktorand	Dan Boneh Vijaya Ramachandran Avi Wigderson

Richard Jay Lipton (geboren am 6. September 1946) ist ein amerikanisch Informatiker Wer ist Associate Dean of Research, Professor und der Frederick G. Storey Chair für Computing am College of Computing am Georgia Institute of Technology. Er hat in der Arbeit gearbeitet Informatik Theorie, Kryptographie, und DNA Computing.

Karriere

1968 erhielt Lipton seinen Bachelor -Abschluss in Mathematik aus Fall Western Reserve University. 1973 erhielt er seine Ph.D. aus Carnegie Mellon Universität; seine Dissertation, überwacht von David Parnas, ist berechtigt Auf Synchronisation primitive Systeme. Nach dem Abschluss unterrichtete Lipton bei Yale 1973–1978, at Berkeley 1978–1980 und dann bei Princeton 1980–2000. Seit 2000 ist Lipton bei Georgia Tech. Während seiner Zeit bei Princeton arbeitete Lipton auf dem Gebiet von DNA Computing. Seit 1996 ist Lipton der Hauptberatungswissenschaftler bei Telkordien. 1999 wurde Lipton zum Mitglied der des Nationale Akademie des Ingenieurwesens Für die Anwendung der Informatik Theorie auf die Praxis.

Karp -Lipton -Theorem

1980 zusammen mit Richard M. Karp, Lipton hat das bewiesen, wenn Sa kann durch gelöst werden Boolesche Schaltungen mit einer Polynomzahl von Logik -Tore, dann ist die Polynomhierarchie bricht auf seine zweite Ebene zusammen.

Parallelalgorithmen

Das Zeigen, dass ein Programm P über eine Eigenschaft verfügt, ist ein einfacher Prozess, wenn die Aktionen im Programm ununterbrochen sind. Wenn die Aktion jedoch unterbrochen ist, zeigte Lipton, dass durch eine Art von Reduktion und Analyse gezeigt werden kann, dass das reduzierte Programm diese Eigenschaft hat, wenn das ursprüngliche Programm über die Eigenschaft verfügt.^[2] Wenn die Reduzierung durch die Behandlung unterbrochener Operationen als eine große ununterbrochene Wirkung erfolgt, können Eigenschaften für ein Programm P. Selbst mit diesen entspannten Bedingungen nachgewiesen werden.

Datenbanksicherheit

Lipton untersuchte und erstellte Datenbank -Sicherheitsmodelle darüber, wie und wann die Abfragen von Benutzern einer Datenbank so eingeschränkt werden sollen, dass private oder geheime Informationen nicht durchgesickert werden.^[3] Selbst wenn der Benutzer nur darauf beschränkt ist, Operationen in einer Datenbank zu lesen, können sichere Informationen gefährdet sein. Wenn Sie beispielsweise eine Datenbank mit Kampagnenspenden abfragen, kann es dem Benutzer ermöglichen, die einzelnen Spenden an politische Kandidaten oder Organisationen zu entdecken. Wenn ein Benutzer die Eigenschaften dieser Durchschnittswerte ausnutzen, um illegale Informationen zu erhalten, kann ein Benutzer zugreifen, wenn er zugänglich ist. Diese Abfragen haben eine große "Überlappung", die die Unsicherheit erzeugt. Durch Begrenzung der "Überlappung" und Anzahl der Abfragen kann eine sichere Datenbank erreicht werden.

Online -Planung

Richard Lipton mit Andrew Tomkins führte eine randomisierte Einführung vor Online -Intervallplanungsalgorithmus, Die 2-Größe-Version ist stark wettbewerbsfähig und die k-Size -Version Erreichung von O (Protokoll${\ displayStyle \ VarTiangle ^{1+ \ Epsilon}}$) und demonstrieren sowie eine theoretische untere Unterbringung von O (log${\ displayStyle \ Vartriangle}$).^[4] Dieser Algorithmus verwendet eine Privatkoin zur Randomisierung und eine "virtuelle" Wahl, um a zu täuschen mittlerer Gegner.

Wenn der Benutzer mit einem Ereignis präsentiert wird, muss er entscheiden, ob das Ereignis in den Zeitplan aufgenommen werden soll oder nicht. Der virtuelle 2-Größen-Algorithmus wird dadurch beschrieben, wie er auf 1-Interval reagiert oder k-Intervals werden vom Gegner präsentiert:

• Für einen 1-Interval umblättern Sie eine faire Münze

  • Köpfe

    Nehmen Sie das Intervall

    Schwänze

    "Praktisch" nehmen das Intervall, aber keine Arbeit. Nehmen Sie für die nächste 1 Zeiteinheit kein kurzes Intervall.

• Für ein k-Interval, nehmen Sie nach Möglichkeit ein.

Auch hier wird gezeigt, dass dieser 2-Größe-Algorithmus stark ist.wettbewerbsfähig. Die verallgemeinerten k-Size-Algorithmus, der dem 2-Größe-Algorithmus ähnelt, wird dann als O (log${\ displayStyle \ VarTiangle ^{1+ \ Epsilon}}$)-wettbewerbsfähig.

Programmprüfung

Lipton zeigte, dass randomisierte Tests nachweislich nützlich sein können, da das Problem bestimmte Eigenschaften erfüllt.^[5] Beweis Korrektheit eines Programms ist eines der wichtigsten Probleme in der Informatik. Normalerweise müssen bei randomisierten Tests 1000 Tests durchgeführt werden, um eine 1/1000 Chance eines Fehlers zu erreichen. Lipton zeigt jedoch, dass, wenn ein Problem "einfache" Unterparts hat, wiederholte Black-Box-Tests durchführen können c^r Fehlerrate mit c eine Konstante weniger als 1 und r die Anzahl der Tests sein. Daher die Fehlerwahrscheinlichkeit geht exponentiell auf Null schnell wie r wächst.

Diese Technik ist nützlich, um die Richtigkeit vieler Arten von Problemen zu überprüfen.

• Signalverarbeitung: Schnelle Fourier -Transformation (FFT) und andere hoch parallelisierbare Funktionen sind schwer zu manuell zu prüfen, wenn sie in Code geschrieben wurden, z. B. ForranEine Möglichkeit, die Korrektheit schnell zu überprüfen, ist sehr gewünscht.
• Funktionen über endliche Felder und die Permanent: Angenommen, das ${\ displayStyle f (x_ {1}, \ dots, x_ {n})}$ ist ein Polynom über einem endlichen Größenfeld q mit q > Grad (ƒ) + 1. Dann ƒ ist zufällig bestellbar Gradƒ) + 1 Über die Funktionsbasis, die nur Addition enthält. Die vielleicht wichtigste Anwendung daraus ist die Fähigkeit, die Richtigkeit der Richtigkeit effizient zu überprüfen dauerhaft. Kosmetisch ähnlich wie die Determinante, ist die Ständige sehr schwer die Korrektheit zu überprüfen, aber selbst diese Art von Problem erfüllt die Einschränkungen. Dieses Ergebnis führte sogar zu den Durchbrüchen von Interaktive Proof -Systeme Karloff-Nisan und Shamir, einschließlich des Ergebnisses IP = PSPACE.

Spiele mit einfachen Strategien

In der Gegend von Spieltheoriegenauer gesagt von Nicht kooperative Spiele, Lipton zusammen mit E. markakis und A. Mehta bewiesen^[6] die Existenz von Epsilon-Gleichgewicht Strategien mit Unterstützung logarithmisch in der Anzahl von reine Strategien. Darüber hinaus kann die Auszahlung solcher Strategien die genauen Auszahlungen epsilonimieren Nash -Gleichgewichte. Die begrenzte (logarithmische) Größe der Unterstützung bietet einen natürlichen quasipolynomialen Algorithmus zum Berechnen Epsilon-Gleichgewicht.

Abfragebetriebsschätzung

Lipton und J. Naughton präsentierten einen adaptiven zufälligen Stichprobenalgorithmus für die Datenbankabfrage^[7][8] Dies gilt für jede Abfrage, für die Antworten auf die Abfrage in disjunkte Teilmengen aufgeteilt werden können^{[Klarstellung erforderlich]}. Im Gegensatz zu den meisten Stichprobenschätzungsalgorithmen, die statisch die Anzahl der benötigten Proben bestimmen, entscheidet ihr Algorithmus die Anzahl der Proben basierend auf den Größen der Proben und neigt dazu, die Laufzeit konstant zu halten (im Gegensatz zu linear in der Anzahl der Proben).

Formale Überprüfung der Programme

Demillo, Lipton und Perlis^[9] kritisierte die Idee der formalen Überprüfung von Programmen und argumentierte das

• Formale Überprüfungen in der Informatik spielen nicht die gleiche Schlüsselrolle wie die Beweise in der Mathematik.
• Das Fehlen von Kontinuität, die Unvermeidlichkeit des Wandels und die Komplexität der Spezifikation realer Programme erschweren die formelle Überprüfung der Programme zu rechtfertigen und zu verwalten.

Mehrparteienprotokolle

Chandra, Furst und Lipton^[10] verallgemeinerte den Begriff von Kommunikationsprotokollen mit zwei Parteien auf Mehrparteien-Kommunikationsprotokolle. Sie schlugen ein Modell vor, bei dem eine Sammlung von Prozessen (${\ displayStyle p_ {0}, p_ {1}, \ ldots, p_ {k-1}}$) Zugriff auf eine Reihe von Ganzzahlen (${\ displayStyle a_ {0}}$, ${\ displayStyle a_ {1}, \ ldots, a_ {k-1}}$) außer einem von ihnen, so dass das ${\ displayStyle p_ {i}}$ wird den Zugang zu verweigert zu ${\ displayStyle a_ {i}}$. Diese Prozesse dürfen kommunizieren, um einen Konsens über ein Prädikat zu erreichen. Sie untersuchten die Kommunikationskomplexität dieses Modells, definiert als die Anzahl der Bits, die zwischen allen Prozessen ausgestrahlt wurden. Als Beispiel untersuchten sie die Komplexität von a k-Party-Protokoll für genau-N (alles machen ${\ displayStyle a_ {i}}$Summe bis n?) Und erhielt eine untere Grenze mit der Kachelmethode. Sie wandten dieses Modell weiter an, um allgemeine Verzweigungsprogramme zu untersuchen, und erhielten eine Zeit unter der Untergrenze für Konstantraumzweigerungsprogramme, die genau berechnen.N.

Zeit/Weltraum -Sat -Kompromiss

Wir haben keine Möglichkeit, das zu beweisen Boolesche Zufriedenheitsproblem (oft abgekürzt wie SAT), was ist NP-Completeerfordert eine exponentielle (oder zumindest superpolynomiale) Zeit (dies ist die berühmte P gegen NP -Problem) oder linearer (oder zumindest super-logarithmischer) Raum zu lösen. Im Kontext von Weltraum -Zeit -KompromissMan kann beweisen, dass SAT nicht berechnet werden kann, wenn wir Einschränkungen sowohl für Zeit als auch für den Raum anwenden. L. Fortnow, Lipton, D. Van Melkebeek und A. Viglas^[11] bewiesen, dass SAT nicht von einer Turing -Maschine berechnet werden kann, die höchstens o dauert (n^1.1) Schritte und höchstens o ((n^0,1) Zellen seiner Leseschreibbänder.

Auszeichnungen und Ehrungen

• Guggenheim Fellow, 1981
• Gefährte des Verband für Rechenmaschinen, 1997
• Mitglied von Nationale Akademie des Ingenieurwesens^[12]
• Knuth -Preis Gewinner, 2014^[13]

Siehe auch

• SL (Komplexität)
• Nehmen Sie ein Grant-Schutzmodell
• Planar -Separator -Theorem

Anmerkungen

Weitere Lektüre

• "Hochzeiten: Kathryn Farley, Richard Lipton",", Die New York Times, 5. Juni 2016.

Externe Links

• Sein persönlicher Blog "Gödels verlorener Brief und P = NP"