Richard Lipton - Richard Lipton

Richard Jay Lipton (narozen 6. září 1946) je americký -Jihoafričan počítačový vědec kdo pracoval v teorie počítačových věd, kryptografie, a Výpočet DNA. Lipton je proděkanem pro výzkum, profesorem a předsedou Fredericka G. Storeye v oboru výpočetní techniky na College of Computing at the Gruzínský technologický institut.

Kariéra

V roce 1968 získal Lipton vysokoškolské vzdělání v matematika z Case Western Reserve University. V roce 1973 obdržel Ph.D. z Univerzita Carnegie Mellon; jeho disertační práce, pod dohledem David Parnas, je oprávněn V synchronizačních primitivních systémech. Po absolutoriu Lipton učil na Yale 1973–1978, v Berkeley 1978–1980 a poté v Princeton 1980–2000. Od roku 2000 je Lipton v Georgia Tech. Během pobytu v Princetonu pracoval Lipton v oboru Výpočet DNA. Od roku 1996 je Lipton hlavním konzultantem ve společnosti Telcordia.

Karp – Liptonova věta

V roce 1980 spolu s Richard M. Karp, Lipton dokázal, že pokud SAT lze vyřešit pomocí Booleovské obvody s polynomickým počtem logické brány, pak polynomiální hierarchie se zhroutí na druhou úroveň.

Paralelní algoritmy

Ukázání, že program P má nějakou vlastnost, je jednoduchý proces, pokud jsou akce uvnitř programu nepřerušitelné. Když je však akce přerušitelná, Lipton ukázal, že prostřednictvím typu redukce a analýzy lze ukázat, že redukovaný program má tuto vlastnost právě tehdy, má-li ji původní program.^[2] Pokud se redukce provádí zpracováním přerušitelných operací jako jedné velké nepřerušitelné akce, lze i u těchto uvolněných podmínek prokázat vlastnosti pro program P. Důkazy správnosti paralelního systému lze tedy často značně zjednodušit.

Zabezpečení databáze

Lipton studoval a vytvořil modely zabezpečení databáze o tom, jak a kdy omezit dotazy uživatelů databáze tak, aby nedošlo k úniku soukromých nebo tajných informací.^[3] I když je uživatel omezen pouze na operace čtení v databázi, mohou být ohroženy zabezpečené informace. Například dotaz na databázi darů kampaně by mohl uživateli umožnit objevit jednotlivé dary politickým kandidátům nebo organizacím. Pokud je uživateli poskytnut přístup k průměrům dat a neomezený přístup k dotazům, může uživatel využívat vlastnosti těchto průměrů k získání nezákonných informací. U těchto dotazů se předpokládá, že mají velké „překrytí“ vytvářející nejistotu. Omezením „překrytí“ a počtu dotazů lze dosáhnout zabezpečené databáze.

Online plánování

Richard Lipton s Andrewem Tomkinsem představili randomizované algoritmus online intervalového plánování, verze 2 velikosti je silně konkurenční a k-size verze dosahující O (log${displaystyle vartriangle ^ {1 + epsilon}}$), jakož i prokázání teoretické dolní meze O (log${displaystyle vartriangle}$).^[4] Tento algoritmus používá pro randomizaci soukromou minci a „virtuální“ volbu k oklamání střední protivník.

Při prezentaci události se uživatel musí rozhodnout, zda událost zahrne do plánu. Virtuální algoritmus o velikosti 2 je popsán tím, jak reaguje na 1-interval nebo k-intervaly předkládané protivníkem:

• V intervalu 1 otočte spravedlivou minci

  • Hlavy

    Vezměte interval

    Ocasy

    „Prakticky“ berte interval, ale nedělejte žádnou práci. Následující 1 jednotku času neberte žádný krátký interval.

• Pro k-interval, vezměte, kdykoli je to možné.

Znovu se ukazuje, že tento algoritmus o velikosti 2 je silněkonkurenční. Zobecněný k-size algoritmus, který je podobný 2-size algoritmu, je pak zobrazen jako O (log${displaystyle vartriangle ^ {1 + epsilon}}$)-konkurenční.

Kontrola programu

Lipton ukázal, že randomizované testování může být prokazatelně užitečné, vzhledem k tomu, že problém splňuje určité vlastnosti.^[5] Prokazující správnost programu je jedním z nejdůležitějších problémů počítačových věd. Typicky v randomizovaném testování, aby se dosáhlo pravděpodobnosti chyby 1/1000, musí být spuštěno 1000 testů. Lipton však ukazuje, že pokud má problém „snadné“ dílčí části, může se dosáhnout opakovaného testování černé skříňky C^r chybovost, s C konstanta menší než 1 a r je počet testů. Proto pravděpodobnost chyby jde na nulu exponenciálně rychle jako r roste.

Tato technika je užitečná ke kontrole správnosti mnoha typů problémů.

