Skip to content

Happy Fiftieth Birthday FOCS

October 18, 2009


A look back at some the early days of the FOCS conference

images-2

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 {{50}^{th}} 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 images-3the 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.

images

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 {n^{3}}: 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

Some Observations

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:
Picture 1

SWAT 1971

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.

{\bullet } Matching: This is the famous paper of John Hopcroft and Richard Karp called: A {n^{5/2}} Algorithm For Maximum Matching In Bipartite Graphs. The special symbols in this and other papers were written in by hand: in the abstract the { \sqrt {}} symbol was left out and the running time was claimed to be order {(m+n) \quad n \quad } instead of {(m+n)\sqrt n}: note the extra space around the last {n}. The things we had to do before \TeX.

{\bullet } 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.”

{\bullet } 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.

{\bullet } 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.

{\bullet } 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.

Open Problems

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:

  1. Cryptography Without Assumptions: by Alice Brown, Bob Green, John Lime, Hila Mustard, Lincoln Violet, Chuck Yellow, {\dots}
  2. An { \sqrt n (\log n /\log\log\log n)^{3.1 + \epsilon}} Space {2 + \epsilon} Approximation Algorithm in the River-Streaming Model for the iBrain Optimization Problem: by Carol Smith and Fred Thomas;
  3. 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?

14 Comments leave one →
  1. October 18, 2009 3:31 pm

    I will offer contributions under two headings.

    (1) A 2019 FOCS article that proves what everyone already ‘knows’: Simulating noisy quantum systems is generically in the same computational complexity class as simulating classical systems (with the key caveat that external supplies of abscissa bits are not allowed … and thus no quantum error correction … so that Shor’s algorithm can’t be simulated).

    (2) A 2029 FOCS articles that proves what no one ever dreamed (much tougher!): M-Theory is the unique causally separable, relativistically invariant quantum field theory that can be simulated with classical computational resources (but heck … please don’t ask me to envision what that M-theory might look like).

    These two predictions follow from a heuristic argument by Bennett, Leung, Smith, and Smolin (arXiv:0908.3023) that the universe avoids “computational extravagance.”

    • rjlipton permalink*
      October 18, 2009 4:18 pm

      Love these, better than mine.

  2. vips permalink
    October 18, 2009 9:58 pm

    Cool post. I would also be interesting in knowing how the research culture in TCS (or CS in general) has changed over the years. And for the better or the worse?

    • rjlipton permalink*
      October 19, 2009 1:07 pm

      The field is larger. While the conference is larger, the field has probably grown much faster. The results is: parallel sessions, lots more people that do not know each other, lots more topics that many are not expert in, more competition for slots for papers, and generally a less close knit community. But all these are natural parts of the growth of the field.

      • vips permalink
        October 19, 2009 9:34 pm

        Thanks. If you feel appropriate, this is potentially a question for a full blog post which I am sure many young researchers like me would love to read. For example I remember you saying somewhere that in earlier days, there was more intersection between theory and practice with theorists regularly attending and publishing in systems venues.

  3. October 19, 2009 12:13 am

    How many FOCS have you attended?

    How old are you Lipton?

    • rjlipton permalink*
      October 19, 2009 1:03 pm

      I attended many many of these. I believe first was the 1974 FOCS.

    • October 19, 2009 1:52 pm

      A: some politeness please?

  4. October 19, 2009 9:53 pm

    My candidates
    (please note that I intend these just as a joke)

    ‘A proof for P = NP’ for 2019′ by Percy Heawood
    and
    ‘An error in 2019’s P = NP proof’ by Alfred Kempe

    (After all, let Kempe have his revenge on Heawood!
    I request complexity theorists and mathematicians to take above remarks as a joke which is what it is)

    • October 19, 2009 9:55 pm

      I missed the year of hypothetical paper by Kempe. Assume it to be 2029

  5. November 15, 2009 10:32 pm

    Hey everyone just wanna say hello and introduce myself!

  6. Paul Beame permalink
    March 11, 2010 11:07 pm

    One correction: The FOCS fox logo was not created by Emily Friedman. The logo was created for the 26th FOCS in Portland by the staff at the University of Oregon. A life-like silver fox was part of the logo for the 25th (Silver Anniversary) FOCS in 1984. Here is a slightly edited note from Gene Luks who was local arrangements chair for FOCS 1985:

    Hi Paul:

    I can enlighten you as to when and where it was designed but not
    the specific artist. It was done in 1985 by a staff member at the
    University of Oregon publications office.

    It had been left to me, as local organizer, to have the program
    published here. There had previously been a sketch of a fox,
    full-bodied and somewhat realistic, on the FOCS program
    …. the year earlier. But my thought,
    as long as it was legitimate to associate a “fox” with “FOCS”, we
    could have more of a logo for the meeting and I suggested as
    much in contracting for the printing job. Not everyone at UO
    thought the design was identifiable as a fox, but I figured FOCS
    folk would make the connection, … after the year earlier,
    and it spruced up the front of the program. (The back had
    a Portland skyline I think.) We made a point of using the image
    for other things at the Portland FOCS, e.g., nametags, folders,
    postings around the hotel, etc. I never proposed the logo for
    continued use, but was surprised and pleased to see it copied in
    subsequent years.

    It’s possible that there is some record or memory of who actually did
    the design but it would take some tracing — the duties of that
    office were split up between designers and printers, and the latter
    is not even located on campus. I’m not even sure if it was just
    one individual responsible for the design and it may even have been
    a student intern.

    – Gene

Trackbacks

  1. Giving Some Thanks Around the Globe « Gödel’s Lost Letter and P=NP
  2. Two Bits About FOCS 2013 | Gödel's Lost Letter and P=NP

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s