Distinguisher-Space Analysis: An Instance-Space Framework for Pseudorandomness

Develop a “distinguisher-space analysis” (DSA) that parameterizes and visualizes families of distinguishers (e.g., symmetric functions, permutation branching programs, read-once branching programs) by structural features such as symmetry, sensitivity to Hamming weight, spectral profile, permutation width, and memory. Use DSA to design targeted test suites and new “distinguisher classes” that expose PRG weaknesses. While instance-space analysis has transformed benchmarking in optimization, PRGs are still mostly judged by worst-case indistinguishability theorems or ad hoc empirical tests. DSA treats distinguishers themselves as instances and systematically probes where PRGs fail in practice, guiding the design of “targeted PRGs.” This approach leverages literature on expander-walk pseudorandomness, small-bias distributions, and derandomization needs for specific algorithmic models. It promises a principled methodology to avoid overfitting PRGs to narrow test families and to uncover realistic “failure regions,” leading to more robust PRG design, improved understanding of limits of standard constructions, and new benchmarks for theory-to-practice transfer in pseudorandomness.

References:

1. Instance Space Analysis for the Quadratic Assignment Problem. Jeffrey Christiansen, Kate Smith-Miles Arc Training Centre in Optimisation Technologies, Integrated Methodologies, Applications, S. O. Mathematics, Statistics, The University of Melbourne (2025).
2. Distinguishing, Predicting, and Certifying: On the Long Reach of Partial Notions of Pseudorandomness. Jiatu Li, Edward Pyne, R. Tell (2024). IEEE Annual Symposium on Foundations of Computer Science.
3. Pseudorandomness of expander random walks for symmetric functions and permutation branching programs. Louis Golowich, S. Vadhan (2022). Electron. Colloquium Comput. Complex..
4. Derandomization with Minimal Memory Footprint. Dean Doron, R. Tell (2023). Electron. Colloquium Comput. Complex..
5. Pseudorandomness, symmetry, smoothing: I. H. Derksen, P. Ivanov, Chin Ho Lee, Emanuele Viola (2024). Cybersecurity and Cyberforensics Conference.