Abstract
A common theme in many areas of theoretical computer science is that it is sometimes much easier to compute approximations to a function than to compute the function exactly, while sometimes approximation does not make things any easier. In this talk, we explore the hardness of approximating functions in the circuit complexity model. Specifically, we restrict our attention to depth-2 circuits (i.e., DNFs and CNFs) and we ask how large such a circuit must be to agree with a given target function on 99% of all possible inputs. As we will see during the talk, the study of this question leads to surprising results and to interesting connections between complexity theory and information theory, the analysis of Boolean functions, and extremal combinatorics.
This talk is based on joint works with Eric Blais.