Russell Impagliazzo - Russell Impagliazzo

Tento článek obsahuje seznam obecných Reference, ale zůstává z velké části neověřený, protože postrádá dostatečné odpovídající vložené citace. Prosím pomozte zlepšit tento článek představuji přesnější citace. (Květen 2009) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Russell Impagliazzo
Russell Impagliazzo na semináři DIMACS o kryptografii, červenec 2016.

Russell Impagliazzo je profesorem počítačových věd na University of California, San Diego specializující se v výpočetní složitost teorie. Získal doktorát z University of California, Berkeley. Jeho poradce byl Manuel Blum. On je 2004 Guggenheimův kolega.

Impagliazzoovy příspěvky k teorii složitosti zahrnují: Konstrukce a generátor pseudonáhodných čísel od kteréhokoli jednosměrná funkce, jeho důkaz Yaoovo XOR lemma prostřednictvím „setů tvrdého jádra“ vede jeho práce k prolomení složitosti výrokových důkazů, jako je dolní hranice exponenciální velikosti pro konstantní hloubku Hilbert důkazy princip pigeonhole a zavedení systému polynomiálního počtu, jeho práce na souvislostech mezi výpočetní tvrdostí a de-randomizací a nedávné^{[Citace je zapotřebí ]} průlomové práce na konstrukci vícezdrojových bezsemenných extraktorů.

Impagliazzo přispěl do více než 40 příspěvků na témata v rámci svých specializací. Rovněž uvedl exponenciální časová hypotéza že 3-SAT nelze vyřešit v subexponenciálním čase v počtu proměnných. Tato hypotéza se používá k odvození mnoha dolních mezí algoritmy v počítačová věda.

Jeho "pět světů" jsou dobře známé v teorie výpočetní složitosti.

Reference

externí odkazy

• Russell Impagliazzo
• UCSD Jacobs, profil fakulty School of Engineering

Tento životopisný článek týkající se počítačového specialisty je pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to.