A conversation about complexity lower bounds, III

Boolean circuit complexity, U^k Gowers norm, polynomial phase functions, lower bounds theory, computational complexity classes

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$.

🙂 Yes indeed. I’ve been thinking about that. I have to say that it’s not obvious to me even that the answer is independent of $n$. A preliminary observation is that if $f$ is a basic function, then $\|f\|_{U^2}^*=1$, and if $f$ and $g$ are two different basic functions, then $\|f\vee g\|_{U^2}^*=2^{4/3}$. Both these facts can be proved by “cheating” and using the fact that $\|f\|_{U^2}^*=\|\hat{f}\|_{4/3}$. The Fourier transform of $f$ is $1$ at one point and $0$ everywhere else, while the Fourier transform of $f\vee g$ is $\pm 1/2$ at four points and $0$ everywhere else.

Ah, I think I’ve come up with a fairly disastrous example. Choose a positive integer $r$ and take $f(x)$ to be a random function that depends just on $x_1,\dots,x_r$ and $g(x)$ to be a random function that depends just on $x_{r+1},\dots,x_{2r}$. Then $f\vee g$ is a randomish function of $x_1,\dots,x_{2r}$. It’s not hard to show that the $U^2$ dual norms of $f$ and $g$ are something like $2^{r/4}$. I’m not sure what the norm of $f\vee g$ is, but I think it might be more like $2^{2r/4}=2^{r/2}$. If so, then we’d be in big trouble.

😐 What makes you think that the norm of $f\vee g$ is that big?

🙂 Well, somehow $f\vee g$ is a bit like a “tensor product” of $f$ and $g$, and so the badnesses of $f$ and $g$ feel as though they could multiply together.

😐 But what would the function be that norms $f\vee g$?

🙂 Good question. Let’s try to find one. I think that $f$ norms itself and $g$ does too. (If not, I can create explicit examples of quadratic phase functions where that is definitely the case.) So we could try taking $fg$ as a norming function. Since $f$ and $g$ depend on disjoint sets of variables, it isn’t too hard to prove that $\|fg\|_{U^2}=\|f\|_{U^2}\|g\|_{U^2}\approx 2^{-r/2}$. Just to make things simpler, let’s look at $f\wedge g$ instead. Then, as we’ve already commented, $f\wedge g=(1+f)(1+g)/2-1=(f+g+fg-1)/2$, so we want a lower bound for

$$\langle fg,-1+f+g+fg\rangle.$$

Now the pointwise product of $fg$ with $f$ is just $g$, and similarly the pointwise product with $g$ is $f$. Also, since $f$ and $g$ are “independent”, the expectation of $fg$ is zero. So all the first three terms are small. The last one, since $fg$ is a Boolean function, is $1$. Therefore, $\langle fg,f\wedge g\rangle=1/2$. Since $\|fg\|_{U^2}=2^{-r/2}$, we get that $\|f\wedge g\|\geq 2^{r/2}/2$. So my prediction seems to have been correct, unfortunately.

If, as this calculation suggests, pointwise maxima somehow behave more like tensor products than sums, then one might expect $\log\|f\|_{U^k}^*$ to be a formal complexity measure, or at least to have more of a chance of being one. But that’s not very encouraging, since the largest value it can take is not going to be more than $\log(2^n)=n$, so there would be no hope of proving superlinear lower bounds.

8) Well, I can’t say that came as a huge surprise.

🙂 The argument seems to apply to any dual norm if the original norm has what one might call the product property: that configurations in a product group $G\times H$ are of the form $((g_1,h_1),\dots,(g_s,h_s))$, where $(g_1,\dots,g_s)$ is a configuration in $G$ and $(h_1,\dots,h_s)$ is a configuration in $H$. Unfortunately, that’s a pretty common property for these norms to have.

8) That’s the price you pay for proposing a complexity measure without any thought for why it should do the job.

🙂 I think that’s slightly unfair. I did at least think about why it wouldn’t trivially not do the job.

Actually, hang on a moment.

8) Groan.

🙂 No, bear with me for two more minutes. Probably this is nothing, but it occurs to me that we ought to think a little bit harder about the argument above before being certain that it applies to the $U^k$ norm when $k=C\log n$.

8) Why? Where was the dependence on $k$?

