La comunità dell’informatica teorica è rimasta affranta dalla prematura scomparsa di Luca Trevisan, avvenuta il 19 giugno 2024 a Milano all’età di 52 anni. Suo marito, Junce Zhang, era al suo fianco insieme ad altri cari amici e colleghi. Luca lascia un’eredità ricca e diversificata di risultati influenti e un profondo impatto sulla nostra comunità.

Traiettoria di vita e di carriera
Figlio unico, Luca è nato e cresciuto a Roma, dove da adolescente ha trascorso molti lunghi pomeriggi a leggere libri di matematica. Amava andare in bicicletta a Villa Ada o lungo il Tevere, ed era appassionato di cinema, in particolare di Frankenstein Junior di Mel Brooks e dei film dei Monty Python e di Woody Allen. A scuola Luca prendeva i voti più alti, ma era particolarmente precoce in matematica. L’amico di sempre di Luca, Flavio Marchetti, racconta: “Ho parlato spesso di Luca con la nostra professoressa di matematica del liceo, Daniela Crosti… e scherziamo sulle interrogazioni di Luca, che spesso si trasformavano in dimostrazioni estemporanee originali in cui arrivava alle risposte ragionando insieme alla classe, senza alcuna preparazione preventiva”.

Quando era studente alla Sapienza di Roma, divenne il primo studente a laurearsi presso il dipartimento di Scienze dell’Informazione. Un articolo sull’evento pubblicato dal quotidiano romano Il messaggero nel 1993 [31] fa luce sulla personalità giovanile di Luca. La madre di Luca, Giuseppina, lo descriveva come calmo, disorganizzato e poco adatto a gestire le questioni pratiche. Gli amici dicevano che guidava come un pazzo ed era un pericolo per la sicurezza pubblica, ma aveva un grande senso dell’umorismo.

Nel suo terzo anno di università, seguì un corso sulla complessità computazionale tenuto da Daniel Pierre Bovet. Quell’anno, l’annuncio della svolta di Feige-Goldwasser-Lovász-Safra-Szegedy (FGLSS) su “hardness of approximation” [17] catturò l’immaginazione di Luca, che iniziò a fare ricerca sull’argomento con Pierluigi Crescenzi, proseguendo fino a conseguire il dottorato alla Sapienza nel 1997. «Luca era il dottorando perfetto», ricorda Pierluigi. «Chiaramente era eccezionalmente intelligente. Ma era anche sempre così gentile e premuroso che spiegava pazientemente e chiaramente le sue idee, facendoti sentire a tuo agio e mai in imbarazzo se non riuscivi a comprenderle immediatamente.»

Durante il suo dottorato, Luca svolse uno stage con Madhu Sudan presso IBM Research, che ospitò Luca anche per un postdoc al MIT, dove ottenne il suo risultato fondamentale sugli estrattori di casualità (randomness extractors) [41]. Del primo incontro con Luca, Madhu ricorda: «Fu uno degli incontri iniziali più sorprendenti. In quindici minuti, mentre guidavo per le affollate strade di Manhattan, Luca mi spiegò elementi del mio stesso articolo (con Bellare e Goldreich) e mi mostrò perché un’idea contenuta nell’articolo portasse a risolvere quello che pensavamo fosse un problema completamente diverso, proveniente da un’altra parte dello stesso articolo. Questo portò infine al primo articolo di Luca presentato a FOCS(/STOC), scritto insieme a me, Sorkin e Williamson, contribuendo a lanciare una carriera prestigiosa. È stato un privilegio incontrare Luca così presto!».

Successivamente, Luca svolse un secondo postdoc al DIMACS prima di entrare nel corpo docente della Columbia University. In seguito, insegnò a Berkeley e Stanford prima di ritornare a Berkeley nel 2014 come Senior Scientist presso il Simons Institute for the Theory of Computing. «Non c’è dubbio che Luca abbia significativamente elevato il clima intellettuale del gruppo teorico a Berkeley», osserva Alistair Sinclair, direttore associato fondatore del Simons Institute, «e lo abbia fatto con grande umiltà e un senso dell’umorismo disarmante. La sua capacità di distillare l’essenza di una vastissima gamma di idee matematiche e di condividere generosamente le sue intuizioni con gli altri, attraverso il suo blog e altrove, era un dono davvero raro. Riportarlo da Stanford a Berkeley come Senior Scientist al Simons fu un grande colpo. I suoi consigli e le sue parole sagge furono preziosissimi durante le interminabili discussioni e decisioni che affrontammo nei primi anni dell’Istituto».

