SFB funding period 1 (2014-2017)

Pseudorandom numbers are generated by deterministic algorithms and are not random at all. However, in contrast to truly random numbers they guarantee certain randomness properties.

Their desirable features depend on the application area. For example, uniformly distributed sequences of pseudorandom numbers are needed for Monte Carlo methods, unpredictable sequences for cryptography, and uncorrelated sequences for wireless communication or radar. Corresponding quality measures are discrepancy for uniform distribution, linear complexity for unpredictability, and correlation.

The main goal of this project is to find relations between different measures of pseudorandomness. For example, Dorfer, Niederreiter and Winterhof showed that the linear complexity provides essentially the same quality measure as certain lattice tests coming from the area of Monte Carlo methods. Moreover, Mauduit, Niederreiter and Sarközy studied links between uniformly distributed pseudorandom sequences of real numbers in $[0, 1)$ and the correlation of pseudorandom binary sequences derived from them.

Brandstätter and Winterhof proved a relation between the linear complexity and the higher order correlation of binary sequences.

Roughly speaking, the discrepancy is a stronger measure than correlation which is a stronger measure than linear complexity.

There are many other related measures of pseudorandomness for sequences and we want to analyze their hierarchy.