🙂 Well, it looks like a merely technical point at first, but I’m starting to wonder. You recall that we found Boolean functions $f$ and $g$ for which we could prove that $\|f\vee g\|^*\geq\|f\|^*\|g\|^*/2.$ Now in order for that to be significant, we need at least one of $\|f\|^*$ and $\|g\|^*$ to be bigger than $\sqrt{2}.$ When $k$ is bounded, that’s easy to achieve: you just pick a random function that depends on a small but bounded number of variables. But when $k$ is unbounded, the number of variables it has to depend on becomes unbounded too. Indeed, a random function that depends on $r$ variables will have $U^k$ norm about $2^{-r/2^k}$, so we appear to need $r$ to be about $2^k$, which is bigger than $n$. So here’s a potential reason that the $U^k$ norm could behave genuinely differently when $k$ passes the $\log n$ threshold.

Of course, we’re still in the realms of guesswork here, but this suggests we need to think a little further.

😐 Can I interject at this point?

🙂 Of course.

😐 Well, doesn’t the argument you’ve just given show that no function has small $U^k$ norm? After all, if random functions have the smallest $U^k$ norms and you need more than $n$ variables to get them to be small, then you seem to have a proof that all functions have large $U^k$ norm. Doesn’t that just kill off the idea completely?

🙂 Oops. Nor for the first time I feel quite embarrassed. Indeed, the $U^k$ norm of an arbitrary Boolean function is at least $N^{1/2^k}$, which becomes constant when $2^k=\log N=n$. I was forgetting that when you calculate the $U^k$ norm then the power you take is exponentially small in $k$, so $k=\log\log N$ is actually a bigger function than it looks.

8) Can we stop this conversation now?

🙂 OK.

…………….

No, sorry, no, hang on a moment!

8) All right, but at the next collapse I’m off for some coffee, and I can’t promise you that I’ll be back.

🙂 Well, all I wanted to say was that :|’s observation doesn’t kill off the approach at all. In fact, the more I think about it, the more I wonder whether we shouldn’t in fact be encouraged by it.

8) Your optimism really does know no bounds.

🙂 Just let me explain what I mean. The point I want to make is that even if all $U^k$ norms lie between $1$ and $2$ (or perhaps $1$ and $1.01$ or something like that), the $U^k$ dual norm could still be a useful measure of complexity. It might be that all the norms of low-complexity functions were incredibly close to 1. Perhaps we would find that it was more natural to raise everything to the power $2^k$, in which case the largest possible value would be $N$, which is back to being acceptably large. In short, what I’m saying is that what matters is behaviour within a scale: if the scale looks a bit narrow, then rescale it.

That looks like another desperate manoeuvre, and perhaps it is. But why did I say that it might even be positively encouraging rather than merely not disastrous? The reason is that the argument that the dual of the $U^k$ norm is not a complexity measure really does fail when $k$ is of order $\log n$, because then that seemingly innocuous division by 2 becomes much more important. So we’re back in the nice position of having a proposed measure of complexity, and no convincing reason for its not working.

8) Yes, but you don’t have any convincing reason in favour of its working either.

🙂 I fully admit that. All I’m saying is that we need to go back to the phase of trying to attack it.

There seem to me to be two natural lines of attack, and I can’t get either of them to work. The first is to look for a more sophisticated example of a pair of Boolean functions where $\|f\vee g\|_{U^k}^*$ or $\|f\wedge g\|_{U^k}^*$ is big given the values of $\|f\|_{U^k}^*$ and $\|g\|_{U^k}^*$. The second is to try to come up with some low-complexity function $f$ such that $\|f\|_{U^k}^*$ is near to being maximal.

Let me start with the first approach. Now this is a bit strange, because so far, as a result of the division by 2, I haven’t even got an example where I’ve managed to show that $\|f\vee g\|_{U^k}^*$ is bigger than $\|f\|_{U^k}^*\vee\|g\|_{U^k}^*.$ But let’s have a look again at the example where $f$ is a random function of $r$ variables and $g$ is a random function of a disjoint set of $r$ variables. As I commented before, $f\wedge g=(f+g+fg-1)/2.$ If $k$ is small and $r$ is big, then it seems pretty clear that $fg$ is a good choice of function to norm $(f+g+fg-1)/2.$ That is because $\|fg\|_{U^k}$ is much smaller than any of $1$, $\|f\|_{U^k}$ or $\|g\|_{U^k}$ so it is an efficient function to use for providing a lower bound for the $U^k$ dual norm. But if $k$ is very large, then the norms of all vectors are pretty similar and this argument breaks down. So we could for example consider taking $f+g+fg-1.$