Nel 2019, Luca tornò con orgoglio in Italia per contribuire al lancio del nuovo Dipartimento di Scienze Computazionali all’Università Bocconi di Milano. Il suo fascino intellettuale e personale fu determinante per attrarre in Italia scienziati di livello mondiale, dando impulso a un periodo di notevole e inaspettata crescita per il dipartimento. Alla Bocconi, Luca ricoprì la Cattedra in Informatica della Fondazione Invernizzi e co-fondò e diresse il Master biennale in Intelligenza Artificiale, inaugurato nell’autunno del 2023 e attualmente in significativa espansione. Poco dopo il suo rientro, Luca ricevette il prestigioso Advanced Grant del Consiglio Europeo della Ricerca e nel 2021 diventò il primo informatico a essere eletto nell’Accademia Nazionale delle Scienze italiana. Il dipartimento della Bocconi continua a prosperare sull’impulso da lui creato e rimane determinato a realizzare l’eredità visionaria che Luca ha condiviso nei suoi ultimi giorni.

Figure 1: Luca al workshop dell’Università Bocconi, 22 May 2024

Contributi alla ricerca
Durante la sua carriera, Luca ha fornito splendidi contributi alla teoria della computazione, spaziando tra pseudocasualità, ottimizzazione approssimata e sistemi probabilisticamente verificabili (PCP), computazione distribuita, test di proprietà, crittografia e algoritmi spettrali. Di seguito riportiamo solo alcuni di questi risultati.

Approssimabilità e sistemi PCP. La ricerca di dottorato di Luca, a metà degli anni ’90, si concentrò sull’approssimabilità e produsse due risultati molto eleganti sulla non-approssimabilità: uno che dimostrava che la dipendenza doppiamente esponenziale dalla dimensione negli schemi di approssimazione per il problema TSP (traveling salesman problem) euclideo era intrinseca [40], risultato per il quale ricevette il premio per il miglior articolo studentesco alla conferenza STOC 1997, e un altro che forniva un framework sistematico basato sulla programmazione lineare per scoprire cosiddetti gadget di riduzioni preservanti i gap e argomentare la loro ottimalità [49]. Al momento del dottorato, Luca era ormai diventato un esperto del campo, in rapida evoluzione, dei sistemi PCP. Attribuiva all’esposizione approfondita di Bellare, Goldreich e Sudan [11] il suo punto di partenza. Tra i vari contributi di Luca, vi è una linea di lavoro culminata nei PCP con il miglior rapporto qualità-costo rispetto alle interrogazioni effettuate, ottenendo asintoticamente un guadagno quasi doppio in robustezza per ogni bit aggiuntivo interrogato [36, 34, 35]. L’ultimo articolo di questa serie [35] introdusse strumenti della matematica combinatoria additiva, come le norme di Gowers [21, 22], nell’ambito della teoria della computazione. Luca aveva una vera abilità nell’individuare direzioni nella matematica pura che avessero fruttuose connessioni con la teoria della complessità computazionale (e viceversa). Analogamente, in [32, 50] scoprì profonde connessioni tra il Teorema del Modello Denso, che svolge un ruolo centrale nel Teorema di Green-Tao [23] sulle progressioni aritmetiche arbitrariamente lunghe nei numeri primi, e concetti fondamentali nella complessità media e pseudocasualità, come il Lemma “Hardcore” di Impagliazzo [25].

