Logical Pseudorandomness: Inductive-Logic Indistinguishability and Derandomization

Define distributions D and U to be logically pseudorandom if no inference in a resource-bounded inductive logic significantly increases posterior odds of D over U. Calibrate resource bounds via proof/derivation length or model complexity, connecting these to algorithmic classes such as BPP tests. Explore derandomization equivalences in this logical setting and link to hardness-of-Kolmogorov-complexity characterizations of derandomization. This reframes pseudorandomness beyond measure-theoretic probability, capturing “randomness as lack of inferential leverage” within bounded inference systems. It may yield new lower bounds from proof-complexity assumptions rather than circuit complexity, and expose new barriers or “free lunch” zones where derandomization is possible without PRGs if inference is suitably bounded. The project maps classical distinguish-to-predict paradigms to logical analogues and uses hardness assumptions to characterize when logical derandomization is possible. The impact is a fresh conceptual framework interfacing pseudorandomness and derandomization with logic and proof complexity, diversifying tools for impossibility results and constructive derandomizations.

References:

1. 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.
2. Pseudorandomness of expander random walks for symmetric functions and permutation branching programs. Louis Golowich, S. Vadhan (2022). Electron. Colloquium Comput. Complex..
3. Derandomization with Minimal Memory Footprint. Dean Doron, R. Tell (2023). Electron. Colloquium Comput. Complex..
4. Derandomization from time-space tradeoffs. Oliver Korten (2022). Cybersecurity and Cyberforensics Conference.
5. Guest Column: New ways of studying the BPP = P conjecture. Lijie Chen, R. Tell (2023). Sigact News.
6. Complexity Theory. Peter Bürgisser, Irit Dinur, Salil P. Vadhan (2022). Oberwolfach Reports.
7. Characterizing derandomization through hardness of Levin-Kolmogorov complexity. Yanyi Liu, R. Pass (2022). Electron. Colloquium Comput. Complex..