L'ex dottorando Robin Moser riceve il prestigioso premio G?del
Uno dei premi più prestigiosi nel campo dell'informatica teorica è stato assegnato a Robin Moser (D-INFK) per la sua versione algoritmica del lemma di Lovász-Local.
L'articolo "A constructive proof of the general Lovász Local Lemma" è stato pubblicato nel 2010 sul Journal of the ACM 57(2): 11:1-11:15 insieme all'autore Prof. Gábor Tardos.
Questo lavoro si occupa del Lovász-Local-Lemma (LLL), un importante strumento del metodo probabilistico, che permette di dimostrare l'esistenza di determinati oggetti, anche se si verificano con probabilità esponenzialmente piccole.
La prova originale non era algoritmica e le versioni algoritmiche successive presentavano significative perdite di parametri. L'articolo pubblicato fornisce un paradigma algoritmico semplice e potente che converte quasi tutte le applicazioni note di LLL in algoritmi randomizzati che soddisfano i limiti della prova di esistenza. L'articolo fornisce inoltre un algoritmo derandomizzato, un algoritmo parallelo e un'estensione dell'LLL "unilaterale".
Il nuovo paradigma algoritmico prevede il ricampionamento delle variabili che hanno generato eventi negativi. Tale ricampionamento è stato utilizzato in seguito in numerosi altri lavori, anche non direttamente collegati a LLL. Inoltre, l'articolo fornisce un'elegante prova di correttezza utilizzando gli alberi dei testimoni. Gli alberi dei testimoni hanno avuto un'influenza che va ben oltre Chi siamo e hanno ispirato il metodo della compressione dell'entropia in combinatoria. La potenza e la semplicità del lavoro di Moser ne fanno un successo di vasta portata.
Chi siamo Robin Moser
Robin Moser ha conseguito il dottorato nel 2012 presso il Dipartimento di informatica dell'ETH di Zurigo, dove era membro del gruppo di ricerca del Prof. Emo Welzl. La sua tesi di dottorato era su "Algoritmi esatti per problemi di soddisfazione di vincoli". La sua carriera ha incluso stage presso l'Organizzazione europea per la ricerca nucleare (CERN) a Ginevra e presso la Microsoft Research a Redmond, Washington, USA. Dal 2013 lavora allo sviluppo di software di trading e come analista quantitativo per Circular Capital nella regione di Basilea, in Svizzera.
Chi siamo Il Premio G?del
Il Premio G?del per un lavoro eccezionale nel campo dell'informatica teorica è sponsorizzato e assegnato annualmente dalla European Association for Theoretical Computer Science (EATCS) e dallo Special Interest Group on Algorithms and Computation Theory della Association for Computing Machinery (ACM SIGACT). Il 28° Premio G?del sarà assegnato durante il 47° Colloquio internazionale su robot, linguaggi e programmazione, che si terrà dall'8 all'11 luglio 2020 a Saarbrücken, in Germania. Il premio è intitolato a Kurt G?del in riconoscimento dei suoi significativi contributi alla logica matematica.