Given a Boolean circuit $C$, we wish to convert it to a circuit $C'$ that computes the same function as $C$ even if some of its gates suffer from adversarial short circuit errors, i.e., their output is replaced by the value of one of their inputs [KLM97]. Can we ... more >>>

Two of the most useful cryptographic primitives that can be constructed from one-way functions are pseudorandom generators (PRGs) and universal one-way hash functions (UOWHFs). The three major efficiency measures of these primitives are: seed length, number of calls to the one-way function, and adaptivity of these calls. Although a long ... more >>>

We consider the range avoidance problem (called Avoid): given the description of a circuit $C:\{0, 1\}^n \to \{0, 1\}^\ell$ (where $\ell > n$), find a string $y\in\{0, 1\}^\ell$ that is not in the range of $C$. This problem is complete for the class APEPP that corresponds to explicit constructions of ... more >>>