The hardness vs. randomness paradigm aims to construct pseudorandom generators (PRGs) based on complexity theoretic hardness assumptions. A seminal result in this area is a PRG construction by \cite{NW,IW97}.
A sequence of works \cite{KvM,SU01,Umans02,SU05} generalized the result of \cite{NW,IW97} to nondeterministic circuits. More specifically, they showed that if $\E=\DTIME(2^{O(n)})$ requires ... more >>>

Pseudorandom generators (PRGs) for low-degree polynomials are a central object in pseudorandomness, with applications to circuit lower bounds and derandomization. Viola’s celebrated construction (CC 2009) gives a PRG over the binary field, but with seed length exponential in the degree $d$. This exponential dependence can be avoided over sufficiently large ... more >>>

In this work, we propose a new bounded arithmetic theory, denoted $\mathbf{APX}_1$, designed to formalize a broad class of probabilistic arguments commonly used in theoretical computer science. Under plausible assumptions, $\mathbf{APX}_1$ is strictly weaker than previously proposed frameworks, such as the theory $\mathbf{APC}_1$ introduced in the seminal work of Je?ábek ... more >>>