ColloquiaChris Umans, Microsoft Research - Friday, April 5

[Margery Ishmael]

Friday, April 5, 2002
2:30 pm - Ryerson 251
Chris Umans, Microsoft Research

Title: "Derandomization: Constructions and Applications"

Host: Prof. Janos Simon

Abstract:
Randomness is pervasive in modern algorithm design, cryptography, and 
large-scale simulation in the natural sciences. Reconciling the design of 
randomized procedures with their implementation on inherently deterministic 
machines is of fundamental importance, as we increasingly rely on the 
integrity of the implementations for safety, security, privacy, and the 
accuracy of computational science. Derandomization theory addresses this issue.

In this talk I'll describe two objects designed to provide a sound basis 
for implementing randomized procedures: extractors and pseudo-random 
generators. I'll present new, simple algebraic constructions of these 
objects. The pseudo-random generator construction is the first to produce 
an optimal tradeoff between computational hardness and pseudo-randomness, 
and the extractor construction significantly simplifies many previous 
papers while matching the parameters of the best-known constructions.

I'll also highlight one of the many applications of extractors outside of 
derandomization, answering an important question in logic synthesis 
regarding the approximability of DNF formula minimization. Finally, I'll 
discuss some other potential applications and various open questions. 
(Portions of this talk are joint work with Ronen Shaltiel.)

Bio: I am a postdoc in the Theory Group at Microsoft Research. My research 
interests are in theoretical computer science, especially complexity 
theory.  Specifically, I am interested in derandomization, explicit 
constructions, hardness of approximation, algorithms, and graph theory. I 
received my Ph.D. in Computer Science from Berkeley in 
2000.  http://www.research.microsoft.com/~umans/

Host: Janos Simon

*The talk will be followed by refreshments in Ryerson 255*
Persons with disabilities who may need assistance should call 773.834.8977

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Margery Ishmael
Secretary to the Chairman, Department of Computer Science
The University of Chicago
1100 E. 58th Street, Chicago, IL. 60637-1581
tel. 773.834.8977  fax. 773.702.8487
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=