Luca Trevisan, l'informatico che spiega perche' gli algoritmi funzionano

Uno stereotipo fin troppo diffuso vuole che gli accademici si occupino di cose che funzionano in teoria, ma non in pratica. Luca Trevisan, informatico teorico e professore ordinario al Dipartimento di Scienze delle Decisioni da settembre, cerca invece di dare un fondamento teorico a tecniche matematiche usate in informatica, che funzionano bene, senza che ne capiamo fino in fondo il perché.

Alla laurea e al dottorato in informatica a Roma, Trevisan ha fatto seguire un invidiabile, ventennale percorso accademico negli Stati Uniti tra MIT, Columbia, Berkeley e Stanford, prima di decidere di tornare in Italia. «Alla Bocconi esiste un convincente progetto di sviluppo delle materie STEM, con una visione a lungo termine e risorse consistenti, tanto da farne il luogo più attrattivo in Italia per un informatico che lavori negli Usa, e uno dei primissimi in Europa», dice.

Grazie anche al recente ottenimento di un ERC Advanced Grantper lo sviluppo di tecniche capaci di trovare una struttura in dati pieni di rumore, Trevisan potrà aggregare intorno a sé un gruppo di ricercatori capaci di studiare gli algoritmi e dimostrarne rigorosamente le loro proprietà.

Quando era postdoc al MIT, Trevisan ha dato un contributo fondamentale alla cosiddetta estrazione di casualità, ovvero alla generazione di random bits (dati statisticamente indipendenti), fondamentali nella costruzione di chiavi crittografiche. «Per raggiungere questo obiettivo», spiega, «di solito si prendono dati imprevedibili e casuali, ma non completamente indipendenti, e si crea una procedura per ripulirli ed estrarre casualità perfetta da questi oggetti. Per ottenere questa trasformazione, ho usato un algoritmo fino ad allora usato per applicazioni completamente diverse, dimostrando che quello che fa è analogo all'estrazione di casualità e che, inoltre, risulterebbe efficace anche utilizzando un computer quantistico per il calcolo». La parola chiave è «dimostrando», perché altri metodi funzionano, ma non se ne è mai dimostrata l'efficacia.

Anni dopo, nel periodo passato a Stanford, Trevisan ha affrontato il tema dell'analisi delle reti attraverso l'algebra lineare. In un lavoro molto importante ha dimostrato la validità dei metodi basati sull'algebra lineare nell'individuazione di sottoinsiemi di nodi con connessioni particolarmente dense (frequenti). «Questi algoritmi consentono di individuare questi sottoinsiemi dalla semplice osservazione della rete. Ed è importante farlo, perché la densità di connessioni è causata, con ogni probabilità, da una comunanza di interessi, da qualche affinità».

Un altro filone di ricerca di Trevisan riguarda i problemi per i quali non esistono algoritmi che assicurino una soluzione o la assicurino in tempi ragionevoli. «Questa è una caratteristica positiva se applicata alla crittografia», dice Trevisan, «ma negativa se vogliamo risolvere il problema. Sapere che non esiste soluzione può allora aiutarci ad aggirare in qualche modo il problema, magari cercando algoritmi che approssimino la soluzione, senza darne una esatta». Trevisan ha dato un contributo importante allo sviluppo di tecniche capaci di dimostrare l'inesistenza persino di algoritmi capaci di approssimare una soluzione.

Nel 2012 Trevisan ha deciso di celebrare in modo originale, nel suo blog in theory, il centenario della nascita di Alan Turing, geniale precursore dell'informatica, della crittografia e dell'intelligenza artificiale e gay dichiarato in un'epoca in cui, per farlo, serviva un coraggio al limite dell'incoscienza, tanto che la sua storia si concluse con un arresto e il suicidio. Con le parole di Trevisan: «Nell'ambito delle celebrazioni di Turing, penso che sarebbe interessante parlare di come le cose sono cambiate (o meno) dai tempi di Turing per le persone che svolgono un lavoro accademico nella crittografia e nella teoria dell'informatica e che sono gay o lesbiche. Così ho invitato un certo numero di colleghi gay e lesbiche a scrivere dei post per parlare di come le cose sono state per loro. I loro post appariranno il mese prossimo che, oltre ad essere il mese del centenario di Turing, è anche l'anniversario delle rivolte di Stonewall». La serie del Turing centennialè disponibile cliccando qui.


Per saperne di più

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