Luca Trevisan

Short Bio

Luca Trevisan is a Professor of Computer Science at Bocconi University, where he holds the Invernizzi Foundation Chair in Computer Science. He is the founding director of Bocconi's new M.Sc. in Artificial Intelligence that opened in Fall 2023.

Luca received his Dottorato (PhD) in 1997, from the Sapienza University of Rome, working with Pierluigi Crescenzi. After graduating, Luca was a post-doc at MIT and at DIMACS, and he was on the faculty of Columbia University, U.C. Berkeley, and Stanford, before returning to Berkeley in 2014 and, at long last, returning to Italy in 2019.

Luca's research is in theoretical computer science, with a focus on computational complexity, on the analysis of algorithms, on the foundations of cryptography, and on topics at the intersection of theoretical computer science and pure mathematics.

Luca is a Fellow of the ACM and a member of the Accademia Nazionale delle Scienze Detta dei XL, the Italian National Academy of Science. He received the 2000 Oberwolfach Prize, the 2000 Sloan Fellowship and an NSF CAREER Award. He was an invited speaker at the 2006 International Congress of Mathematicians. In 2019, he received an ERC Advanced Grant. He is currently serving a five-year term on the committee that assigns the Turing Award.

Some selected papers

James R. Lee, Shayan Oveis Gharan, and Luca Trevisan
Multi-way spectral partitioning and higher-order Cheeger inequalities
J. of the ACM 61(6): 37:1-37:30 (2014)
arXiv:1111.1055

Alex Samorodnitsky and Luca Trevisan.
Gowers Uniformity, Influence of Variables, and PCPs
Siam J. on Computing 39(1): 323-360, 2009
[Preprint]

Luca Trevisan
Extractors and Pseudorandom Generators
J. of the ACM 48(4):860-879, 2001
[Preprint]

Some recent papers

Luca Becchetti, Andrea Clementi, Francesco Pasquale, Luca Trevisan, Robin Vacus, and Isabella Ziccardi
The Minority Dynamics and the Power of Syn chronicity
In Proc. of SODA 2024, 4155-4176, arXiv:2310.13558
Jun-Ting Hsieh, Pravesh K. Kothari, Lucas Pesenti, and Luca Trevisan
New SDP Roundings and Certifiable Approximation for Cubic Optimization
In Proc. of SODA 2024, arXiv:2310.00393

Luca Becchetti, Andrea Clementi, Amos Korman, Francesco Pasquale, Luca Trevisan, Robin Vacus.
On the Role of Memory in Robust Opinion Dynamics
In Proc. of IJCAI 2023, arXiv:2302.08600

Tommaso D'Orsi and Luca Trevisan
A Ihara-Bass Formula for Non-Boolean Matrices and Strong Refutations of Random CSPs
In Proc. of CCC 2023, pages 27:1-27:16, arXiv:2204.10881

Flavio Chierichetti, Alessandro Panconesi, Giuseppe Re, and Luca Trevisan
Spectral Robustness for Correlation Clustering Reconstruction in Semi-Adversarial Models
In Proc. of AISTATS 2022, pages 10852-10880, arXiv:2108.04729

Luca Becchetti, Andrea Clementi, Riccardo Denni, Francesco Pasquale, Luca Trevisan, and Isabella Ziccardi
Percolation and Epidemic Processes in One-Dimensional Small-World Networks
In Proc. of LATIN 2022, arXiv:2103.16398

Antares Chen, Jonathan Shi and Luca Trevisan
Cut Sparsification of the Clique Beyond the Ramanujan Bound
In Proc. of SODA 2022, arXiv:2008.05648

Luca Becchetti, Andrea Clementi, Francesco Pasquale, Luca Trevisan and Isabella Ziccardi
Expansion and Flooding in Dynamic Random Networks with Node Churn
In Proc. of ICDCS 2021, arXiv:2007.14681

Sam Hopkins, Tselil Schramm and Luca Trevisan
Subexponential LPs Approximate Max Cut
In Proc. of FOCS 2020, arXiv:1911.10304

Advising

Current

Postdocs:

Students:

Past

Postdocs:

Ali Sinop
Or Meir
Irit Dinur
Fabrizio Pittorino
Jonathan Shi

Students:

Frank Ban (PhD 2019) now at Google
Pasin Manurangsi (PhD 2019) now at Google
Siu On Chan (PhD 2013) now at CUHK
Siu Man Chan (PhD 2013) now research engineer in the private sector
Anindya De (PhD 2013) now at U. Penn
Thomas Watson (PhD 2013) now at U. of Memphis
Omid Etesami (PhD 2010), now at IPM
Grant Schoenebeck (PhD 2010), now at U. of Michigan
Madhur Tulsiani (PhD. 2009), now at TTI Chicago
Hoeteck Wee (PhD. 2007), now at Ecole National Superior, Paris
Kenji Obata (PhD. 2006), now CEO of turbo.net
Andrej Bogdanov (Ph.D. 2005), now at CUHK

Other activities

I write at in theory about theoretical computer science and other things that interest me.

I am associate editor of SIAM J. on Computing and ACM Transactions on Computation Theory

I am a member of IPAM's science advisory board

I am a member of the Turing Award Commmittee

In 2022-2023, I

coorganized a Theory Day at Bocconi on January 26, 2023

served on the external evaluation committee of the Computer Sciences department at ETH Zurich

served on the PE6 review panel for the 2023 ERC Advanced Grants

In 2021-2022, I

have been on the program committee of STOC 2022
have chaired the committee for the FOCS 2021 test of time award
have chaired the organizing committee for a workshop on average-case complexity in statistical problems at the Simons Institute in Berkeley
co-organized a theory day on Dec 13, 2021 at Bocconi
organized a workshop on spectral and convex optimization techniques in graph algorithms, held in Milan on June 15-18, 2022
organized a workshop on fairness in artificial intelligence, held in Milan on June 27, 2022

Luca Trevisan

Professor of Computer Science

Teaching

Past Teaching

Lecture Notes

Research

All Papers