Randomness
Prerequisiti
Il corso è espressamente pensato per gli studenti del primo anno della laurea magistrale in matematica e informatica, ma è accessibile anche gli studenti di fisica e agli studenti di PhD in matematica e modelli matematici.
Programma
- Breve riassunto della teoria dell'informazione. Fondamenti di casualità algoritmica: introduzione alla teoria della computabilità, casualità di Martin-Löf, complessità di Kolmogorov. Incomprimibilità. Casualità computabile e nozioni più deboli di casualità algoritmica.
- Casualità vs. pseudocasualità e teoria ergodica. Generatori di pseudocasualità crittografici (PRG). Derandomizzazione. Grafi espandibili.
- Come i sistemi deterministici simulano la vera casualità.
- Casualità nella teoria dei numeri: distribuzione modulo 1. Equidistribuzione. La funzione zeta di Riemann. Modello casuale per i numeri primi. Progressioni aritmetiche. Teorema di Szemerédi, teorema di struttura di Furstenberg (dicotomia tra struttura e casualità) e panoramica del teorema di Green-Tao. Numeri normali.
- Test statistici di stringhe binarie: framework per la verifica statistica delle ipotesi. La suite di test statistici del NIST: test di frequenza, test delle sequenze, test del rango di matrici binarie, test spettrale ed entropia approssimata. Test di complessità lineare. L'algoritmo di Berlekamp-Massey, il test statistico "universale" di Mauer.
- Presentazioni seminariali su alcuni degli argomenti precedenti e su altri collegati (stime di concentrazione, riduzione della dimensionalità, ecc), problemi aperti nella pseudocasualità e nella validazione della generazione di numeri casuali quantistici (QRNG).
Obiettivi formativi
Obiettivo del corso è introdurre le nozioni fondamentali di caso e pseudocaso, la relazione con la teoria dell’informazione, della complessità algoritmica e con la teoria dei numeri e i metodi statistici per decidere se una successione binaria è casuale.
Riferimenti bibliografici
- Wigderson A. (2019) Mathematics and Computation, Princeton University Press
- Downey, R. G., & Hirschfeldt, D. R. (2010). Algorithmic Randomness and Complexity. Springer.
- Nies, A. (2009). Computability and Randomness. Oxford University Press.
- Li, M., & Vitányi, P. (2019). An Introduction to Kolmogorov Complexity and Its Applications (4th ed.). Springer.
- Arora, S., & Barak, B. (2009). Computational Complexity: A Modern Approach. Cambridge University Press.
- Vadhan, S. P. (2012). Pseudorandomness. Foundations and Trends® in Theoretical Computer Science.
- Kuipers, L., & Niederreiter, H. (2006). Uniform Distribution of Sequences. Dover Publications.
- Tao, T. (2008). Structure and Randomness: Pages from Year One of a Mathematical Blog. American Mathematical Society.
- Knuth, D. E. (1997). The Art of Computer Programming, Volume 2: Seminumerical Algorithms (3rd ed.). Addison-Wesley.
- Martin-Löf, P. (1966). The definition of random sequences. Information and Control, 9(6), 602-619.
- Rukhin, A., Soto, J., Nechvatal, J., et al. (2010). A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications. NIST Special Publication 800-22 Revision 1a.
- Maurer, U. M. (1992). A universal statistical test for random bit generators. Journal of Cryptology, 5(2), 89-105.