Myth creation: Polylogarithmic independence fools AC

Note: See first post of the series myth creation for context.

In 1991 [Nis91] constructed a pseudorandom generator for AC (a.k.a. alternating circuits or AC0 circuits), vastly improving the parameters of the pioneering work [AW89]. This is one of my favorite papers ever. (Mini myth creation episode: A large fraction of papers cite [NW94] for this result, possibly even the majority. This issue of credit is indeed complicated, since the 1988 conference version of [NW94] claims ownership for this AC result, and cites an unpublished manuscript with the same title as [Nis91], but with both authors. One can only guess that the authors decided that the AC result should only be attributed to Nisan.)

Nisan’s distribution, and even the earlier one in [AW89], is polylog-wise uniform, that is, any polylog bits are uniform. (The polylog depends on the parameters of the circuit to be fooled in a standard way which is ignored here.) In fact, these results apply to a natural class of polylog-wise distributions: If you pick a uniform sparse linear transformation, the output distribution will be polylog-wise uniform, and Nisan’s proof shows that it fools AC.

However, the proof does not show that every polylog-wise distribution fools AC. Later, Linial and Nisan [LN90] conjectured that polylog-wise uniformity suffices to fool AC, which would generalize both [AW89] and [Nis91].

This problem was somewhat notorious but there was no progress until the paper by Bazzi [Baz09], 15+ years after the conjecture was posed, which proves if for the special case of DNF.

Bazzi’s paper is quite hard to read, and the journal version is also long – 60 pages. Consequently it was hard to find referees, both for the conference and the journal version. Things must have gotten somewhat desperate, because when it finally was my turn to be asked to review the journal version it was deemed appropriate to extract a commitment from me before I could see the submission, something that has never occurred to me for any other paper. My back-and-forth with the author during the refereeing process was then abruptly stopped by, I suspect, the circulation of Razborov’s follow up [Raz09] which dramatically simplifies the presentation, especially with an idea by Wigderson. It was then clear that the results were correct and the paper could be accepted, even though I never claimed to understand Bazzi’s proof for the non-monotone case.

The message in the papers [Baz09] and [Raz09] was loud and clear: You can make progress with just a little duality. From Razborov’s paper:

At this point it was clear that the general case of AC might not be that hard. Shortly after Razborov’s paper, Braverman [Bra09] indeed proved this, albeit with a quadratic rather than linear dependence on the depth of the circuit. This dependence was later improved.

As usual we can look at citation count:

[Bra09] 143

[Baz07] 91

But more interestingly the literature is full of citations like:

My definition of breakthrough result is roughly that of progress on a problem such that many people have thought about it but have been stuck for a long time. This applies to [Baz07].

Approximate number of years gap:

[LN90]–[Baz07]: XXXXXXXXXXXXXXXXX

[Baz07]–[Raz09]: XX

[Raz09]–[Bra09]: X

I also think that if a problem was open even for depth 2, then going from 1 to 2 tends to be more fundamental than going from 2 to d. One can think of situations where this wouldn’t be the case, for example if the depth-2 case was known for a while, and people were really stuck and couldn’t do even depth 3, and that turned out to require a completely different approach. This isn’t the case here.

Consider the following example. Tonight a breakthrough lower bound for depth-3 Majority circuits comes out. Then in a year this result is extended to any constant depth with additional but related techniques. Which result, if any, is the breakthrough?

References