Efficient algorithms and data structures are important every time huge data sets are to be processed, say, in a web search engine. Designing efficient algorithms, and analyzing them, is no easy task. This course teaches basic design methodologies of wide applicability and gives the mathematical tools that are necessary to analyze the efficiency of algorithms.
Luca Trevisan has been at Columbia since 1999. He works in theoretical computer science. He is interested in computational questions where the answer is supposed to be an "impossibility result" of a certain kind, and/or to say something interesting about infinitely many computational problems all at once. Luca has been working a lot on the complexity of finding optimal and near-optimal solutions for large-scale optimization problems. More recently, he has been studying how to simulate every possible probabilistic procedure (like the ones arising in computational finance or cryptography) by using computers that have only access to biased sources of randomness, or to no randomness at all. Believe it or not, these two research directions are connected, and some of the common ground belongs to coding theory, algebra and mathematical logic.
Laurea, University of Rome "La Sapienza" 1993, Ph.D., University of Rome "La Sapienza", 1997.