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 Trevisan, Extractors and pseudorandom generators, J. ACM 48(4): 860-879 (2001).

James R. Lee, Shayan Oveis Gharan, Luca Trevisan, Multiway Spectral Partitioning and Higher-Order Cheeger Inequalities,J. ACM 61(6): 37:1-37:30 (2014).

Luca Trevisan, Gowers Uniformity, Influence of Variables, and PCPs, SIAM J. Comput. 39(1): 323-360 (2009).