• Zpracování signálu: rychlá Fourierova transformace (FFT) a další vysoce paralelizovatelné funkce je obtížné ručně zkontrolovat výsledky při zápisu v kódu, jako je FORTRAN, takže je velmi žádoucí způsob rychlé kontroly správnosti.
• Funkce přes konečná pole a trvalé: Předpokládejme, že ${displaystyle f (x_ {1}, tečky, x_ {n})}$ je polynom přes konečné pole velikosti q s q > deg (ƒ) + 1. Pak ƒ je náhodně testovatelné objednávky deg (ƒ) + 1 přes funkční základ, který zahrnuje pouze přidání. Snad nejdůležitější aplikací z toho je schopnost efektivně kontrolovat správnost souboru trvalý. Kosmeticky podobný determinantu, permanent je velmi obtížné kontrolovat správnost, ale i tento typ problému splňuje omezení. Tento výsledek dokonce vedl k průlomům interaktivní kontrolní systémy Karloff-Nisan a Shamir, včetně výsledku IP = PSPACE.

Hry s jednoduchými strategiemi

V oblasti herní teorie, konkrétněji z nespolupracující hry, Prokázal Lipton společně s E. Markakisem a A. Mehta^[6] existence epsilon-rovnováha strategie s podporou logaritmické v počtu čisté strategie. Navíc výplata těchto strategií může epsilon-aproximovat výplaty přesné Nashovy rovnováhy. Omezená (logaritmická) velikost podpory poskytuje pro výpočet přirozený kvazipolynomiální algoritmus epsilon-rovnováhy.

Odhad velikosti dotazu

Lipton a J. Naughton představili adaptivní algoritmus náhodného vzorkování pro dotazování databáze^[7][8] což je použitelné na jakýkoli dotaz, u kterého lze odpovědi na dotaz rozdělit do nesouvislých podmnožin^{[je zapotřebí objasnění ]}. Na rozdíl od většiny algoritmů pro odhad vzorkování - které staticky určují počet potřebných vzorků - jejich algoritmus rozhoduje o počtu vzorků na základě velikostí vzorků a má tendenci udržovat konstantní dobu chodu (na rozdíl od lineárního počtu vzorků).

Formální ověření programů

DeMillo, Lipton a Perlis^[9] kritizoval myšlenku formálního ověření programů a argumentoval tím

• Formální ověření v informatice nebude hrát stejnou klíčovou roli jako důkazy v matematice.
• Absence kontinuity, nevyhnutelnost změn a složitost specifikace skutečných programů způsobí, že formální ověření programů bude obtížné obhájit a spravovat.

Protokoly více stran

Chandra, Furst a Lipton^[10] zobecnil pojem komunikačních protokolů dvou stran na komunikační protokoly více stran. Navrhli model, ve kterém je kolekce procesů (${displaystyle P_ {0}, P_ {1}, ldots, P_ {k-1}}$) mít přístup k množině celých čísel (${displaystyle a_ {0}}$, ${displaystyle a_ {1}, ldots, a_ {k-1}}$) kromě jednoho z nich, takže ${displaystyle P_ {i}}$ je odepřen přístup k ${displaystyle a_ {i}}$. Tyto procesy mohou komunikovat za účelem dosažení konsensu o predikátu. Studovali komunikační složitost tohoto modelu, definovanou jako počet bitů vysílaných mezi všemi procesy. Jako příklad studovali složitost a k-party protokol přesněN (udělat vše ${displaystyle a_ {i}}$Je součet až N?) A pomocí metody obkladů získal dolní mez. Dále použili tento model ke studiu obecných větvících programů a získali časově nižší mez pro větvicí programy s konstantním prostorem, které počítají přesněN.

Časoprostorový kompromis SAT

Nemáme způsob, jak to dokázat Booleovský problém uspokojivosti (často zkráceně SAT), což je NP-kompletní, vyžaduje exponenciální (nebo alespoň superpolynomický) čas (toto je slavný Problém P versus NP ), nebo lineární (nebo alespoň super-logaritmický) prostor k řešení. V kontextu časoprostorový kompromis, lze dokázat, že SAT nelze vypočítat, pokud použijeme omezení jak v čase, tak v prostoru. L. Fortnow, Lipton, D. van Melkebeek a A. Viglas^[11] dokázal, že SAT nelze vypočítat Turingovým strojem, který trvá maximálně O (n^1.1) kroky a maximálně O (n^0.1) buňky jejích pásek pro čtení a zápis.

Ceny a vyznamenání

• Guggenheim Fellow, 1981
• Chlapík z Sdružení pro výpočetní techniku, 1997
• člen National Academy of Engineering
• Knuth Prize vítěz 2014^[12]

Viz také

• SL (složitost)
• Vezměte model ochrany
• Věta o planárním oddělovači

Poznámky

Další čtení

• "Svatby: Kathryn Farley, Richard Lipton ", The New York Times, 5. června 2016.

externí odkazy

• Jeho osobní blog „Gödelův ztracený dopis a P = NP“