Range Avoidance and the Complexity of Explicit Constructions

Abstract

A recent line of work has investigated the complexity of explicit construction problems through the study of a search problem known as Range Avoidance: given as input a boolean circuit C : {0, 1}n → {0, 1}n+1, find an element y ∈ {0, 1}n+1 outside of its range. Analysis of this search problem and its variants has lead to several exciting new results in derandomization and circuit complexity. In this survey we give an overview of this nascent research direction and its connections to some old and fundamental questions in complexity theory.