Pseudocasualità. Luca diede numerosi importanti contributi alla teoria della pseudocasualità, inclusi il citato Teorema del Modello Denso e risultati correlati. Tra questi spicca l’incredibile scoperta di Luca [41], come postdoc, che la costruzione di generatori pseudocasuali da parte di Impagliazzo-Wigderson da funzioni (ipotizzate) ad alta complessità circuitale [26] costituisce anche una costruzione (incondizionata) di estrattori di casualità. (Vedi Figura 2.) Luca dimostrò così che due principali linee di ricerca sulla casualità nella computazione stavano in realtà studiando lo stesso problema sotto mentite spoglie. Il collegamento stabilito da Luca fu altamente non ovvio e creativo, sorprese persino i leader del settore che avevano lavorato su entrambe le linee di ricerca. Questo risultato inaspettato fornì a molti giovani ricercatori di tutto il mondo un’opportunità ideale per entrare in un’area prima considerate ben consolidata e intimidatoria.

Figura 2: Il metodo di Luca per trasformare una costruzione di un generatore pseudocasuale (PRG) in un estrattore di casualità [41]. Se invece di eseguire la costruzione con una funzione fissa di elevata complessità circuitale (come era sempre stato immaginato), la alimentiamo con una funzione casuale estratta da una distribuzione con sufficiente min-entropia, risulta che l’output non sarà soltanto computazionalmente indistinguibile dall’uniforme, ma anche statisticamente vicino all’uniforme.

Teoria spettrale dei grafi. Nella seconda parte della sua carriera, il percorso di ricerca nel campo degli algoritmi di approssimazione lo condusse a lavorare sulla teoria algoritmica spettrale dei grafi. Le sue diverse estensioni della disuguaglianza di Cheeger, che mettono in relazione il più piccolo autovalore del laplaciano di un grafo con componenti quasi bipartite [43], e l’autovalore k-esimo con partizioni a k-vie dei grafi [28], sono già diventate parte integrante del canone centrale di quest’area di ricerca e hanno avuto sorprendenti conseguenze anche in matematica pura [29, 30]. Leggendo le loro eleganti dimostrazioni, emerge un senso di inevitabilità che le rende difficili da dimenticare.

Algoritmi distribuiti. A partire dal 2012, Luca fu attratto dal mondo della computazione distribuita e, in particolare, dal comportamento auto-organizzativo generato da semplici processi completamente decentralizzati noti come dinamiche [7]. Come elemento di un affiatato gruppo di collaboratori romani (alcuni mostrati in Figura 3), propose nuove tecniche e nuovi modelli per studiare la diffusione dell’informazione e le dinamiche di formazione delle reti in grafi evolutivi, ottenendo importanti progressi nella comprensione del comportamento complesso di tali sistemi dinamici [9]. Luca ottenne ulteriori contributi rilevanti nello studio delle dinamiche su grafi (dinamiche base su regole di maggioranza e di media), e della loro capacità di eseguire compiti distribuiti fondamentali, come il consenso auto-stabilizzante [8, 9] e la rilevazione di comunità [6, 10].

Figura 3: Luca con amici e collaboratori a Roma. Da sinistra a destra: Stefano Leucci, Guido Proietti, Pierluigi Crescenzi, Luca Trevisan, Luca Becchetti, Riccardo Silvestri e Luciano Gualà. Foto di Andrea Clementi.

Altri contributi. Nella crittografia, Luca pubblicò articoli influenti sulla comprensione dei limiti delle costruzioni e delle riduzioni “black-box” nella realizzazione di primitive crittografiche [19, 13, 33]. Nella teoria dei codici, diede i primi limiti inferiori per codici localmente decodificabili [27, 20], un filone di ricerca che ha visto una ripresa di attività e progressi dopo due decenni. Nei test di proprietà, dimostrò il primo limite inferiore lineare per testare una proprietà naturale dei grafi (ossia la 3-colorabilità) nei grafi a grado limitato [12].
Luca aveva una straordinaria capacità di identificare rapidamente la rilevanza e il potenziale di una nuova direzione scientifica appena intravista. Comprendeva in profondità il primo articolo su un argomento, scriveva un elegante seguito ricco di intuizioni chiarificatrici e migliorative, ispirando a sua volta ulteriori approfondimenti e progressi. Lo fece ripetutamente, su argomenti diversissimi, dall’amplificazione dell’hardness agli algoritmi sui giochi unici. Ciò è esposto chiaramente dallo stesso Luca nel suo blog, nel post “On being second” [42].

