Archive for October 2nd, 2009

A conversation about complexity lower bounds, III

October 2, 2009

The story so far: :), 8) and 😐 have been discussing how it might be possible to prove lower bounds for formula or circuit complexity. They have come to some understanding of what a proof could not be like, and in particular they have looked at examples of proof attempts that are ruled out by the result of Razborov and Rudich on natural proofs. But 🙂 has proposed basing a proof on the dual of the $U^k$ norm, with $k$ around $\log n.$ Several observations have been made that suggest that this is very unlikely to work, but the approach has not been definitively killed off. In the next stage of the conversation, our characters investigate the approach in more detail, finding further ways to attack it. They end on an optimistic note, but that optimism will be shaken in later instalments of the dialogue.

Incidentally, I’ve decided to let the rate that I post instalments be governed by the statistics: when they suggest that most people who are going to read an instalment have done so, then I’ll post the next one. It’s not an exact science, of course.

*************************************************

🙂 Before we dismiss the $U^k$ norm for unbounded $k$ as a useful complexity measure, it still seems worth thinking about the following problem.

Problem. Let $f$ and $g$ be two Boolean functions. If $\|f\|_{U^k}^*\leq A$ and $\|g\|_{U^k}^*\leq B$, then how big can $\|f\vee g\|_{U^k}^*$ be?

😐 I suppose quite a nice feature of that problem is that you can start right at the bottom, with $k=2$. (more…)