LUCA TREVISAN
Courses a.y. 2022/2023
Courses previous a.y.
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.
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
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
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
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
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
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
When hamming meets euclid: the approximability of geometric TSP and Steiner tree
SIAM JOURNAL ON COMPUTING, 2000
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
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
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
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
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
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
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
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
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
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
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
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
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
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