Impatto umano
Oltre alla sua eccellenza nella ricerca, Luca fu leader in un modo diverso (più sottile), ma non meno importante. Come insegnante e divulgatore, Luca risvegliava la curiosità negli altri. Nei suoi numerosi articoli di rassegna [39] e appunti di lezione [38], fornì le esposizioni più chiare e sintetiche di molti risultati fondamentali dell’informatica teorica. Il suo modo di spiegare era generoso, utilizzava pienamente il suo intelletto, ma tenendolo sullo sfondo. Aveva una grande passione nel rendere la teoria dell’informatica accessibile ai nuovi arrivati, e i suoi scritti riuscivano meravigliosamente in questo scopo. Molti di noi hanno regolarmente beneficiato degli appunti di Luca per il proprio insegnamento—aveva il dono di distillare materiale avanzato in uno stile accattivante, perfettamente calibrato e confezionato per le lezioni; infatti, talvolta abbiamo scelto argomenti da trattare nelle nostre lezioni proprio perché Luca aveva scritto degli appunti su di essi!

Sul suo blog, intitolato “In theory” [37], oltre agli appunti di lezione, Luca condivideva con noi anche ciò che stava imparando. Questo includeva argomenti come le funzioni zeta [46], le varietà [44], e altri temi meno familiari al pubblico della teoria della computazione. Era un invito a espandere la nostra immaginazione, e un promemoria che è importante imparare qualcosa semplicemente per il piacere di farlo. Di persona, Luca aveva un modo semplice di porre domande, per poi esplorarle con chiarezza, senza alcuna traccia di competizione o fretta. Conversare con lui era un invito gentile a meravigliarsi. Condivideva generosamente domande e intuizioni, e ripetutamente si impegnò per collaborare con persone più giovani, non necessariamente suoi studenti, compresi noi stessi. Dubitiamo che la nostra esperienza con Luca sia stata unica. Egli rappresentava quanto c’è di meglio nel nostro campo: la sua apertura e la generosità dei suoi leader. Ci auguriamo che lo stile di Luca resti vivo per sempre nella nostra comunità.

Come professore universitario per oltre 25 anni, Luca fu un amatissimo mentore per molti studenti. Collaborò con loro ottenendo risultati influenti e li ispirò a crescere come ricercatori coraggiosi, con progetti ambiziosi. I suoi ex studenti ora sono docenti o ricercatori presso l’Università di Ottawa, NTT Research, TTI-Chicago, l’Università del Michigan, l’Istituto per la Ricerca in Scienze Fondamentali, l’Università di Memphis, l’Università della Pennsylvania e Google. «Come dottorandi eravamo sbalorditi e un po’ intimiditi dalla brillantezza e dalle capacità di Luca», ricorda il suo primo studente di dottorato, Andrej Bogdanov. «La sua personalità gentile e il suo modo di fare umoristico ci misero rapidamente a nostro agio. Luca si divertiva molto a risolvere problemi difficili, ma ciò che davvero amava era parlare, scherzare o semplicemente sedersi insieme davanti a un caffè. Mi ero iscritto per avere un supervisore. Ho trovato un amico per la vita.»

Sul piano personale, Luca fu tra i primi teorici dell’informatica apertamente gay che contribuirono a rendere questa comunità accogliente per ricercatori e studenti LGBTQIA+. Raccontò il proprio coming-out nel 2000 con un post sul blog [47] caratteristicamente ironico (e ormai leggendario), parte del suo sforzo di «riportare il tema gay al centro del Centenario di Turing». Oltre al suo post, ospitò una serie di 8 articoli scritti da colleghi LGBTQIA+ della teoria della computazione e della matematica [45, 15], che raccontavano le loro esperienze nel settore, un’iniziativa che ebbe un enorme impatto sull’inclusività del nostro campo. Questo tipo di contributi significava così tanto per Luca che, anche durante l’ospedalizzazione nelle sue ultime settimane, preparò eroicamente un discorso ispirazionale, invitato a tenere al workshop TCS4All della conferenza STOC, discorso che fu poi tenuto postumo a suo nome [48].

