Rating FOCS 1973
Can we rate the research topics from 1973?
Janos Simon is one of Juris Hartmanis’ illustrious students. He did not have a paper in FOCS 1973, but did have one with Juris at FOCS 1974, which went into his PhD thesis in 1975. He has been a mainstay of the University of Chicago Computer Science Department ever since. He posed a very interesting question as a comment in our recent discussion on FOCS 2013.
Today I am going out on a limb, taking a chance, potentially losing, all because of his question about FOCS 1973.
The question is:
- How many of the “open problems” mentioned in these papers are still interesting?
- If you had an answer, which of them would be accepted at FOCS 2014? (to even the playing field, assume that the answer is nontrivial and technically not uninteresting).
I decided to raise my attempted “answer” from a comment to this short discussion. But I am changing the question. I looked at the papers, selected the main topics that are there, and rated those. The rating is meant to reflect how relevant and important the areas are still today. So first here are some papers from the FOCS 1973 list again, and then the “star” rating of their importance today. This is a really a quick analysis and please take it as such.
Janos’ paper with Juris, incidentally, showed a case where something like is true. They considered ordinary assembly language (formally, random-access machines) in which multiplication is counted as a unit-time instruction, even if the numbers produced are exponentially large. They also allowed probing individual bits, which in assembly could be handled by a “left-shift ” instruction, where is a number in binary notation that could be large. Their model is now called MRAM for RAM with multiplication. They showed that both nondeterministic and deterministic polynomial time for MRAMs are equal to deterministic polynomial space for ordinary RAMs and Turing machines. Incidentally this also means that the results of the large multiplications can be probed without the whole value having to be explicitly stored, and the techniques were later relevant to parallel machine models.
Go to this to see the full list of the papers from FOCS 1973. Or here is a wordle:
This wordle does reveal some patterns—that is what they are for. Note that “LR” is prominent, as is “grammar”—in 1973 much of theory was about parsing and the theory of formal languages. Also lurking in the background are several words that concern real circuits: I cannot recall what all of them mean, but they were key research topics back then.
I will try and list some of the main topics, and then comment on whether we are still interested in these topics. I apologize to all those who I left out and to all those I include. Please all take this with a very large—small?—grain of salt.
Pattern Matching Algorithms: We have Karp-Rabin now, but I think pattern matching in the wide sense is still a core area. Any advance is always exciting.
Recursion Schemes: This area was very hot in the 1970’s, but has turned out to be less interesting than originally thought. The work done was interesting, deep, but the promise of the area did not quite work out as hoped.
On Lower Bounds in comparison models: Still a very core area: we would love to have better understanding of even this simple restricted model.
Statistical Indicators of Optimality: The area is of local search type algorithms. It is one of the key mysteries of theory that we so poorly understand this type of algorithm. I would say any advance is very welcome still.
Evaluation of a Set of -Linear Forms: This is all about tensor rank and is therefore still a core area. It is very hard, and there are many problems that remain open.
Nondeterministic Time and Space Hierarchies: This area is still one that we do not fully understanding. There are plenty of open problems especially concerning nondeterministic time.
On Tape-Bounded Complexity Classes: Many problems remain, but the fine level that was being studied then is less core these days.
Computable Functions: A huge area, of great importance still. But it has moved to other parts of the world. We are mostly interested in functions that are much lower in the complexity hierarchy. So this is not a core area any more.
Inductive Inference: A huge area. Perhaps the work done was ahead of its time. Redefined today as learning theory, it is core and has its own conferences too.
Still Open Problems
I looked at several of the papers in detail, and found that some of the explicit open problems remained open for some time. One, which struck me as the most important one at least from my own research standpoint, was the tensor rank problem. This is the problem, given a tensor which is an box of numbers, find the minimum such that can be written as a sum of -many rank-1 boxes. A rank-1 box is the outer product of ordinary -vectors such that the number in box position is .
In two dimensions this is matrix rank which, of course, is in polynomial time via Gaussian elimination, but Johan Håstad proved in 1990 showed that this is -hard already in three dimensions, and the associated decision problem is -complete for finite fields. This is another case where 2 is easy but 3 is hard. Other questions in this area have been resolved in a recently-updated paper by Christopher Hillar and Lek-Heng Lim. They have a nice quote:
Bernd Sturmfels once made the remark to us that “All interesting problems are NP- hard.” In light of this, we would like to view our article as evidence that most tensor problems are interesting.
Looking over the problems that to my knowledge are still open, I’ve selected two:
- An open problem on the power of nondeterministic time: Is
Here means proper subset. In a way this is really about: how much can we sharpen the techniques of diagonalization?
- An open problem on tensor ranking: Is there an algorithm to find the rank of tensors over the rationals? Given Håstad’s result “algorithm” means any algorithm, or if you like “is it even decidable?”
I believe that any paper that made progress on either of these questions, for example, would have an excellent chance to be accepted. I certainly, if on the program committee, would argue strongly for such papers.
Do you agree with my quick estimate here?