Randomness
Prerequisiti
The course is specifically designed for first-year master's students in mathematics and computer science, but is also accessible to physics students and PhD students in mathematics and mathematical modeling.
Programma
- A brief summary of information theory. Foundations of Algorithmic Randomness: introduction to computability theory, Martin-Löf randomness, Kolmogorov complexity. Incompressibility. Computable Randomness and weaker notions of algorithmic randomness.
- Randomness vs. Pseudorandomness & Ergodic Theory. Cryptographic Pseudorandom Generators (PRGs). Derandomization. Expander graphs
- How deterministic systems simulate true randomness.
- Randomness in Number Theory: Distribution Modulo 1. Equidistribution. The Riemann Zeta Function. Random model for prime numbers. Arithmetic progressions. Szemerédi’s Theorem, the Furstenberg Structure Theorem (Dichotomy of Structure vs. Randomness), and the Green-Tao Theorem overview. Normal Numbers.
- Statistical Testing of Binary Strings: Framework for Statistical Hypothesis Testing. The NIST Statistical Test Suite: Frequency tests, Runs test, Binary Matrix Rank test, spectral test and approximate entropy. Linear complexity tests. The Berlekamp-Massey algorithm, Mauer's "Universal" statistical test.
- Seminar presentations on some of the previous topics and other related ones (concentration estimates, dimensionality reduction, etc.), open problems in pseudorandomness and quantum random number generation (QRNG) validation.
Obiettivi formativi
The aim of the course is to introduce the fundamental notions of randomness and pseudorandomness, their relationship with information theory, algorithmic complexity, and number theory, and the statistical methods for deciding whether a binary sequence is random.
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.