Figura 4: Luca con i suoi primi tre studenti di dottorato. Da sinistra a destra: Kenji Obata, Luca Trevisan, Andrej Bogdanov e Hoeteck Wee.

L’affetto e il rispetto della comunità per Luca si riflettono nei numerosi tributi che gli sono stati dedicati, inclusi workshop e sessioni commemorative ben frequentati durante RANDOM 2024 [2], presso il Simons Institute [3] e l’Università Bocconi [1]; articoli sui blog di numerosi colleghi [4, 5, 14, 18, 24]; una rubrica sui problemi aperti su SIGACT News [16]; e il fatto che la conferenza TCC abbia intitolato a lui il premio per giovani ricercatori.

Conclusione.
Luca Trevisan è stato un ACM Fellow ed è stato il primo informatico eletto all’Accademia Nazionale delle Scienze italiana. In precedenza, nel corso della sua carriera, aveva ricevuto il premio Oberwolfach e una Sloan Research Fellowship, ed era stato relatore invitato al Congresso Internazionale dei Matematici. Aveva fatto parte del comitato di selezione del Premio Turing, del Comitato Scientifico dell’Institute for Pure and Applied Mathematics, e dei comitati editoriali del Journal of the ACM (JACM), delle ACM Transactions on Computation Theory, del SIAM Journal on Computing, e del Bollettino EATCS. Fu presidente del comitato di programma per le conferenze RANDOM 2001, RANDOM 2005, CCC 2005, FOCS 2010 e TAMC 2013.
Luca era uno scienziato e un divulgatore brillante, e un amico e collega sempre divertente. La sua chiarezza e il suo intuito hanno reso più profonda la nostra comprensione e hanno fatto avanzare la frontiera della ricerca nella teoria della computazione. Luca lascia dietro di sé una duratura eredità scientifica. Ci mancherà moltissimo.
Andrea Clementi, Venkatesan Guruswami, Kristin Kane, Alon Rosen, Nikhil Srivastava, Salil Vadhan e Riccardo Zecchina.
Il punto di partenza per questo testo è stato il post sul blog [24].
(versione in inglese pubblicata in Obituary for Luca Trevisan – bulletin.eatcs.org)

