< back Computer Science & Engineering russell@cs.ucsd.edu Phone 858-534-1332 Website < back |
Russell Impagliazzo Computational complexity, cryptography, circuit complexity, computational randomness. Professor Impagliazzo is a mathematician who focuses on the foundations of cryptography, or using "hard problems" for security applications. Hard problems require a prohibitive amount of time or resources to solve. Complexity theory, the mathematical domain in which Impagliazzo works, aims at establishing how hard a problem really is. A grade school student would obtain 10 percent of 100 by multiplying 0.10 by 100 the long way, making 15 separate calculations. But moving the decimal point two places, gains the same result in just one operation, establishing the job’s actual complexity, or its lower bounds. One hard problem common to cryptographic systems is factoring large numbers. It is easy for a computer to obtain a 1,000 digit number by multiplying two 500 digit prime factors. But backing out the initial two inputs from the third factor is so hard that it would probably take a billion of today’s fastest computers the rest of time. This function achieves computational randomness because it is impossible for a hacker to decipher how the computer picked the input factors. Impagliazzo is now seeking methods to safely use less randomness in cryptography and in algorithms. Impagliazzo's work is largely theoretical, but has obvious application to Internet security. He is turning his attention now to encryption in “smart” cards and technologies to guarantee privacy to consumers. Biography Russell Impagliazzo joined the UCSD in faculty in 1989 after receiving his Ph.D. in mathematics from UC Berkeley. In 2003, he received two awards for contributions to the theory of pseudo-randomness and cryptography: an Outstanding Paper Award from the Society of Industrial and Applied Mathematicians; and the Best Paper Award at STOC, the top theory-of-computing conference. In April 2004 he was appointed a Guggenheim Fellow and cited for his work on "heuristics, proof complexity, and algorithmic techniques." |
