Winston Li DIMACS 2025

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

2025-W22

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

Week 1

2025-W23

This week I spent a lot of time exploring the existing literature, and trying to understand what is possible to accomplish in the domain of uniformity testing. So far, it’s not looking the best. We’re trying to test uniformity of random sources, but all the directions I’m looking at pose issues.

• If we have a very large domain (say bit strings of length $1024$), nothing can be said about uniformity unless we have an $O(\sqrt{n}\cdot {\epsilon }^{-2})$ samples.
• If we do not care about pure uniformity and only require statistical assurance of some properties about the sequence, existing test suites do a pretty good job already (TestU01, NIST).
• Say a program only requires some conditions of the randomness in order to run properly. I don’t think this can be analyzed generally, as deriving such properties of automata would probably be equivalent to the Halting problem. The best we can do here would likely fall under formal verification (quite a departure from the current topic).

Although I’m feeling more lost than ever, I did read quite a lot of literature. I am also convinced of two truths. Spot the lie!

1. Randomness is hard.
2. I know what I am doing.
3. There are no standards in complexity theory.

Hopefully next meeting will give more insights.

Papers:

1. NIST Test Suite https://nvlpubs.nist.gov/nistpubs/legacy/sp/nistspecialpublication800-22r1a.pdf
2. PCG https://www.pcg-random.org/paper.html
3. Distribution Testing (in progress) https://ccanonne.github.io/files/misc/main-survey-fnt.pdf

Skimmed:

1. Trapdoor Functions https://www.di.ens.fr/users/phan/secuproofs/yao82.pdf
2. Generalized Uniformity Testing https://arxiv.org/pdf/1708.04696
3. Properties of tests for uniformity https://ieeexplore.ieee.org/document/7040743

Link to original

Week 2

2025-W24

I found something of a direction to explore in. We can repurpose the NIST hypothesis tests to check random variables over binary strings by taking several samples, then passing a concatenated string in. This gives a question of whether the tests can detect if something is $\epsilon$-close to uniformity.

This gives a bit of a headache when working with the actual tests though, since $\epsilon$-close is a very weird condition. For something like the monobits test, the test statistic originally takes on a binomial distribution. $\epsilon$-close cuts off the left $\epsilon$ tail and moves that mass to the rightmost value. I can’t think of “nice” way to compute this distribution, which is pretty bad since this is literally the first NIST test.

In other news, I did some reading on the Wishful Thinking Theorem, to better understand sample size bounds for distribution testing of symmetric properties. There is quite a bit of machinery needed to complete the proof, but it is quite interesting.

Papers:

1. Testing Symmetric Properties of Distributions https://dl.acm.org/doi/10.1145/1374376.1374432
2. Distribution Testing (continued) https://ccanonne.github.io/files/misc/main-survey-fnt.pdf

Link to original

Week 3

2025-W25

This week the project is pivoting directions. We plan on reframing the NIST statistical tests in the view of concentration bounds instead of hypothesis testing. As a result, I spent most of the week learning about Chernoff and Hoeffding bounds. Working through the proofs is unironically going to give me brain damage, but seeing these probabilistic tools being applied is very cool!

I’m also pretty sure there is an error with the formulation and proof of Chernoff-Hoeffding in one of the textbooks I was going through. In any case, progress this week can be summarized with working through the proofs of the theorems, and doing the exercises Periklis sent me.

Textbooks:

• Concentration of Measure for the Analysis of Randomized Algorithms (https://dl.acm.org/doi/book/10.5555/1568639)
• Randomized Algorithms (https://www.google.com/books/edition/Randomized_Algorithms/QKVY4mDivBEC?hl=en)

Link to original

Week 4

2025-W26

I spent most of this week trying to construct concentration bounds for the NIST statistical tests. Hopefully, this effort can lead to some unified theory of statistical tests, or discovery of some property that quantifies the quality of each test. I also spent some time trying to think of a distribution that is $\epsilon$ far from uniform, but passes every NIST test. This definitely exists, but each one I can think of breaks a different property.

Unfortunately I couldn’t make much progress. Trying to convert a ${\chi }^2$ test to concentration bounds is proving to be very difficult. There is also a lot of math involved that it outside my knowledge, and alot of existing literature takes advantage of useful approximations (which we are trying to avoid). The fact I was sick for a bit of time also didn’t help.

Sources:

• On statistical distance based testing of pseudo random sequences (https://www.sciencedirect.com/science/article/pii/S0167404815000693)
• Linear rank of random binary matrix (https://epubs.siam.org/doi/epdf/10.1137/1117037)
• Randomness evaluation with DFT (https://arxiv.org/pdf/1701.01960)

Link to original

Week 5

2025-W27

This week we decided to pivot from our original theoretical direction to a different empirical investigation. I finished implementing the BIWZ and Random Rebucketing Extractor from Periklis’ paper from 9 years ago. Took some time relearning C++ and figuring out bit manipulation. I also found some quantum randomness sources, but there isn’t enough data to do anything meaningful. I will probably need to look into other sources of randomness.

The current line of investigation is to try to poison the randomness generated from this extractor, and see how it behaves when thrown into the NIST Randomness tests and a neural data compressor. Ultimately we want to see if we can develop a better test with this method.

Sources:

• True Randomness from Big Data (https://www.nature.com/articles/srep33740)
• CURBy Randomness Beacon (https://random.colorado.edu/)

Link to original

Week 6

2025-W28

This week was spent entirely running experiments and optimizing code. Cumulatively, I improved my original implementation by about 20x by manually doing bit operations. I tried using SIMD and OMP, but they will likely require a much harder refactor before becoming reliable.

I also wasted a few days trying to setup the project on Amarel. Unfortunately, the build system I’m using is a bit new, so I will need to update python before installing it. This opens a whole can of worms with getting a newer version of glibc, binutils, gcc, etc. In any case, I’ve made zero progress on this end, and will likely have to redo my build system, or ship everything through singularity to get it to work. This is probably going to be a requirement, since running tests is time consuming, but doable in parallel.

Next week is the presentation and I have pretty much no content (lol). Hopefully I can make some headway into testing the Neural Data Compression algorithms before then.

Link to original

Resources

• Website Setup

Slides

Introduction

Acknowledgments

This work was carried out as part of the 2025 DIMACS REU program at Rutgers University, supported by NSF grant CCF-2247342.