Luca Trevisan, the Computer Scientist Who Explains How Algorithms Work

Luca Trevisan, the Computer Scientist Who Explains How Algorithms Work


A widespread stereotype depicts academics dealing with things that work in theory, but not in practice. Luca Trevisan, a computer scientist and a Full Professor at the Department of Decision Sciences since September 2019, tries instead to give a theoretical foundation to mathematical techniques used in computer science, which work well, but which we do not fully understand why.
After his degree and doctorate in computer science in Rome, Prof. Trevisan has had an enviable, twenty-year academic career in the United States between MIT, Columbia, Berkeley and Stanford, before deciding to return to Italy. «At Bocconi, there is a convincing STEM development project with a long-term vision and substantial resources, making it the most attractive place in Italy for a computer scientist working in the US, and one of the very first in Europe», he says.
Thanks also to a recent ERC Advanced Grant, awarded to him to develop techniques capable of finding a structure in noisy data, Prof. Trevisan will gather around him a group of researchers to study algorithms and to rigorously demonstrate their properties.
When he was a postdoc researcher at MIT, Luca Trevisan gave a fundamental contribution to the so-called randomness extraction, that is the generation of random bits (statistically independent data), fundamental in the construction of cryptographic keys. «To achieve this goal», he explains, «we usually take unpredictable, random data, but not completely independent, and create a procedure to clean up and extract perfect randomness from these objects. To achieve this transformation, I used an algorithm used until then in completely different applications, demonstrating that what it does is similar to randomness extraction and that it would also be effective using a quantum computer for calculation». The key word is «demonstrating», because other methods work, but they have never been demonstrated to be effective.
Years later, during his time at Stanford, Prof. Trevisan addressed the issue of network analysis through linear algebra. In a very important work, he demonstrated the validity of methods based on linear algebra in the detection of subsets of nodes with particularly dense (frequent) connections. «These algorithms allow to identify these subsets by simply observing the network. And it is an important thing to detect, because connections density is caused, in all probability, by a commonality of interests, by some affinity».
Another strand of Trevisan's research looks at the problems for which there are no algorithms that provide a solution, or not within a reasonable time. «This is a positive feature when applied to cryptography», says Prof. Trevisan, «but negative if we want to solve the problem. Knowing that there is no solution can, then, help us get around the problem somehow, perhaps by looking for algorithms that approximate the solution, without giving an exact one». Prof. Trevisan has made an important contribution to the development of techniques capable of demonstrating the non-existence even of algorithms capable of approximating a solution.
In 2012, Luca Trevisan decided to celebrate in an original way, in his blog in theory, the centennial of the birth of Alan Turing, a brilliant forerunner of computer science, cryptography and artificial intelligence and an openly gay man in a time when it took courage on the edge of recklessness, so much so that his story ended with his arrest and suicide. In the words of Prof. Trevisan: «Within the Turing festivities, I think it would be interesting to talk about how things have changed (or not) since Turing’s time for people who do academic work in cryptography and in the theory of computing and who are gay or lesbian. So, I have invited a number of gay and lesbian colleagues to write guest posts talking about how things have been for them, and, so far, half a dozen have tentatively accepted. Their posts will appear next month which, besides being Turing’s centennial month, also happens to be the anniversary of theStonewall riots». The Turing centennialseries is available by clicking here.
Find out more
Luca TrevisanExtractors and pseudorandom generators,  J. ACM 48(4): 860-879 (2001).
James R. LeeShayan Oveis GharanLuca TrevisanMultiway Spectral Partitioning and Higher-Order Cheeger Inequalities,J. ACM 61(6): 37:1-37:30 (2014).
Luca TrevisanGowers Uniformity, Influence of Variables, and PCPs, SIAM J. Comput. 39(1): 323-360 (2009).

by Fabio Todesco


All News
  • COVID: The Multifaceted Truth in the Case of Lombardy

    A strand of research by Alessia Melegaro aims to reconstruct the early stages of the epidemic and the reasons why it hit the region so hard  

  • Quantum Physics and Statistical Physics for Machine Learning Meet at Bocconi

    In the early days of next week the University will virtually host 300 participants of the ELLIS Workshop on Quantum and Physics Based Machine Learning  


  July 2020  
Mon Tue Wed Thu Fri Sat Sun
    1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31    


All Seminars
  • Il regolamento europeo sui prospetti informativi
    Business law

    Welcome Address Piergaetano Marchetti, Università Bocconi   Coordinator Giovanni Strampelli, Università Bocconi   Introduction Guido Ferrarini, Università di Genova   Speakers Danny Busch, Radboud University, Nijmegen;   Antonella Sciarrone Alibrandi, Università Cattolica del Sacro Cuore, Milano;   Paolo Giudici, Libera Università di Bolzano;   Michele Siri, Università di Genova   Conclusions Marco Ventoruzzo, Università Bocconi


  • Oh, What an UnTangled Web We Weave: The Abnormal Structure of Illegal Digital Marketplace Communities

    JOHN HULLAND, University of Georgia