Luca Trevisan

I am from Rome, where I studied at the University "La Sapienza", advised by Pierluigi Crescenzi. Before coming to Berkeley, I was a post-doc at MIT (with theTheory of Computing Group) and at DIMACS and then an assistant professor at Columbia University.

I am interested in Theoretical Computer Science.

Office hours: Tuesdays 1-2pm and Wednesdays 2-3pm (615 Soda)
Quick links:  [PAPERS] [Lecture Notes] [CS170] [Theory Lunch] [Theory Reading Group]

research

• Papers and stuff
    [PAPERS] [SLIDES]
• Mettings seminars etc.
    [Theory Lunch]
• Program committee
    FOCS'99, CCC'00, ICALP'00, RANDOM'01, TCS'02, STOC'03, APPROX'04, CCC'05, RANDOM'05, TCC'06, LATIN'06
• Graduate Students:
  • present: Andrej Bogdanov, Kenji Obata, Hoeteck Wee
  • past: Kumar Saurabh (M.S. 2001, Columbia University), Beini Zhou (M.S.2002, U.C. Berkeley)
• Postdocs: Irit Dinur (2003-04)
• Prizes
  • [Okawa grant, '02]   [Oberwolfach prize, '00]  [Sloan Fellowship, '00]  [STOC student paper award, '97]

• Research supported by my NSFCareer award

teaching

[Lecture notes]

 

Fall 98: W4231 ,Analysis of Algorithms I	Spring 99: E6291,Topics in Cryptography
Fall 99: W4231, Analysis of Algorithms I
	Spring 01: 278,Complexity Theory
Fall 01: 170, Algorithms	Spring 02: 276,Cryptography
Fall 02: 278, Complexity Theory	Spring 03: 174,Randomized Algorithms
Fall 03: 294, Coding Theory and Complexity	Spring 04: 172, Computability and Complexity
Fall 04: 278, Complexity Theory	Spring 05: 170, Algorithms
Fall 05: 294, PCP and Inapproximability ?	Spring 06: 172, Computability and Complexity?

• A short course on PCP and Inapproximability in Cortona, Italy, July 2005. (notes will be posted)
• A short course on Error-Correcting Codes in Rome, Italy. May 2003.
• IAS Summer School on Computational Complexity, Summer 2000. [notes]
• A short course on Cryptography in Siena, Italy. January 2000.

other stuff

 

NEWS:	[NY Times] [SF Chronicle] [The Nation]
	[la Repubblica] [L'Espresso][il manifesto][Al Jazeera] [Haaretz]
MOVIES:	[Internet Movie DB] [Moviefone][Oscar][PFA][Castro theater]
CARTOONS:	[Dilbert] [Peanuts][Simpsons][Far Side]
FUN:	[The Straight Dope] [The Onion]
WORTHY CAUSES:	[EFF] [Lambda] [ACLU]
NAWAAZ	[I can't believe it's not google] [Free Fall]

• QUOTESon theory of computing, and other random quotes
• PICTURES
• Books and Movies
  

Real Battles and Empty Metaphors (Susan Sontag, NYT,9/10/02) [link]
The Faith Factor (Barbara Ehrenreich, TheNation, 11/11/04)
On 'MoralValues' It's Blue in a Landslide (Frank Rich, NYT, 11/14/04)
 

How to contact me

Snail mail

Luca Trevisan University of California at Berkeley
Computer Science Division
615 Soda Hall
Berkeley, CA 94720-1776
USA