Affine extractors give some of the best-known lower bounds for various computational models, such as AC$^0$ circuits, parity decision trees, and general Boolean circuits. However, they are not known to give strong lower bounds for read-once branching programs (ROBPs). In a recent work, Gryaznov, Pudl\'{a}k, and Talebanfard (CCC' 22) introduced ... more >>>

We develop the theory of cryptographic nondeterministic-secure pseudorandomness beyond the point reached by Rudich's original work (Rudich 1997), and apply it to draw new consequences in average-case complexity and proof complexity. Specifically, we show the following:

?*Demi-bit stretch*: Super-bits and demi-bits are variants of cryptographic pseudorandom generators which are ... more >>>

We present simple constructions of good approximate locally decodable codes (ALDCs) in the presence of a $\delta$-fraction of errors for $\delta<1/2$. In a standard locally decodable code $C \colon \Sigma_1^k \to \Sigma_2^n$, there is a decoder $M$ that on input $i \in [k]$ correctly outputs the $i$-th symbol of a ... more >>>