But what is $\|f+g+fg-1\|_{U^k}$? Let’s assume that $\|f\|_{U^k}$ and $\|g\|_{U^k}$ are both at most $1-\epsilon.$ Then $\|fg\|_{U^k}$ is at most $(1-\epsilon)^2$, so by the triangle inequality it is at most $1+2(1-\epsilon)+(1-\epsilon)^2=(2-\epsilon)^2.$ It follows that $\|f+g+fg-1\|_{U^k}^*$ is at least $4/(2-\epsilon)^2=1/(1-\epsilon/2)^2.$ Unfortunately, this is smaller than $1/(1-\epsilon),$ which is the lower bound we know for $\|f\|_{U^k}^*$ and $\|g\|_{U^k}^*.$ But that could be because of our inefficient use of the triangle inequality. What, for instance, do we expect $\|f+g\|_{U^k}$ to be when $f$ and $g$ are random Boolean functions of disjoint sets of $r$ variables each?

Hmm … I don’t yet see how to answer this question precisely enough. So let me make a general remark that clarifies a little :|’s remark about the dual norm never being big. If $k$ is $C\log n$ and $f$ is any function defined on $\{0,1\}^n$ (not necessarily Boolean), then a trivial upper bound for $\|f\|_{U^k}$ is $\|f\|_\infty,$ since if $|f(x)|\leq 1$ for every $x,$ then the average in the expression for $\|f\|_{U^k}^{2^k}$ is also at most 1.

But for large $k$ this is also a lower bound. Indeed, if $f(u)=1,$ then when you choose a random $x,a_1,\dots,a_k,$ the probability that $x=u$ and $a_1=\dots=a_k=0$ is $N^{-(k+1)}=2^{-n(k+1)}.$ It’s not too hard to prove that this implies that $\|f\|_{U^k}\geq 2^{-n(k+1)/2^k}.$ So as long as $2^k$ is at least comparable to $n(k+1),$ the $U^k$ norm is equal to the $L_\infty$ norm up to a constant. It follows that the $U^k$ dual norm is equal to the $L_1$ norm up to a constant.

😐 Doesn’t that make it useless as a complexity measure?

🙂 No. As I’ve already said, but perhaps not quite in these terms, I am now trying to understand the $U^k$ and $U^k$ dual norms at a finer level of detail than just equality up to a constant. In fact, if the approach stands any chance of working, I think it will be just this feature that distinguishes it from the $U^k$ norms for bounded $k$ and may lead to different behaviour.

8) I still don’t see any particular reason to suppose that for large $k$ the $U^k$ norm of every low-complexity function is large.

🙂 OK, you’re moving to the second line of attack, so let’s have a go at that. A first idea is that when $k$ is bounded, if we believe the natural-proofs heuristic, then a random formula (I’m still thinking about formula complexity, by the way) gives an extremal example. So it makes sense to try to work out, or at least guess, what $\|f\|_{U^k}^*$ is when $f$ is a random low-complexity function. At the moment I don’t have a clear idea how to go about that. All I would point out is that, at least to start with, the functions one builds up all have norm 1. That’s because $(-1)^{p(x)}\wedge (-1)^{q(x)}=(-1)^{p(x)q(x)}$. Therefore, if $f$ and $g$ are polynomial phase functions of low degree (meaning functions like $(-1)^{p(x)}$, with $p$ a low-degree polynomial), then so are $f\vee g$ and $f\wedge g$.

😐 Sorry to interrupt with a very basic question, but how do you prove that for $\vee$? Your proof applied to $\wedge$ only.

🙂 Yes, but basically anything you can do for $\wedge$ you can do for $\vee$. That’s because $f\vee g=-((-f)\wedge(-g))$, which is one way of stating de Morgan’s laws.

😐 I see. And if $f(x)=(-1)^{p(x)}$, then $-f(x)=(-1)^{1-p(x)}$, so you’ve got another function of the same kind.

🙂 Exactly. So as I say, it takes a while to produce a Boolean function that doesn’t have norm 1. That is slightly disconcerting, because it makes it a little hard to see how an inductive argument would work. But maybe one could come up with a more sophisticated complexity measure that looked at all $U^k$ dual norms at once and picked out the point at which they started to be large, or something like that.

Let me leave that question aside and turn to the question of trying to devise an explicit low-complexity Boolean function $f$ such that $\|f\|_{U^k}^*$ is large.

If you recall from way back in the conversation, the natural explicit example of a function with very low $U^2$ norm was a quadratic phase function. I suggested the function $f(x)=(-1)^{x_1x_2+\dots+x_{n-1}x_n+x_nx_1}$. Now why didn’t I just go for the simpler $(-1)^{x_1x_2}$? The reason is that if you use a low-rank quadratic form, then you can cut the function up into nice linear pieces: this function, for example, is constant on each of the four subspaces you get by fixing the coordinates $x_1$ and $x_2$. The result is that you don’t get a small $U^2$ norm after all.

