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

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

NEI SUOI LAVORI, TREVISAN DA' FONDAMENTO TEORICO A TECNICHE MATEMATICHE CHE FUNZIONANO BENE, SENZA CHE NE CAPIAMO FINO IN FONDO IL PERCHE'. NEL 2012 HA FESTEGGIATO IN MODO ORIGINALE IL CENTENARIO DI ALAN TURING

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

di Fabio Todesco

News

Tutte le News
  • I rapporti tra generazioni trasformati in un rischio

    L'Europa del Sud registra il piu' alto tasso al mondo di contatti tra over 60 e giovani in eta' scolare e cosi' un forte potenziale di contagio per una malattia sensibile all'eta' come il COVID19  

  • Perche' rispettiamo, o no, le regole di distanziamento sociale

    Pamela Giustinelli e una collega dell'UCL vogliono capire come la gente comune in Italia, Regno Unito e Stati Uniti percepisca i costi e i benefici del lockdown da COVID19  

Seminari

  Aprile 2020  
Lun Mar Mer Gio Ven Sab Dom
    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      

Seminari      

Tutti i Seminari
  • Which scientific results can we trust? Evidence from replications and prediction markets
    Development Labor Political Economy - DLPE

    Anna Dreber (Stockholm School of Economics)

    Webinar

  • SEMINARIO ANNULLATO: Errore giudiziale e sistema di impugnazione
    Ciclo di seminari di Filosofia del diritto

    ATTN: IL SEMINARIO E' STATO ANNULLATO   Flavia Carbonell, Universidad de Chile

    Sala riunioni 1.C4-SR01, primo piano, Via Roentgen 1