We give a simple explicit hitting set generator for read-once branching programs of width w and length r with known variable order. When r = w, our generator has seed length O(log^2 w + log(1/eps)). When r = polylog w, our generator has optimal seed length O(log w + log(1/eps)). For intermediate values of r, our generator's seed length smoothly interpolates between these two extremes. Our generator's seed length improves on recent work by Braverman, Cohen, and Garg (STOC '18). In addition, our generator and its analysis are dramatically simpler than the work by Braverman et al. Our generator's seed length improves on all the classic generators for space-bounded computation (Nisan Combinatorica '92; Impagliazzo, Nisan, and Wigderson STOC '94; Nisan and Zuckerman JCSS '96) when eps is small. As a corollary of our construction, we show that every RL algorithm that uses r random bits can be simulated by an NL algorithm that uses only O(r/log^c n) nondeterministic bits, where c is an arbitrarily large constant. Finally, we show that any RL algorithm with small success probability eps can be simulated deterministically in space O(log^{3/2} n + log n log log(1/eps)). This improves on work by Saks and Zhou (JCSS '99), who gave an algorithm that runs in space O(log^{3/2} n + sqrt(log n) log(1/eps)).

This is joint work with William Hoza.

We show that popular hardness conjectures about problems from the field of fine-grained complexity theory imply structural results for resource-based complexity classes. Namely, we show that if either k-Orthogonal Vectors or k-CLIQUE requires $n^{\epsilon k}$ time, for some constant $\epsilon>1/2$, to \emph{count} (note that these conjectures are significantly weaker than the usual ones made on these problems) on randomized machines for all but finitely many input lengths, then we have the following derandomizations: - BPP can be decided in polynomial time \emph{using only $n^{\alpha}$ random bits} on average over \emph{any} efficient input distribution, for any constant $\alpha>0$ - BPP can be decided in polynomial time with \emph{no randomness} on average \emph{over the uniform distribution} This answers an open question of Ball et al. (STOC '17) in the positive of whether derandomization can be achieved from conjectures from fine-grained complexity theory. More strongly, these derandomizations improve over all previous ones achieved from \emph{worst-case uniform} assumptions by succeeding on all but finitely many input lengths, as is wanted for asymptotics. Previously, derandomizations from worst-case uniform assumptions were only know to succeed on infinitely many input lengths. It is specifically the structure and moderate hardness of the $k$-Orthogonal Vectors and $\kCLIQ$ problems that makes removing this restriction possible. Via this uniform derandomization, we connect the problem-centric and resource-centric views of complexity theory by showing that exact hardness assumptions about specific problems like k-CLIQUE imply quantitative and qualitative relationships between randomized and deterministic time. This can be either viewed as a barrier to proving some of the main conjectures of fine-grained complexity theory lest we achieve a major breakthrough in unconditional derandomization or, optimistically, as route to attain such derandomizations by working on very concrete and weak conjectures about specific problems.

One of the ultimate goals of symmetric-key cryptography is to find rigorous theoretical framework for building block ciphers from small pseudorandom components, such as cryptographic S-boxes, and then argue why iterating such small components for sufficiently many rounds would yield a secure construction. Unfortunately, a fundamental obstacle towards reaching this goal comes from the fact that traditional security proofs cannot get security beyond than 2^{-n}, where n is the size of the corresponding component. As a result, prior provably secure approaches --- which we call "big-box cryptography" --- always made n larger than the security parameter, which led to several problems divorcing such results from reality. In this work introduce a novel paradigm for justifying the security of existing block ciphers, which we call *small-box cryptography*. Unlike the "big-box" paradigm, it allows one to go much deeper inside the existing block cipher constructions, by only idealizing a small (and, hence, realistic!) building block of very small size n, such as an 8-to-32-bit S-box. It then introduces a clean and rigorous mixture of proofs and hardness conjectures which allow one to lift traditional, and seemingly meaningless, "at most 2^{-n}" security proofs for *reduced-round* idealized variants of the existing block ciphers, into meaningful, *full-round* security justifications of the actual ciphers used in the real world. We then apply our framework to the design of popular SPN-based ciphers, which include AES, Serpent, and PRESENT, among others. To the best of our knowledge, our results give the most accurate and plausible theoretical justification for the security of SPN ciphers to date.

For every small ?, we explicitly construct binary erasure list-decodable codes that can be list-decoded from 1-? fraction of erasures, with near-optimal list-size poly(log(1/?)) and near-optimal rate O(?^(1+?)) where ?>0 is any constant. This is the first construction to break the ?^2 rate barrier, solving a long-standing open problem raised by Guruswami and Indyk, and it does so with a remarkably small list size (we remark that Guruswami showed such a result is impossible using linear codes, and indeed our code is not linear). Equivalently, in terms of dispersers, we construct ?-error one-bit strong dispersers with near-optimal seed-length and near-optimal entropy-loss. The main ingredient in the construction is a new (and nearly optimal) unbalanced two-source extractor. The extractor extracts one bit with constant error from two independent sources, where one source has length n and tiny min-entropy O(loglog n) and the other source has length O(log n) and arbitrarily small constant min-entropy rate. Joint work with Avraham Ben-Aroya and Amnon Ta-Shma.

The recent line of study on randomness extractors has been a great success, resulting in exciting new techniques, new connections, and breakthroughs to long standing open problems in several seemingly different topics. These include seeded non-malleable extractors, privacy amplification protocols with an active adversary, independent source extractors (and explicit Ramsey graphs), and non-malleable codes in the split state model. Previously, the best constructions are given in \cite{Li17}: seeded non-malleable extractors with seed length and entropy requirement O(log n+log(1/\eps)log log (1/\eps)) for error \eps; two-round privacy amplification protocols with optimal entropy loss for security parameter up to \Omega(k/log k), where k is the entropy of the shared weak source; two-source extractors for entropy O(log n log log n); and non-malleable codes in the 2-split state model with rate \Omega(1/log n). However, in all cases there is still a gap to optimum and the motivation to close this gap remains strong. In this talk, I'll describe a set of new techniques that further push the frontier in the above questions. Our techniques lead to improvements in all of the above questions, and in several cases partially optimal constructions. This is in contrast to all previous work, which only obtain close to optimal constructions. Specifically, our results include the first seeded non-malleable extractor where either the seed length or the entropy requirement can be optimal, further improvements on two source extractors, and the first explicit non-malleable code in the 2-split state model with constant rate, which has been a major goal in the study of non-malleable codes for quite some time. We believe our new techniques can help to eventually obtain completely optimal constructions in the above questions, and may have applications in other settings.