With this thought in mind, it would seem that the natural choice for an explicit Boolean function with almost minimal $U^k$ norm would be a polynomial of degree $k+1$ that in some sense has “high rank” so that it can’t be built out of lower-degree polynomials.

Now a problem I have when trying to build an explicit polynomial phase function of high degree is that it doesn’t seem to be easy to find one for which I can prove that it really does have a small $U^k$ norm. Incidentally, the unboundedness of $k$ makes a difference here: when $k$ is bounded we can just pick a random collection $\mathcal{A}$ of sets of size $k$, define $p(x)$ to be $\sum_{A\in\mathcal{A}}\prod_{i\in A}x_i$ (that is a function from $\mathbb{F}_2^n$ to $\mathbb{F}_2$), and set $f(x)=(-1)^{p(x)}.$ Computing this function will take something like $n^k$ steps (and can easily be done by a formula of that size too). But that’s not a polynomial if $k$ is unbounded, so we need to think of an explicit example.

For instance, we could try the obvious generalization of what I did in the case $k=2$ and consider the polynomial that you get when $\mathcal{A}$ consists of the $n$ sets of the form $\{i+1,\dots,i+k\}$, where addition is mod $n$.

But if we restrict to the subspace $x_k=x_{2k}=\dots=x_{\lfloor n/k\rfloor k}=0$, then this polynomial is identically zero. The codimension of this subspace is about $n/k$, so the $U^k$ norm looks to me as though it is at least $(2^{-n/k})^{1/2^k}$, which is very close to 1, since $n/k2^k\rightarrow 0.$ (Again, this argument does not work when $k$ is bounded.)

That doesn’t really prove much, since I could obviously make some much cleverer choices of $\mathcal{A}$, though always with the strong constraint that the resulting polynomial must be of low complexity. But I can also make some much cleverer choices when I try to restrict the polynomial to a set where it is constant: for example, instead of restricting to a linear subspace, I can restrict to a degree-$(k-1)$ submanifold of $\mathbb{F}_2^n.$

That’s where I’ve got so far. I have to say that the question I like best out of the ones I’ve just raised (either explicitly or implicitly) is the one about random low-complexity functions and their $U^k$ norms and dual norms. If I could convince myself that a random low-complexity function almost certainly had a fairly large $U^k$ norm, then I’d be pretty excited.

8) What you’re saying is reminiscent of a standard proof technique: the method of random restrictions.

🙂 What’s that?

8) Well, some nice lower bounds have been proved as follows. You take a function of low complexity, and you randomly fix a number of its coordinates. You then argue that this hugely simplifies the function — for instance, by making it almost constant. And then you point out that the parity function cannot be simplified unless you restrict all the variables. In this way it has been shown that the parity function has formula-size at least $n^2$ (this is a result of Andreev) and cannot be computed by a circuit of constant depth and polynomial size (this is a result of Hastad).

It seems to me that you are randomly restricting to a $k$-dimensional subspace and hoping that a very slight simplification will occur that encourages your Boolean function to have even parity. It’s not quite the same, since you don’t expect this simplification to be all that dramatic — just faintly detectable.

🙂 Hmm. I think it is fairly different, but it’s quite a nice way of thinking about the problem, because if we take a random low-complexity Boolean function and restrict it to a random $k$-dimensional affine subspace, the result ought itself to be some kind of random low-complexity Boolean function.

8) How do you mean?

🙂 Well, let $X$ be a random $k$-dimensional affine subspace and let $e_i$ be the basic function $e_i(x)=(-1)^{x_i}$. Then there are two possibilities. Either $X$ is contained in one of the two subspaces $x_i=0$ or $x_i=1$, or we have two subspaces $X\cap\{x_i=0\}$ and $X\cap\{x_i=1\}$, and the restriction of $e_i$ to $X$ is $1$ on the first and $-1$ on the second. In other words, the restriction of a basic function is either constant or very similar to a basic function. And with high probability it is the latter, since a $k$-dimensional subspace will have constant $x_i$ coordinate with probability $2^{-k}$.

Since $2^k>n$, this in fact shows that with reasonably high probability all the basic functions will end up non-constant when you restrict them to $X$. And then when you build up a low-complexity function $f$ using Boolean operations, you do exactly the same to the restriction of $f$ to $X$.

Does this mean that inside $X$ there is a little copy of $f$? Not at all, because if you look at the intersections of the sets where the basic functions are constant, then you find that they don’t behave as they should. To give a trivial example, the intersection of all the sets $\{x\in X:x_i=0\}$ is almost certainly empty.

