Luca Trevisan
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.
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
Counting distinct elements in a data stream
Randomization and approximation techniques in computer science, 2002Almost optimal local graph clustering using evolving sets
JOURNAL OF THE ASSOCIATION FOR COMPUTING MACHINERY, 2016Find your place: simple distributed algorithms for community detection
SIAM JOURNAL ON COMPUTING, 2020When hamming meets euclid: the approximability of geometric TSP and Steiner tree
SIAM JOURNAL ON COMPUTING, 2000From gap-exponential time hypothesis to fixed parameter tractable inapproximability: Clique, dominating set, and more
SIAM JOURNAL ON COMPUTING, 2020Multiway spectral partitioning and higher-order cheeger inequalities
JOURNAL OF THE ASSOCIATION FOR COMPUTING MACHINERY, 2014Lower bounds for max-cut in h-free graphs via semidefinite programming
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2021Simple 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, 2014Information spreading in dynamic graphs
PODC'12 : proceedings of the 2012 ACM Symposium on Principles of Distributed Computing; July 16-18, 2012, Madeira, Portugal, 2012An Alon-Boppana type bound for weighted graphs and lowerbounds for spectral sparsification
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018Improved 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, 2013Dense subsets of pseudorandom sets
49th Annual IEEE Symposium on Foundations of Computer Science, 2008 FOCS '08 ; 25 - 28 Oct. 2008, Philadelphia, Pennsylvania, USA, 2008Find your place: simple distributed algorithms for community detection
SODA '17: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017New notions and constructions of sparsification for graphs and hypergraphs
2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS 2019), 2019Consensus vs broadcast, with and without noise (Extended Abstract)
11th Innovations in Theoretical Computer Science Conference (ITCS 2020), 2020An 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, 2017Teaching