Search

For [delta] [member of] (0, 1) and k, n [member of] N, we study the task of transforming a hard function f : [{0, 1}.sup.n] [right arrow] {0, 1}, with which any small circuit disagrees on (1 - [delta])/2 fraction of the input, into a harder function f', with which any small circuit disagrees on (1 - [[delta].sup.k])/2 fraction of the input. First, we show that such hardness amplification, when carried out in some black-box way, must require a high complexity. In particular, it cannot be realized by a circuit of depth d and size [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] or by a nondeterministic circuit of size o(k/log k) (and arbitrary depth) for any [delta] [member of] (0, 1). This extends the result of Viola, which only works when (1 - [delta])/2 is small enough. Furthermore, we show that even without any restriction on the complexity of the amplification procedure, such a black-box hardness amplification must be inherently nonuniform in the following sense. To guarantee the hardness of the resulting function f', even against uniform machines, one has to start with a function f, which is hard against nonuniform algorithms with [OMEGA](k log (1/[delta])) bits of advice. This extends the result of Trevisan and Vadhan, which only addresses the case with (1 - [delta])/2 = [2.sup.-n]. Finally, we derive similar lower bounds for any black-box construction of a pseudorandom generator (PRG) from a hard function. To prove our results, we link the task of hardness amplifications and PRG constructions, respectively, to some type of error-reduction codes, and then we establish lower bounds for such codes, which we hope could find interest in both coding theory and complexity theory. Index Terms--Computational complexity, hardness amplification, list-decodable code, pseudorandom generator.

We give a simple construction of distance-preserving mappings from ternary vectors to permutations (3-DPM). Our result gives a lower bound for permutation arrays, i.e., P(n, d) [greater than or equal to] [A.sub.3](n, d), which significantly improves previous lower bounds for d [less than or equal to] 3n/5. Index Terms--Code constructions, distance-preserving mappings, permutation arrays, ternary codes.

We study the distance measures between two probability distributions via two different distance metrics, a new metric induced from Jensen-Shannon divergence, and the well known [L.sub.1] metric. We show that several important results and constructions in computational complexity under the [L.sub.1] metric carry over to the new metric, such as Yao's next-bit predictor, the existence of extractors, the leftover hash lemma, and the construction of expander graph based extractor. Finally, we show that the useful parity lemma in studying pseudorandomness does not hold in the new metric. Index Terms--Jensen-Shannon divergence, expander, extractors, leftover hash lemma, parity lemma.