And now my intuition is starting to desert me again. What I want to understand is what happens when I just build up a function randomly using Boolean operations. Could it be that then the random restriction cleverly manages not to lose information? I think what I mean by that is something like that one should be able to reconstruct the original function pretty well from its restriction to a random $k$-dimensional subspace.

That feels plausible somehow. But if it is true, then why would it help to produce a large $U^k$ norm? One might think it would do the opposite, since all those random restrictions of random low-complexity functions would still look random. It’s not clear where the bias towards even parity would come in. But that thought may be orthogonal to what is really going on: even if a random restriction does indeed look pretty random, we are looking for just a small proportion of subspaces where it isn’t random. In other words, we are interested in a low-probability event.

8) If I had to evaluate what I’ve heard so far, I think the point where your approach is most vulnerable to attack is one you mentioned just before we started talking about random restrictions. You’ve just mentioned that if it were possible to take a random polynomial of degree $k,$ then it would have a very low $U^k.$ You then made a rather pathetic effort to come up with an explicit example that would do the job, and were encouraged by the fact that it failed. But perhaps there is a clever method of defining a pseudorandom polynomial of degree $k.$

🙂 Do let me know if you find one. But I’m having trouble doing so. And bear in mind that there’s an important distinction between explicitly defining a set system $\mathcal{A}$ that looks like a random collection of sets of size $k,$ and defining a low-complexity function $f$ such that $f$ is a polynomial of the form $f(x)\sum_{A\in\mathcal{A}}\prod_{i\in A}x_i,$ where $\mathcal{A}$ looks like a random collection of sets of size $k.$

Also, now that I think about it, there is a better reason that my “pathetic” attempt, as you put it, failed. That is that the polynomial $\sum_i x_{i+1}\dots x_{i+k}$ is almost always zero, so the polynomial phase function that results is almost always 1. Indeed, the probability that it is not zero if you choose a random $x$ is at most $2^{-k}n,$ which is very small when $k$ is $2\log n,$ say. One could cure that by taking a sum of $2^k$ monomials, but if it’s a small challenge even to get the polynomial not to be almost constant, a lack of quasirandomness that even the $U^1$ seminorm will pick up, think how much harder it will be to make it quasirandom for the $U^k$ norm.

Ah, but I’ve now had an idea. It’s a way of building up a random polynomial of degree at most $k$ and complexity at most $m.$ I’m going to think of it as a function from $\{0,1\}^n$ to $\{0,1\}$ rather than to $\{-1,1\}.$ I then allow myself three operations, which are $f\mapsto 1-f,$ $(f,g)\mapsto fg$ and $(f,g)\mapsto f+g.$ The first two of these are Boolean operations (NOT and AND) and the third, addition mod 2, or parity, is easily built out of Boolean operations.

😐 If you can easily build it out of the other two operations, then why include it?

🙂 Because I’m going to insist that it is used a lot. Once I’ve got these operations, I can build up functions rather as one does with circuit complexity: I just take a sequence of functions $f_1,\dots,f_m$ such that each $f_r$ is built from earlier functions $f_s$ and $f_t$, or possibly just $f_s$, using one of the permitted operations. Because parity can be built easily out of $\wedge$ and $\vee$ (and I should have mentioned that multiplication is $\wedge$), the circuit complexity of $f_m$ is at most $C m$. Also, the degree of $f_r$ is the maximum of the degrees of $f_s$ and $f_t$ if $f_r=f_s+f_t$, and the sum of their degrees if $f_r=f_sf_t$ (and the degree of $f_s$ if $f_r=1-f_s$). Therefore, if I want to keep the degree down, then all I have to do is make sure that I use multiplication only a limited amount.

One way of doing that is as follows. I start by producing a “layer” of polynomially many functions of the form $\sum_{i\in A}e_i$, where the $e_i$ are basic functions. From these, I form a second layer of polynomially many functions, each of which is a product of two functions from the first layer. Then for the third layer I take sums of functions from the second layer, and so on. I can keep this up for $\log_2k$ layers before I will start getting polynomials of degree $k.$

My question now is this. If I do that randomly, then do I get a polynomial $p(x)$ that is random enough for the corresponding phase function $(-1)^{p(x)}$ to have a small $U^k$ norm? What we’ve done is sufficiently linear that it’s not even obvious that its $U^2$ norm will be all that small.

😐 That at least I can answer. If you let your first layer consist just of the basic functions, your second layer consist of a random collection of products of basic functions, and your third layer be the sum of all those products, then you have a random quadratic, and I thought you said that random quadratic phase functions had tiny $U^2$ norm.

