LUCA TREVISAN

LUCA TREVISAN

Biographical note

I am a professor of computer science at Bocconi University. I received my Dottorato (PhD) in 1997, from the Sapienza University of Rome, working with Pierluigi Crescenzi. After graduating, I was a post-doc at MIT and at DIMACS, and was on the faculty of Columbia University, U.C. Berkeley, and Stanford, before returning to Berkeley in 2014 and, eventually, returning to Italy in 2019.

In 2023 I became Director of the Bocconi Master of Sciences in Artificial Intelligence.


Research interests

My 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.


Selected Publications

Bar-Yossef, Ziv; Jayram, T. S.; Kumar, Ravi; Sivakumar, D.; Trevisan, Luca
Counting distinct elements in a data stream
Randomization and approximation techniques in computer science, 2002

Andersen, Reid; Gharan, Shayan Oveis.; Peres, Yuval; Trevisan, Luca
Almost optimal local graph clustering using evolving sets
JOURNAL OF THE ASSOCIATION FOR COMPUTING MACHINERY, 2016

Samorodnitsky, Alex; Trevisan, Luca
Gowers uniformity, influence of variables, and PCPs
SIAM JOURNAL ON COMPUTING, 2009

Becchetti, Luca; Clementi, Andrea; Natale, Emanuele; Pasquale, Francesco; Silvestri, Riccardo; Trevisan, Luca
Simple dynamics for plurality consensus
DISTRIBUTED COMPUTING, 2017

Becchetti, Luca; Clementi, Andrea E.; Natale, Emanuele; Pasquale, Francesco; Trevisan, Luca
Find your place: simple distributed algorithms for community detection
SIAM JOURNAL ON COMPUTING, 2020

Trevisan, Luca
When hamming meets euclid: the approximability of geometric TSP and Steiner tree
SIAM JOURNAL ON COMPUTING, 2000

Trevisan, Luca
Max Cut and the smallest eigenvalue
SIAM JOURNAL ON COMPUTING, 2012

Chalermsook, Parinya; Cygan, Marek; Kortsarz, Guy; Laekhanukit, Bundit; Manurangsi, Pasin; Nanongkai, Danupon; Trevisan, Luca
From gap-exponential time hypothesis to fixed parameter tractable inapproximability: Clique, dominating set, and more
SIAM JOURNAL ON COMPUTING, 2020

Lee, James R.; Gharan, Shayan Oveis; Trevisan, Luca
Multiway spectral partitioning and higher-order cheeger inequalities
JOURNAL OF THE ASSOCIATION FOR COMPUTING MACHINERY, 2014

Trevisan, Luca
Extractors and pseudorandom generators
JOURNAL OF THE ASSOCIATION FOR COMPUTING MACHINERY, 2001

Charles Carlson; Alexandra Kolla; Ray Li; Nitya Mani; Benny Sudakov; Luca Trevisan
Lower bounds for max-cut in h-free graphs via semidefinite programming
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2021

Becchetti, Luca; Pasquale, Francesco; Clementi, Andrea; Silvestri, Riccardo; Natale, Emanuele; Trevisan, Luca
Simple dynamics for plurality consensus
SPAA '14 : proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures : June 23-25, 2014, Prague, Czech Republic, 2014

Clementi, Andrea; Silvestri, Riccardo; Trevisan, Luca
Information spreading in dynamic graphs
PODC'12 : proceedings of the 2012 ACM Symposium on Principles of Distributed Computing; July 16-18, 2012, Madeira, Portugal, 2012

Srivastava, Nikhil; Trevisan, Luca
An Alon-Boppana type bound for weighted graphs and lowerbounds for spectral sparsification
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Kwok, Tsz Chiu; Lau, Lap Chi; Lee, Yin Tat; Gharan, Shayan Oveis; Trevisan, Luca
Improved Cheeger's inequality: analysis of spectral partitioning algorithms through higher order spectral gap
STOC'13 proceedings of the 2013 ACM International Symposium on Theory of Computing : June 1 - 4, 2013, Palo Alto, California, USA, 2013

Reingold, Omer; Trevisan, Luca; Tulsiani, Madhur; Vadhan, Salil
Dense subsets of pseudorandom sets
49th Annual IEEE Symposium on Foundations of Computer Science, 2008 FOCS '08 ; 25 - 28 Oct. 2008, Philadelphia, Pennsylvania, USA, 2008

Becchetti, Luca; Clementi, Andrea; Natale, Emanuele; Pasquale, Francesco; Trevisan, Luca
Find your place: simple distributed algorithms for community detection
SODA '17: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Bansal, Nikhil; Svensson, Ola; Trevisan, Luca
New notions and constructions of sparsification for graphs and hypergraphs
2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS 2019), 2019

Clementi, Andrea; GualĂ , Luciano; Natale, Emanuele; Pasquale, Francesco; Scornavacca, Giacomo; Trevisan, Luca
Consensus vs broadcast, with and without noise (Extended Abstract)
11th Innovations in Theoretical Computer Science Conference (ITCS 2020), 2020

Borassi, Michele; Crescenzi, Pierluigi; Trevisan, Luca
An axiomatic and an average-case analysis of algorithms and heuristics for metric properties of graphs
SODA '17: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017