General Information
- Student: Winston Li
- Mentor: Periklis Papakonstantinou
- School: Rutgers University
- E-mail: 29winstonli@gmail.com
- Project: New approaches to uniformity testing
About Me
I like Hatsune Miku. If this isn’t updated in a week please bother me to fix it
Project Description
This project regards testing whether samples from a random source are uniformly distributed. Randomness plays a significant role in various areas of Computer Science, though its necessity is sometimes debated or not fully understood. For instance, modern Machine Learning (ML) systems, such as those used to train transformers for building Large Language Models, rely on coin-flipping techniques during training. These state-of-the-art systems depend heavily on high-quality random sources. In contrast, in fields like Cryptography, the necessity of randomness is unequivocal. The security of every cryptographic protocol fundamentally depends on the availability of high-quality randomness at the outset. High-quality randomness is defined as “uniform noise” - data that follows a uniform distribution or is statistically indistinguishable from uniform. Given its importance, randomness is a critical resource. This raises two key questions: Where do we obtain randomness, and how can we ensure its quality? This project focuses on the second question: how can we test for uniformity?
The National Institute of Standards and Technology (NIST) has developed standardized test suites to evaluate uniformity. While testing for perfect uniformity is theoretically infeasible, these tests are widely used in practice by systems and protocols that rely on uniform randomness. This project aims to explore the development of a more practical theoretical framework for randomness testing and investigate how deep neural networks might be employed to assess uniformity.
Weekly Log
Week 0
Moved in and stole food from orientation. Wow my hands are typing.
Did some reading to refresh my knowledge on the language of probability. After that, I learned about randomness extractors and spent some time getting familiar with the NIST randomness test suite.
Periklis suggested trying to compare different tests to see which ones perform better. I had an insight on the weekend that statistical tests effectively select a subset of elements to mark as “non-uniform”. In this sense, all the tests function equivalently up to significance level. Thus to find a better test, I’m going to have to scrap the direction of individual statistical tests altogether.
Didn’t read too many papers in depth this week. Next week I’ll focus on learning about distribution testing, and understanding some of the existing results about hypothesis testing.
Also, I cooked (literally).
Link to original