🙂 Oh yes, sorry. So we can be pretty certain that the random polynomials I’ve just constructed will have almost minimal $U^d$ norm for all bounded $d.$ But what happens when $d$ gets to $k=\log n$? I can see a problem arising at the last layer. There we would be wanting to take the sum of a whole lot of functions, each of which would typically be a product of two polynomials of degree $k/2$. I don’t know, but it sounds to me as though such a polynomial might be rather “simple” and “of low rank”. And it might be that you had to add together a superpolynomial number of “low-rank” polynomials to get a “high-rank” one.

😐 I’m a bit confused here. Ultimately what you want to prove is that all functions of polynomial complexity have large $U^k$ norms (and even small $U^k$ dual norms). In order to test this hypothesis you are attempting to find a counterexample. And in order to do that you are going to a lot of effort to ensure that your example is a polynomial of low degree. But why bother? All you need is a counterexample. Why not just take a random function of complexity $m$?

🙂 It’s because that would result in a mere rephrasing of the question. It seems almost certain that either the hypothesis is true or a random function of complexity $m$ is a counterexample to it. But I don’t know how to argue that random functions of complexity $m$ are so random that even the $U^k$ norm fails to detect any nonrandomness. So instead of looking for a generic counterexample I am looking for the simplest one. And that is why I am restricting my attention to polynomials of degree at most $k.$ If there seem to be reasons for such an example not to exist, it may give us some kind of hint about why the hypothesis could after all be true.

8) OK, I think we can all agree that this problem doesn’t look completely straightforward. But still, it seems possible that somebody will have a clever idea for producing such a polynomial — indeed, your random polynomial may even be such an idea — and if they do then your $U^k$ dual proposal is destroyed instantly.

🙂 I admit that. But it looks to me like a nice problem, unless there’s some construction that computer scientists already know about, in which case I can’t really think of any consolation, other than the weak one that I will have learnt something.

8) If it failed for that reason, then perhaps you could analyse the failure and come up with a new barrier to proving complexity lower bounds.

🙂 I suppose that would be quite nice if it could be done.

😐 I’ve thought of another way of producing randomish polynomials of degree $k$ in $n$ variables. Perhaps it might work.

🙂 Uh oh. What is it?

😐 I can think of many variants, but I’ll choose one arbitrarily. Pick some $m$ that’s at most polynomially large in $n$ and choose a random function $\phi:\{1,2,\dots,m\}^2\rightarrow\{1,2,\dots,n\}.$ I’m going for a function of polynomial circuit complexity, but if I wanted it to be in P I could replace “random” by “pseudorandom” there.

Now, given a Boolean sequence $x=(x_1,\dots,x_n)$, form the $m\times m$ matrix $A(x)=(a_{ij}),$ where $a_{ij}=x_{\phi(i,j)}.$ In other words, fill up the matrix with the values taken by the sequence $x.$ At this point one could just take the determinant, which would be a polynomial of degree $m,$ and I don’t see any reason for it to have a large $U^k$ norm. But you insist on a polynomial of degree $k,$ so we have to be slightly cleverer. What I suggest here is to calculate the characteristic polynomial of $A(x)$ and then the coefficient of $\lambda^{m-k}$ in that polynomial. That will be a polynomial of degree $k$ in the variables $x_1,\dots,x_n,$ and that is my proposed “random looking polynomial of degree $k$“.

🙂 Can we just think about how one calculates the characteristic polynomial in polynomial time?

😐 Well, it’s just the determinant of $\lambda-A(x),$ and calculating determinants can be done in polynomial time, by using row operations.

🙂 I’m happy with that when you’ve got a matrix of numbers, but it doesn’t seem quite so straightforward when you’ve got variables involved.

😐 Oh yes …

Right, I’ve done a search on the web, and it seems that there are polynomial time algorithms for calculating the characteristic polynomials of $01$ matrices over the reals (often known as “chemical graphs” in the literature). So one could just reduce mod 2.

🙂 Oh dear. If that’s right then it does indeed look like a pretty random polynomial of degree $k.$ I can’t think offhand of a reason that it ought to have “low rank”.

8) One way to think about that is to see exactly what it is. You put all your $x_i$s into an $m\times m$ matrix and then you sum up all the determinants of all the $k\times k$ submatrices, without worrying about signs since we’re working in $\mathbb{F}_2.$ Each determinant is itself a sum over all products of $k$ entries, where you pick exactly one from each row and each column. Since each product determines the $k\times k$ submatrix it has come from, the entire polynomial is the sum over all products of $k$ entries of the matrix that do not have two entries from the same row or the same column.

