Seminario Interdipartimentale di Algoritmica
 
 
 

Dipartimento di Informatica e Sistemistica - DIS
via Salaria 113, II piano
Aula C2

Abstract:
Codici a correzione di errori basati su polinomi in piu' variabili ammettono algoritmi molto efficienti (che usano tempo logaritmico o, in certi casi, costante) per rilevare la presenza di errori e per decodificare. Una procedura efficiente di decodifica ricostruisce (con alta probabilita') un bit (on un blocco di bit) desiderato del messaggio originale data una codifica corrotta. Una procedura di rilevazione di errori distingue (con alta probabilita') una parola di codice valida da una codifica corrotta che contenga una alta frazione di errori. L'esistenza di tali procedure sub-lineari e' nota, e molto usata, in teoria della complessita', ed ha rilevanza in program-checking, nello studio della complessita' nel caso medio, nella costruzione di probabilistically checkable proofs (PCP), e in private information retrieval (un problema crittografico). In questo seminario presenteremo risultati e questioni aperte relativi ai seguenti problemi: e' possibile costruire procedure sub-lineari di decodifica e rilevazione di errori per classi piu' generali di codici a correzione di errori? C'e' un trade-off tra l'efficienza delle procedure e la ridondanza del codice? Ulteriori progressi in questa linea di ricerca potrebbero portare, tra l'altro, a una migliore valutazione della praticabilita' di sistemi di private information retrieval con sicurezza teorico-informazionale e a una dimostrazione piu' semplice del teorema di PCP. Rimane da vedere se tali codici saranno utili in futuro nella pratica della trasmissione e archiviazione di dati in sistemi non affidabili