Randomness

seminar and a short oral exam

The exam will consist of a seminar on an agreed topic and a short oral exam with some questions on topics from the course syllabus.

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.

• 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.

• 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.