Lower Bounds and Progressive Algorithms
A new class of algorithms and an approach to lower bounds
Robert Floyd was an early leader of computational theory, who made especially important contributions to the design of algorithms. He became a Turing Award winner in 1978 for this seminal work, which revolutionized our understanding of algorithms. Perhaps his most famous paper is his 1967 paper Assigning Meanings to Programs. It alone has nearly two thousand citations.
Today I want to talk about how hard it is to understand programs, and the consequences that has for lower bounds. This applies to the recent claimed proof of PNP, but goes beyond that to other attempts to understand how algorithms “work.”
I knew Floyd, and had many conversations with him over the years. His Wikipedia article says
“His hobbies included backgammon and hiking.”
I think this is misleading. Hiking may have been a hobby, but backgammon was much more than a hobby to Bob.
We once were stuck at the Chicago O’Hare airport for hours, waiting for our flight to leave, owing to a snow storm. As we sat at our gate, Bob asked me, in a casual manner, “do you know how to play backgammon?” I answered I knew the rules, but why did he want to know? Bob said since we had several hours to wait perhaps we should play a few games, for small stakes of course. He then reached into his briefcase and removed a backgammon set.
My Dad taught me many things. One was to be wary of anyone who suggests a game of pool for money, and then opens a black case and starts to screw together a pool stick. I figured that this advice generalized to anyone who traveled with their own backgammon set. I told Bob that I was not going to play for money, no way. He pushed a bit, but finally said fine. He proceeded instead to give me a free lesson in the art and science of playing backgammon.
I was right to pass on playing him for money—at any stakes. The lesson was fun. I found out later that for years he had been working on learning the game. He took playing backgammon very seriously, studied the game and its mathematics, and was a near professional. I think it was more than a hobby. Like his research, Bob took what he did seriously, and it is completely consistent that he would be terrific at backgammon.
Let’s turn now to understanding programs and lower bounds, and how this links to Floyd’s work.
Alice and Bob Try To Understand Programs
Bob’s seminal paper, “Assigning Meanings to Programs,” showed how, in principle, one could understand a program. His ideas, which are now a standard part of computer science, were to attach assertions to the program. These assertions then could be proved, and this would yield a proof that the program worked as claimed. This was a brilliant insight—perhaps more so since it seems so natural and simple today. But he did it over forty years ago.
The trouble with this insight is the following, which I will show using our friends Alice and Bob. Suppose Bob has a program that he has created. Perhaps it is a beautiful new algorithm for matrix product, or an algorithms for some other neat problem. Bob wants to convince Alice that his program works. One method would be to use the technology created by Floyd. Bob could add assertions to his program, and then walk Alice through a proof that the program solves the problem as he claims it does.
So far all sounds good. But, let’s change the situation a bit. Now Bob wants to give Alice his program, but he does not want her to be able to figure out how it works. In this case Alice has to figure out what Bob’s program does on her own. She knows what it is supposed to compute, but she has no idea how it is doing the computation. This is a much harder problem for Alice.
I claim that this is the crux of why proofs of lower bounds that try to analyze the behavior of programs are hard, or perhaps even impossible. Over the years we have seen a number of attempts at lower bounds—not just for PNP—that try to understand how programs work. Note, the problem they face is much harder than the problem Alice faced. In a lower bound proof one must understand how all possible programs work, whereas Alice only needed to understand how Bob’s program works. In a lower bound proof Alice must be able to show that all programs Bob can create either run too long or compute the wrong answer. This is an extremely difficult task.
I have thought about this issue of understanding programs, and the relationship it has to lower bound attempts. I have an initial idea of how to formalize the difficulty that Alice faces when she tries to understand Bob’s program.
Before I give a formal definition let me try to give the intuition behind the notion that I suggest we call progressive. Suppose Bob claims that he has a program that determines whether or not a graph has a -clique, and further that his algorithm runs much faster than brute force. Alice might try to argue that this is impossible as follows:
- Alice might assert that as Bob’s program runs it must make progress toward the goal of checking all possible sets of vertices to see if they form a clique.
- Alice then could argue there are lots of such sets of vertices, and this dooms the performance of Bob’s program.
This is a reasonable idea—I wanted to say “natural” but the above aligns only partially with the established meaning of that word in lower-bound proofs. Many algorithms do make progress in incremental steps. But, not all do this. Even the simple clique problem fails: For the case of triangle detection with , the best known algorithm uses fast matrix product, and does not “look” at the sets of all triples of vertices. It accumulates information about paths of lengths 1 and 2, and puts together this partial information only at the very end. Algorithms for higher extend this idea. In the above terms these algorithms using matrix product are not progressive.
A Formal Definition of Progressive
Here is an attempt at a formal definition of progressive. Let’s work with boolean circuits, but I think the ideas can be adapted to almost any computational model.
Consider a correlation measure on boolean functions: thus, the value of measures how “close” the function is to . There are many such measures and what we have to say makes sense for any of them. So let’s agree to fix such a measure. We normalize so that .
is a boolean computation for the function where . Then, define to be the value
The value measures the correlation between the step of the computation and the output of the computation. Note, two things: by the normalization and I have “overloaded” the symbol “.” I hope the latter causes no confusion, is a correlation measure and is a particular correlation.
The intuition is that if is small for all , then the computation is not progressive; if grows slowly toward , then the computation is progressive.
Ken Regan has suggested how to make the definition more comprehensive this way: Let us introduce a “referee” that represents a very simple function of all the partial results. Then the correlation measure becomes
Above we have the function that simply returns the last argument . Call this the “simple” referee .
Note that we can regard the inputs as the first gates of the circuit, with representing the function . This allows a more-general to see the input . However, we prevent itself from exploiting this to solve the problem, by fixing to be a simple function, or at least limiting to a class known to be much less powerful than the computations being analyzed. Note also that since returns just one bit, it cannot simply cheat by doing the actual computation. In all cases, stands for what can be “quickly digested” about the progress the computation has made through steps.
Conjectures About Progressive Computations
I have two separate conjectures about progressive algorithms. They are stated for the simple referee but can be extended to others.
Conjecture A: Suppose that is a boolean function with a circuit of size . Then, for any , there is another circuit of size that is polynomial in and that computes . Further, satisfies the condition that if is its step, then for
Conjecture B: Suppose that is a circuit of size for the -clique problem on vertex graphs. Assume for all ,
where is a constant. Then, grows at least where tends to infinity.
Conjecture A states that we can modify any computation so that it appears not to be making progress toward its goal, and that this property does not increase the computational cost too much. For those who wish to prove lower bounds this should be a worry. It says that computations can be very complex.
Conjecture B states that computations that do make progress, in our formal sense, can have provable lower bounds.
Of the two conjectures I believe that it should be possible to prove A, using known cryptography technology. I actually think it should be provable with much stronger notions of “progressive.” We should be able to show that even the values of many of the earlier steps of the computation do not yield much quickly-digested information about the final answer.
The second conjecture I think needs new ideas to be proved. My intuition is that if the information of each step correlates better and better with the final output, this should severely restrict the computation. This may be strong enough to prove nontrivial lower bounds.
Is this definition a reasonable one? Does it capture the intuitive notion of an algorithm working toward its goal? Can we answer the conjectures?
A final question is: can we prove that many actual algorithms are progressive? I would conjecture that many “real” algorithms are progressive—either in the exact sense defined here, or in some small variation.