Electronic Colloquium on Computational Complexity, Report No. 3 (2006) Making Hard Problems Harder

We consider a general approach to the hoary problem of (im)proving circuit lower bounds. We define notions of hardness condensing and hardness extraction, in analogy to the corresponding notions from the computational theory of randomness. A hardness condenser is a procedure that takes in a Boolean function as input, as well as an advice string, and outputs a Boolean function on a smaller number of bits which has greater hardness when measured in terms of input length. A hardness extractor takes in a Boolean function as input, as well as an advice string, and outputs a Boolean function defined on a smaller number of bits which has close to maximum hardness. We prove several positive and negative results about these objects. First, we observe that hardness-based pseudo-random generators can be used to extract deterministic hardness from non-deterministic hardness. We derive several consequences of this observation. Among other results, we show that if E/O(n) has exponential non-deterministic hardness, then E/O(n) has deterministic hardness 2 n /n, which is close to the maximum possible. We demonstrate a rare downward closure result: E with sub-exponential advice is contained in non-uniform space 2 δn for all δ> 0 if and only if there is k> 0 such that P with quadratic advice can be approximated in non-uniform space n k. Next, we consider limitations on natural models of hardness condensing and extraction. We show lower bounds on the length of the advice required for hardness condensing in a very general model of “relativizing ” condensers. We show that non-trivial black-box extraction of deterministic hardness from deterministic hardness is essentially impossible. Finally, we prove positive results on hardness condensing in certain special cases. We show how to condense hardness from a biased function without any advice, using a hashing technique. We also give a hardness condenser without advice from average-case hardness to worst-case hardness. Our technique involves a connection between hardness condensing and certain kinds of explicit constructions of covering codes.