References
[1] In memory of Luca Trevisan (1971–2024). A Workshop at Bocconi University, Milan, Italy, 2 December 2024. https://andrejb.net/lucaworkshop.html.
[2] Luca Trevisan memorial session. The 28th International Workshop on Randomization and Computation (RANDOM 2024) and the 27th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2024), 29 August 2024. London, UK. https://approxrandom2024.site/.
[3] LucaFest@Simons. Workshop at the Simons Institute for the Theory of Computing, Berkeley, CA, 8–9 October 2024. https://simons.berkeley.edu/workshops/lucafestsimons.
[4] Scott Aaronson. Luca Trevisan (1971–2024). Shtetl-Optimized blog post, 19 June 2024. https://scottaaronson.blog/?p=8057.
[5] Boaz Barak. Luca Trevisan (1971–2024). Windows On Theory blog post, 19 June 2024. https://windowsontheory.org/2024/06/19/luca-trevisan-1971-2024/.
[6] Luca Becchetti, Andrea Clementi, Pasin Manurangsi, Emanuele Natale, Francesco Pasquale, Prasad Raghavendra, and Luca Trevisan. Average whenever you meet: opportunistic protocols for community detection. In 26th European Symposium on Algorithms, volume 112 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 7, 13. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2018.
[7] Luca Becchetti, Andrea Clementi, and Emanuele Natale. Consensus dynamics: an overview. ACM SIGACT News, 51(1):58–104, 2020.
[8] Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, and Luca Trevisan. Stabilizing consensus with many opinions. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 620–635. ACM, New York, 2016.
[9] Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, and Luca Trevisan. Finding a bounded-degree expander inside a dense one. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, pages 1320–1336. SIAM, Philadelphia, PA, 2020.[10] Luca Becchetti, Andrea Clementi, Francesco Pasquale, Luca Trevisan, Robin Vacus, and Isabella Ziccardi. The minority dynamics and the power of synchronicity. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 4155–4176. SIAM, Philadelphia, PA, 2024.
[11] Mihir Bellare, Oded Goldreich, and Madhu Sudan. Free bits, PCPs, and nonapproximability—towards tight results. SIAM Journal on Computing, 27(3):804–915, 1998.
[12] Andrej Bogdanov, Kenji Obata, and Luca Trevisan. A lower bound for testing 3-colorability in bounded-degree graphs. In 43rd Symposium on Foundations of Computer Science (FOCS 2002), 16-19 November 2002, Vancouver, BC, Canada, Proceedings, pages 93–102. IEEE Computer Society, 2002.
[13] Andrej Bogdanov and Luca Trevisan. On worst-case to average-case reductions for NP problems. SIAM Journal on Computing, 36(4):1119–1159, 2006.
[14] Andrea Celauro. Luca Trevisan, a beautiful mind. Bocconi University blog post, 19 June 2024. https://www.unibocconi.it/en/news/luca-trevisan-beautiful-mind.
[15] Irit Dinur, Martin Farach-Colton, Rosario Gennaro, Oded Goldreich, Sampath Kannan, Robert MacPherson, Ashwin Nayak, Luca Trevisan, and Günter Ziegler. Turing centennial series. in theory blog posts, May–July 2012. https://lucatrevisan.wordpress.com/tag/turing-centennial/.
[16] William Gasarch (ed.), Lance Fortnow, Oded Goldreich, Johan Håstad, Salil Vadhan, and David P. Williamson. Open problems column. SIGACT News, 55(4):32–48, December 2024.
[17] Uriel Feige, Shafi Goldwasser, Laszlo Lovász, Shmuel Safra, and Mario Szegedy. Interactive proofs and the hardness of approximating cliques. Journal of the ACM, 43(2):268–292, 1996.
[18] Lance Fortnow. Luca Trevisan (1971–2024). Computational Complexity blog post, 20 June 2024. https://blog.computationalcomplexity.org/2024/06/luca-trevisan-1971-2024.html.
[19] Rosario Gennaro, Yael Gertner, Jonathan Katz, and Luca Trevisan. Bounds on the efficiency of generic cryptographic constructions. SIAM Journal on Computing, 35(1):217–246, 2005.
[20] Oded Goldreich, Howard Karloff, Leonard J. Schulman, and Luca Trevisan. Lower bounds for linear locally decodable codes and private information retrieval. Computational Complexity, 15(3):263–296, 2006.
[21] W. T. Gowers. A new proof of Szemerédi’s theorem for arithmetic progressions of length four. Geometric and Functional Analysis, 8(3):529–551, 1998.
[22] W. T. Gowers. A new proof of Szemerédi’s theorem. Geometric and Functional Analysis, 11(3):465–588, 2001.[23] Ben Green and Terence Tao. The primes contain arbitrarily long arithmetic progressions. Ann. of Math. (2), 167(2):481–547, 2008.
[24] Venkatesan Guruswami, Nikhil Srivastava, and Kristin Kane. Remembering Luca Trevisan (1971–2024). Calvin Café: The Simons Institute Blog, 18 July 2024. https://blog.simons.berkeley.edu/2024/07/remembering-luca-trevisan-1971-2024/.
[25] Russell Impagliazzo. Hard-core distributions for somewhat hard problems. In 36th Annual Symposium on Foundations of Computer Science, Milwaukee, Wisconsin, USA, 23-25 October 1995, pages 538–545. IEEE Computer Society, 1995.
[26] Russell Impagliazzo and Avi Wigderson. P= BPP if E requires exponential circuits: Derandomizing the XOR lemma. In Frank Thomson Leighton and Peter W. Shor, editors, Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, El Paso, Texas, USA, May 4-6, 1997, pages 220–229. ACM, 1997.
[27] Jonathan Katz and Luca Trevisan. On the efficiency of local decoding procedures for error-correcting codes. In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, pages 80–86. ACM, New York, 2000.
[28] James R. Lee, Shayan Oveis Gharan, and Luca Trevisan. Multiway spectral partitioning and higher-order Cheeger inequalities. Journal of the ACM, 61(6):Art. 37, 30, 2014.
[29] Laurent Miclo. On eigenfunctions of Markov processes on trees. Probability Theory and Related Fields, 142(3-4):561–594, 2008.
[30] Laurent Miclo. On hyperboundedness and spectrum of Markov operators. Invent. Math., 200(1):311–343, 2015.
[31] Cristina Pace. Festa per il primo laureato in informatica: Luca Trevisan, 22 anni, ha discusso la tesi alla presenza del rettore tecce. Il messaggero, 21 July 1993.
[32] Omer Reingold, Luca Trevisan, Madhur Tulsiani, and Salil P. Vadhan. Dense subsets of pseudorandom sets. In 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008, Philadelphia, PA, USA, pages 76–85. IEEE Computer Society, 2008.
[33] Omer Reingold, Luca Trevisan, and Salil Vadhan. Notions of reducibility between cryptographic primitives. In Theory of cryptography, volume 2951 of Lecture Notes in Comput. Sci., pages 1–20. Springer, Berlin, 2004.
[34] Alex Samorodnitsky and Luca Trevisan. A PCP characterization of NP with optimal amortized query complexity. In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, pages 191–199. ACM, New York, 2000.
[35] Alex Samorodnitsky and Luca Trevisan. Gowers uniformity, influence of variables, and PCPs. SIAM Journal on Computing, 39(1):323–360, 2009.[36] Madhu Sudan and Luca Trevisan. Probabilistically checkable proofs with low amortized query complexity. In 39th Annual Symposium on Foundations of Computer Science, FOCS ’98, November 8-11, 1998, Palo Alto, California, USA, pages 18–27. IEEE Computer Society, 1998.
[37] Luca Trevisan. in theory (blog). https://lucatrevisan.wordpress.com/.
[38] Luca Trevisan. Lecture notes. https://lucatrevisan.wordpress.com/lecture-notes/.
[39] Luca Trevisan. Survey papers. https://lucatrevisan.github.io/pubs/index.html#surveys.
[40] Luca Trevisan. When Hamming meets Euclid: the approximability of geometric TSP and Steiner tree. SIAM Journal on Computing, 30(2):475–485, 2000.
[41] Luca Trevisan. Extractors and pseudorandom generators. Journal of the ACM, 48(4):860–879, 2001.
[42] Luca Trevisan. On being second. in theory blog post, 7 November 2006. https://lucatrevisan.wordpress.com/2006/11/07/on-being-second/.
[43] Luca Trevisan. Max cut and the smallest eigenvalue. SIAM Journal on Computing, 41(6):1769–1786, 2012.
[44] Luca Trevisan. The Cheeger inequality in manifolds. in theory blog post, 20 March 2013. https://lucatrevisan.wordpress.com/2013/03/20/the-cheeger-inequality-in-manifolds/.
[45] Luca Trevisan. In theory celebrates the Turing centennial. in theory blog post, 27 May 2014. https://lucatrevisan.wordpress.com/2012/05/27/in-theory-celebrates-the-turing-centennial/.
[46] Luca Trevisan. Riemann zeta functions and linear operators. in theory blog post, 22 September 2014. https://lucatrevisan.wordpress.com/2014/09/22/riemann-zeta-functions-and-linear-operators/.
[47] Luca Trevisan. Turing centennial post 4: Luca Trevisan. in theory blog post, 2 July 2014. https://lucatrevisan.wordpress.com/2012/07/02/turing-centennial-post-4-luca-trevisan/.
[48] Luca Trevisan. Spectral graph theory and three experiences as an outsider. 7th TCS For All Workshop, 24 June 2024. Delivered by Pravesh Kothari and Salil Vadhan. https://youtu.be/O2gpl5l2eQA.
[49] Luca Trevisan, Gregory B. Sorkin, Madhu Sudan, and David P. Williamson. Gadgets, approximation, and linear programming. SIAM Journal on Computing, 29(6):2074–2097, 2000.
[50] Luca Trevisan, Madhur Tulsiani, and Salil P. Vadhan. Regularity, boosting, and efficiently simulating every high-entropy distribution. In Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, France, 15-18 July 2009, pages 126–136. IEEE Computer Society, 2009