| CARVIEW |
Luca Trevisan
Professor of Computer Science
Department of Computing Sciences
Bocconi University
Via Roentgen 1
20136 Milano
Italy
L.Trevisan at UniBocconi dot It
Research
I am interested in computational complexity theory, algorithms, and topics at the intersection of theoretical computer science and pure mathematicsMy research is supported by an ERC grant on Spectral and Optimization Techniques for Robust Recovery, Combinatorial Constructions, and Distributed Algorithms
All Papers
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:
- Caicai Chen
- Lucas Pesenti
- Jiyu Zhang
Past
Postdocs:- Ali Sinop
- Or Meir
- Irit Dinur
- Fabrizio Pittorino
- Jonathan Shi
- 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