🙂 I have two remarks here. The first is that it’s not so obvious that the determinant has polynomial formula size, so perhaps there is still some possibility of using the $U^k$ dual norm as a useful formal complexity measure. The other, which I don’t think you will like, is that I can’t think how I’d go about estimating the $U^k$ norm of your “random-like polynomial”. So if I believe strongly enough that the $U^k$ norm of a function of polynomial circuit complexity must be large, then I can believe that the very fact that your polynomial is in fact computable in polynomial time implies that it has large $U^k$ norm.

8) You must be getting truly desperate to have said that.

🙂 I sort of am. But what I’m really saying is that if we don’t manage to come up with two Boolean functions $f$ and $g$ such that the $U^k$ dual norm of $f\vee g$ is quite large, given the $U^k$ dual norms of $f$ and $g$ (all this relative to the very fine scale that we must take, given that the norms of all Boolean functions are the same up to a constant), then I won’t feel I can completely rule out the existence of some inductive argument that shows that an explicit function has superpolynomial formula complexity. Who knows, it might even be the function that 😐 has just thought of.

8) You’ve switched back to formula complexity again. But earlier you were talking about circuit complexity. You clearly haven’t let go of your dream of proving that P$\ne$NP, but neither have you given the slightest reason to suppose that the $U^k$ norm of a function of low circuit complexity must be large. And 😐 has given us an example of a polynomially computable function that it’s very plausible to suppose has an almost minimal $U^k$ norm.

🙂 I almost agree with you. It’s just that I don’t see any strong arguments for whether :|’s function has a large $U^k$ norm or a small one. Perhaps the fact that determinants are used gives the function some special structure that causes it to have “low rank” in some sense. I feel as though more thought is needed before we accept this example.

In fact, here’s an argument that this determinant construction isn’t all that different from my random polynomials construction. Unfortunately, owing to the annoyances of characteristic 2, it only seems to work when $k$ is odd. But in that case recall that we are summing over a particular set of products of $k$-tuples of entries from the matrix, namely the ones that do not involve two entries from the same row or column. To evaluate that we could take each entry of the matrix in turn, remove its row and column, work out the corresponding degree-$(k-1)$ polynomial of the resulting $(m-1)\times(m-1)$ matrix, multiply it by the given entry, and add. This counts each $k$-tuple that we want to count $k$ times, which is fine if $k$ is odd.

That argument shows that the polynomial you have defined is a sum of $m^2$ polynomials that are “simple”, in the sense that they are products of a linear polynomial with a polynomial of degree $k-1$. So we’re back to the question we had earlier: in order for a degree-$k$ polynomial to have sufficiently high rank for its $U^k$ norm to be very small, is it enough to take a sum of only polynomially many “simple” polynomials? Given that $k$ depends on $n,$ I don’t think we can claim that the answer is obvious.

It may not be much, but we seem to have arrived at a purely mathematical question that would shed quite a lot of light on this whole approach (either demolishing it or giving quite a good heuristic reason in its favour, depending on whether or not a polynomial number of “simple” degree-$k$ polynomials can be considered as having high rank).

😐 I don’t know why you keep going on about this. My intuition tells me that you shouldn’t need more than $n$ simple polynomials to make a truly complex one.

🙂 Can you back that up?

😐 A little, as follows. Consider the following simple polynomial of degree $k$. I take two polynomials $p$ and $q$ of degree $k-1$ and I define $f(x)$ to be $p(x)$ if $x_1=0$ and $q(x)$ if $x_1=1.$ I can write $f(x)$ as $(1-x_1)p(x)+x_1q(x),$ so $f$ is a simplish polynomial of degree $k,$ according to your definition. Now let’s suppose I build random polynomials $f_i$ like that, one for each coordinate $i,$ and define $f(x)$ to be $f_1(x)+\dots+f_n(x).$ Then $f$ looks to me like a polynomial that’s “truly of degree $k$“. In particular, a $k$-dimensional subspace isn’t going to detect any unusual correlations, as far as I can see, because as you change coordinates you keep changing from one random degree-$(k-1)$ polynomial to another. And because we’ve got a simple polynomial for each coordinate, we can’t avoid these changes of coordinate. This isn’t a rigorous proof, but it convinces me for the time being.

🙂 Ah, but you haven’t said how to produce all those random polynomials of degree $k-1$. You can’t just iterate the procedure, because then you’ve got to build each of those polynomials out of $2n$ polynomials of degree $k-2,$ and so on, and the computational complexity of the eventual polynomial is $(2n)^k$ or something. So you have to recycle the lower-degree polynomials (as you clearly do in both my random-polynomials construction and your determinant one).

