This is really a two part question, and they aren't necessarily related. First, my understanding of natural proof barriers is that they are based on the idea that a suitable distribution over small circuits will "look like" a distribution over all functions, at least to someone with limited computational power. So, are there specific models studied of random circuits, and proofs that they do indeed look pseudo-random? The dialogue in Gowers' blog some time ago indicates some of the difficulty in choosing such a distribution, as at one point one of the speakers inadvertently creates a distribution (over formulas rather than circuits) which fails even some fairly simple tests as pointed out in the comments (see http://gowers.wordpress.com/2009/09/22/a-conversation-about-complexity-lower-bounds/ ). For example, I know that there are results like Mark Braverman's about polylog independence, but are there results showing that a given circuit distribution produces an output with such polylog independence w.h.p?

Second question: is the state of the art any better on circuit lower bounds if we consider N-to-N functions rather than N-to-1 functions? That is, are there explicit functions with N input bits and N output bits for which a superlinear bound is proven, where the results are better than what one can prove for functions with 1 output bit? Would lower bounds on N-to-N functions be "almost as interesting" as those on N-to-1, or is this much less interesting?

  • $\begingroup$ Done. It's somewhere in the middle of the "conversation". $\endgroup$ Commented Dec 16, 2010 at 18:05


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.