Happy Fiftieth Birthday FOCS
A look back at some the early days of the FOCS conference
Alvy Ray Smith is a famous researcher who has won many awards for his seminal work in computer graphics. He is a theorist also: he has had several papers published at FOCS, for example.
Today I thought, since FOCS’s anniversary is soon, that it would be fun to look back at the first conferences and see what researchers were doing. Below is a singing tribute to FOCS:
The first observation is that they were not attending FOCS. The conference we call FOCS has been around for fifty years, but it has gone through two other names before becoming FOCS. The name was changed twice: In 1960 until 1965 it was the “Symposium on Switching Circuit Theory and Logical Design;” then, from 1966 to 1974 it was the “Symposium on Switching and Automata Theory;” and finally it switched to the “Foundations of Computer Science.” Hopefully, this is the last name, but who knows?
When the name was: Switching and Automata Theory, it had the “bad” abbreviation as SWAT. I recall the business meeting where we discussed changing the name to something better. I believe—I could be wrong—that Emily Friedman made two key contributions.
First, she suggested the name, FOCS, and also she helped design the “fox” logo. Emily was very active in the 1970’s and did some quite nice work on program schema and various aspects of language theory. Alvy Smith designed the famous cover that has used for years on the proceedings.
Speaking of covers of proceedings, when I was the program chair for STOC I was very excited about the honor. I especially liked the idea that the program chair got to select the color of the proceedings, since I thought this would be fun. Finally the big day came, we had selected the papers, the accept and reject letters had been sent, and it was time to pick the color for the cover. The print person at ACM called me to ask about my choice of colors. I told him that I wanted the cover to be black with white letters, which I thought would be dramatic and unique. He told me that he would select a color and hung up the phone—really. I did not get to choose. Oh well.
Let’s now turn to look at what the field was up to years ago.
Symposium on Switching Circuit Theory and Logical Design
Here are the papers from the 1963 conference:
- Infinite sequences and finite machines: Muller, David E.
- Two-sided finite-state transductions: by Elgot, C. C.; Mezei, J. E.
- On computability by certain classes of restricted turing machines: by Fischer, Patrick C.
- Bilateral threshold nets: by Frazer, W. D.
- Threshold gate realizations of logical functions with don’t cares: by Coates, C. L.; Lewis, P. M.
- On the analysis of functional symmetry: Arnold, R. F.; Lawler, E. L.
- The minimal synthesis of tree structures: by Lawler, E. L.
- Determining the best ordering of variables in cascade switching circuits: by Levien, Roger E.
- Sequential circuit synthesis using input delays: by Eichelberger, Edward B.
- Finite automata and badly timed elements: by McNaughton, Robert
- Demonstrating Hazards in sequential relay circuits: by Booth, Theodore M.
- Logical design theory of NOR gate networks with no complemented inputs: McCluskey, E. J.
- A survey of asynchronous logic: Comparing various definitions and models for asynchronous switching circuits: Miller, R. E.
Symposium on Switching and Automata Theory
Here are the papers from the 1966 conference:
- Context-free language processing in time : by Daniel Younger.
- Syntax directed transduction: by Lewis, P. M.; Stearns, R. E.
- Simple deterministic languages: by Korenjak, A. J.; Hopcroft, J. E
- One-way stack automata (Extended abstract): by Ginsburg, Seymour; Greibach, Sheila A.; Harrison, Michael A.
- Real-time computation by n-dimensional iterative arrays of finite-state machines: by Cole, Stephen N.
- The recognition problem for the set of perfect squares: by Cobham, Alan
- Roots of star events: by Brzozowski, J. A.
- Subdirect decompositions of transformation graphs: by Yoeli, M.; Ablow, C. M
- Pair algebra and its application: by Liu, C. L.
- Graphs of affine transformations, with applications to sequential circuits: by Gill, Arthur
- A method for the combined row-column reduction of flow tables: by Grasselli, A.; Luccio, F.
- Standard minimum transition time secondary assignments for asynchronous circuits: by Epley, Donald L.
- A row assignment for delay-free realizations of flow tables without essential hazards: by Unger, Stephen H.
- Synthesis of multiple sequential machines: by Smith, Edward J.; Kohavi, Zvi
- Realization of sequential machined with threshold elements: by Hadlock, F. O.; Coates, C. L
- Fast Simulation of Nondeterministic Turing Machines: by Reading, R. U.
- The application of threshold logic to the design of sequential machines: by Masters, Gilbert M.; Mattson, Richard L.
- Minimization and convexity in threshold logic: by Dertouzos, Michael L.; Fluhr, Zachary C.
- On minimal modulo 2 sums of products for switching functions: by Even, S.; Kohavi, I.; Paz, A
- Conjunctive encoding of Boolean matrices: by Stover, D. R.; Epley, D. L.
- Asynchronous propagation-limited logic: by Goldberg, J.; Stone, H. S.
- The synthesis of multipurpose logic devices: by King, W. Frank
- The universal logic block (ULB) and its application to logic design: by Forslund, D. C.
- Statistical properties of random digital sequences: by Booth, Taylor L.
- Reconsider the state minimization problem for stochastic finite state systems: by Ott, Gene H.
- An application of coding algebra to the design of a digital multiplexing system using linear sequential circuits: by Helm, H. A.
- Automorphism groups and quotients of strongly connected automata and monadic algebras: by Bayer, R.
- On the automorphism group of a reduced automaton: by Paul, Manfred
One issue that earlier researchers worried about was the copyright issue. You may see that papers are called “extended abstracts” or “preliminary version.” This was so that journals would allow the authors to publish a final version again. There were relatively few papers, and there were no parallel sessions.
The topics of course were of course different from what we think about today. Yet not too far from things that we are interested in today. It is very clear that exact results were the goal. I think almost no papers were about approximations—in any sense of the word. The field had not discovered that one way to make progress on hard problems was to lower the bar. Since getting the answer was often too hard, try to get an approximation. This lesson would not arrive for a few years.
The papers also just looked different, since they were typed not typeset. Take a look at some of them. You will see handwritten symbols:
Here are a few selected papers from the 1971 conference. You will notice that now the topics are very close to current ones. For example, in FOCS 2009 there is a paper by Nikhil Bansal and Ryan Williams that is on boolean matrix product, which is related to the Fischer and Meyer paper below.
Matching: This is the famous paper of John Hopcroft and Richard Karp called: A Algorithm For Maximum Matching In Bipartite Graphs. The special symbols in this and other papers were written in by hand: in the abstract the symbol was left out and the running time was claimed to be order instead of : note the extra space around the last . The things we had to do before .
DFS: This is the famous paper by Robert Tarjan, no Endre as he added later on, called: Depth-First Search And Linear Graph Algorithms. Tarjan used a special font on his typed papers that we could all tell was from Stanford. Note also he calls it a “working paper.”
Boolean Matrix Product: This is a neat paper by Mike Fischer and Albert Meyer called: Boolean Matrix Multiplication and Transitive Closure. In this paper they showed that fast matrix multiplication can be used to compute boolean matrix products: also they count bit operations not arithmetic operations.
Description Size: This is another neat paper by Mike and Albert, although this time it’s a “Meyer and Fischer” paper called: Economy of Description By Automata, Grammars, And Formal Systems. The main results show that more powerful devices can tremendously affect the size of the description of a set. For example, there is an exponential gap between deterministic finite state automata and non-deterministic automata; even more impressive there is a double exponential gap between deterministic finite automata and pushdown automata. I believe I was asked about this earlier and this is the place to look for such results.
Real Computation: This is a paper that perhaps should be better known. It is by Fred Abramson and is called: Effective Computation Over The Real Numbers. Fred extends Turing Machines to have values that are real numbers. This paper was probably a bit ahead of its time; I will discuss the real P=NP question of Lenore Blum, Michael Shub and Stephen Smale in the future.
I hope the FOCS meeting continues to be an important meeting for another fifty years and then fifty more. I do wonder what topics will be important for FOCS 2019 or FOCS 2029? Here are possible papers that could appear in the FOCS 2019:
- Cryptography Without Assumptions: by Alice Brown, Bob Green, John Lime, Hila Mustard, Lincoln Violet, Chuck Yellow,
- An Space Approximation Algorithm in the River-Streaming Model for the iBrain Optimization Problem: by Carol Smith and Fred Thomas;
- The Extended Generalized Riemann Hypothesis Implies The Scott Quantum Hierarchy Collapses: by Ryan Browodski and Sue Lin-Jun.
What do you think? What are your predictions?