😐 Agreed, but all I was trying to criticize was your intuition that when $k$ is unbounded you need a superpolynomial number of simple polynomials to create one with small $U^k$ norm. If you want to prove that a polynomial of low complexity cannot have small $U^k$ norm, it is now clear that you can’t just look back one layer in the way it is constructed, but will have to argue from the entire construction, as you were starting to do just now. And that looks a lot harder.

🙂 Unless we could prove somehow that the $U^k$ dual norm was a good complexity measure. Then we’d be done by induction, for formula size at least.

By the way, a small change to my random-polynomials construction makes it look more like your determinant one. You build up layers as follows. If you’ve got a layer $j$ that consists of a bunch of polynomially many polynomials of degree $j,$ then you form a layer $j+1$ by taking polynomially many random sums of the form $q(x)=\sum_{i\in A_q}x_ip_{i,q}(x),$ where $A_q\subset\{1,2,\dots,n\}$ and each $p_{i,q}$ is a polynomial drawn from layer $j.$ The advantage of this is that it goes on for $k$ layers rather than $\log k$ layers, so it looks more random. In fact, it looks more random than your determinant construction, so I’m no longer sure that yours affects my perception of the chances that low-complexity functions have large $U^k$ norms.

By the way, I take your point about the lemma I was hoping for being highly likely to be false. But my point is that I still don’t find it clear whether we can build up an explicit degree-$k$ polynomial with almost minimal $U^k$ norm.

8) But that’s still the weakest-looking point of your approach in my view.

🙂 Quite possibly.

😐 I don’t know whether I agree. I’ve just done a bit of Googling and got led to a paper by Viola and Wigderson that contains a number of ideas that are quite close to the ideas we are discussing here. Of particular relevance is a theorem that exhibits a polynomially computable function that has low correlation with any degree-$d$ polynomial. But the bound that they get for the correlation is of the form $\exp(-\alpha n/2^d).$ Since functions with very small $U^{d+1}$ norm have very small correlation with degree-$d$ polynomials …

🙂 How did you know that? It’s true, but you seem to have picked it up very quickly.

😐 A form of telepathy. Anyway, what I’m saying is that if the result of Viola and Wigderson is state of the art (as it may well be given that it was published in 2008), then it suggests that finding an example to demonstrate that your approach doesn’t work may be a challenging problem, even if it doesn’t work.

8) I wouldn’t celebrate just yet. It suggests to me that getting the approach to work could be a very challenging problem even if it does work.

🙂 I don’t know whether you have any grounds for saying that, but it is obviously an important issue. Let’s suppose that it really is true that the $U^k$ dual norm is small for Boolean functions of low complexity — and as 😐 has pointed out, there is probably no example known that contradicts this.

8) I have to admit that that is a point in your proposal’s favour.

🙂 And let’s suppose also that there exists some function in NP has a large $U^k$ dual norm. There still remains the question of whether proving these two facts is any easier than proving that P$\ne$NP.

🙂 How can it be easier if it actually implies that P$\ne$NP?

🙂 Oh dear, that’s one of those philosophical questions that keeps coming up. But this one has an answer, which, if you believe that P$\ne$NP, or even if you don’t know how to prove that P=NP, you have to take seriously. If you want to prove that A implies C, it may be that there exists a statement B such that A implies B easily and B implies C easily, but it may also be that it is hard to think of statement B. (What I mean about P and NP is that it’s easy to see that B works when you’re told it, so what I’m saying doesn’t make sense if P=NP.)

When one is trying to prove that A implies C, one often tries to find a statement B that will have this nice property. If you have some candidate for B, then one obvious thing that can go wrong is that either A doesn’t imply B or B doesn’t imply C. But another thing that can go wrong is that B so obviously implies C that proving that A implies B is no easier than proving that A implies C. So my question is whether, if it is true that the $U^k$ dual norm of every low-complexity function is small, this is easier than proving that P$\ne$NP or whether it’s typical of the kinds of problems that are already known to be excruciatingly difficult.

One reason to suspect the latter is that it deals, implicitly at least, with polynomials of degree $\log n$, and that seems to be the point at which people don’t know how to prove anything. But then again, we wouldn’t be trying to improve the result of Viola and Wigderson: we’d be hoping that it couldn’t be improved! And perhaps if we thought hard enough about the $U^k$ dual norm we’d be able to say something interesting about the norms of $f\vee g$ and $f\wedge g.$ There seems to me to be at least a chance, if a slim one, that this property is an intermediate property of the kind one wants — not something that makes the whole problem easy, but at least something that splits it into two parts that are strictly easier than the original problem.

This entry was posted on October 2, 2009 at 10:05 am and is filed under complexity. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.