We explicitly construct an extractor for two independent sources on n bits, each with
polylogarithmic min-entropy. Our extractor outputs one bit and has polynomially small error …

A long line of work in the past two decades or so established close connections between
several different pseudorandom objects and applications, including seeded or seedless non …

In this paper we give improved constructions of several central objects in the literature of
randomness extraction and tamper-resilient cryptography. Our main results are:(1) An …

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 …

We give an explicit construction of an affine extractor (over F_2) that works for affine sources
on n bits with min-entropy k≧\logn⋅(\log\logn)^1+o(1). This improves prior work of Li …

We construct explicit deterministic extractors for polynomial images of varieties, that is,
distributions sampled by applying a low-degree polynomial map f: F qr→ F qn to an element …

We show a general framework for constructing non-malleable codes against tampering
families with average-case hardness bounds. Our framework adapts ideas from the Naor …

The focus of this survey is the question of quantified derandomization, which was introduced
by Goldreich and Wigderson [44]: Does derandomization of probabilistic algorithms become …

We establish several “sharp threshold” results for computational complexity. For certain
tasks, we can prove a resource lower bound of nc for c≥ 1 (or obtain an efficient circuit …

We consider the problem of extracting randomness from sumset sources, a general class of
weak sources introduced by Chattopadhyay and Li (STOC, 2016). An (n, k, C)-sumset …