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 
The Papers
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.
The Topics
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.
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 
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 
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.
Open Problems
Do you agree with my quick estimate here?
I recently asked on TCS Stack Exchange about the complexity of computing tensor rank over infinite fields. In agreement with your post, the case for the rationals seems open.
http://cstheory.stackexchange.com/questions/7903/complexity-of-tensor-rank-over-an-infinite-field
About 14 hours from now — barring surprise MathOverflow comments/answers — Princeton graduate student Will Sawin will earn a 250-point MathOverflow bounty for his answer to my question: What is the “tangle” at the heart of quantum simulation?
Answer: The “tangle” is the composition of the protean mathematical manifestations of tensor rank.
Consider for example the basic notion of smoothness (as manifest for example tensor-product varieties). How many pages do textbooks require, to introduce the notion of smoothness with a reasonable balance of naturality and rigor?
• Back in 1968, John Milnor needed three pages … in his lucid and much-cited monograph Singular Points of Complex Hypersurfaces.
• Nowadays Ravi Vakil needs 321 pages … in his justly praised, often-hilarious, free-as-in-freedom monograph Foundations of Algebraic Geometry (which is highly recommended).
Open Questions: Has our 21st century appreciation of “smoothness” become hundreds of times more sophisticated since 1968? Should we pity modern-day undergraduate students, who read the Feynman Lectures and fondly imagine that dynamical “tangles” are simple? How can we sustain undergraduate enthusiasm, while imparting a more realistic appreciation of 21st century mathematical realities, all within a too-short (or is it?) four-year degree-granting time-span that is tightly constrained by too-rigid (?) and/or over-full (?) academic/ABET requirements?
The professoriate is confused, conflicted, and divided by these tough questions (needless to say). Heck *everyone* is confused by them … and this affords a wonderful opportunity for students to think for themselves. Good!
As a follow-up, Princeton graduate student Will Sawin did post the best answer to the MathOverflow question What is the “tangle” at the heart of quantum simulation?. Sawin’s answer is partial, for the excellent reason that the “tangle” has a tensor-product nature, and we are (at present) very far from appreciating the confluence of arithmetic, algebraic, combinatoric, computational, informatic, analytic, metric, and symplectic (whew!) aspects of tensor products.
Conclusion The foundational role of tensor-products in computer science was a key theme of FOCS 1973, and is today a key theme of FOCS 2013, and bids fair to be a key theme of FOCS 2053 … and in the event that humanity avoids various historical singularities both good and ill, perhaps even FOCS 2103. 🙂
I previously asked on TCS Stack Exchange about computing tensor rank over an infinite field. Over the reals, an upper bound is PSPACE but we couldn’t find an upper bound over the rationals.
http://cstheory.stackexchange.com/questions/7903/complexity-of-tensor-rank-over-an-infinite-field
One may notice that RV’s Foundations of Algebraic Geometry has grown to 764 pages as of the end of the past academic year. If JS’s metric is accepted, one might detect an analog of Moore’s law at work in the knowledge business.
Other metrics could be considered; for instance, a more humbling metric, at 7.3 megabytes, the contents are still significantly less than a typical Youtube upload.
The highly rated wiki-answer to the MathOverflow question “Best Algebraic Geometry text book?” lists sufficiently many & sufficiently varied AG textbooks, as to suggest that writing an AG textbook is (for many folks) a surer path to knowledge than reading one. Ouch!
Could you please elaborate more/to be more specific on open questions in pattern matching? Or a pointer to current state of the art algorithms. Thanks.
I previously asked on TCS Stack Exchange about the complexity of computing tensor rank over infinite fields. For the reals, it seems the problem is in PSPACE, but for the rationals, no upper bound was given.
http://cstheory.stackexchange.com/questions/7903/complexity-of-tensor-rank-over-an-infinite-field
That is a fine comment Tyson Williams.
It’s empirically evident that computational problems of the form “rank-estimation and model-order reduction of tensor product representations” belong to that burgeoning class of problems that are formally NP-hard yet in practice are generically PTIME.
The prototype of these hard-yet-easy problems is of course SAT, whose rapid progress is widely appreciated:
That is why (as it seems to me) Dick Lipton and Ken Regan are well-advised to emphasize an enduring theme of Gödel’s Lost Letter, that the still-mysterious formal complexity of practical problems is intimately related to their also-mysterious empirical simplicity.
By the end of the 21st century, will computer scientists still understand nothing (in a formally rigorous sense) while efficiently finding good answers to “impossible” problems (in a practical problem-solving sense)? That is a Faustian bargain that many mathematicians would reject, yet many engineers would accept gladly! 🙂
As a further reference, this week’s arxiv preprint by Clare Horsman, Susan Stepney, Rob C. Wagner, and Viv Kendon, titled “When does a physical system compute?” (arXiv:1309.7979 [cs.ET]) delightfully explores the many nuanced and subtle (as they seem to me) complexity-theoretic implications that are naturally associated to open, practical computational questions like “When do BosonSampling trajectories have accurate P-rank tensor product representations?” Future FOCS meetings — and no doubt future GLL columns too — will be exploring these tough questions for a considerable time to come.