Two Bits About FOCS 2013

John Cherniavsky is a theorist who published a paper in FOCS 1973, forty years ago. He has done much great work at NSF, and is currently the senior science advisor for research in the education directorate at NSF. The full name of his directorate is the Division of Research on Learning in Formal and Informal Settings. More on his paper and his work in a moment, but first a public announcement about one of our formal settings that also promotes informal research contact.

Today Ken and I want to remind you about the upcoming FOCS 2013, and look back at FOCS 1973.

In looking back 40 not 50 years, we remember that Alvy Smith, who went on to co-found Pixar, created the proceedings cover design after being asked to help at the 1973 conference. See here for a discussion about that.

The Two Bits

We have been asked to help get two bits out to you:

1. The deadline for early registration and hotel reservation is approaching. It is October 4, see this for details.

2. There are opportunities for student travel support to FOCS: here.

The conference is Oct. 27–29 in Berkeley, as usual also with workshops on Saturday, Oct. 26. For those who cannot attend, or wish to get a feel for the conference ahead of time, here is a Wordle:

The term “two bits” is an old term for twenty-five cents. It is used primarily in the United States, but originally referred to the Spanish dollar which was divisible into “pieces of eight.” According to Wikipedia, two bits is also used for:

• Two Bit Monsters, a 1980 album by American singer-songwriter John Hiatt.

• Two Bits, a 1995 American dramatic film.

• Two Bits Man, an unidentified author of the humor and college commentary column “Two Bits” in The Technique, the student newspaper of Georgia Tech.

Our two bits should help many of you save more than two bits. Does that make sense? Does that make cents?

FOCS 1973

This is what was happening back in 1973 at the 14th Annual Symposium on Foundations of Computer Science, at Iowa City on October 15-17, 1973. At the time the conference was still called “Switching and Automata Theory” (SWAT). The dates, however, were much the same as now. Note also the use of the terms “extended abstract” or “preliminary version.” These were used to protect the ability to submit the paper to a journal. The paper titles cover some long-familiar subjects but are missing some others. Notably, there is no hint of ‘approximation’ in any title below.

We note that John’s paper was right on target given the year. He showed that non-classical logics have the same completeness properties as classical propositional logic, as had been isolated by Steve Cook in the 1971 STOC conference. Here is his abstract:

Decision procedures for validity in intuitionistic propositional calculus and modal propositional calculus are given which require a running time proportional to a polynomial in the length of the formula on a nondeterministic Turing machine. Using a theorem of Cook’s and well-known transformations from intuitionistic to classical and modal to intuitionistic logics, the validity problem for intuitionistic and modal logics is shown to be polynomial equivalent to the validity problem for classical logic.

Here is the full list of the papers from 1973:

• Peter Weiner: Linear Pattern Matching Algorithms.

• Tiko Kameda, Shunichi Toida: Efficient Algorithms for Determining an Extremal Tree of a Graph (Extended Abstract).

• Ashok Chandra: Efficient Compilation of Linear Recursive Programs.

• Emily Friedman: Equivalence Problems in Monadic Recursion Schemes.

• Jean-Marie Cadiou, Jean-Jacques Lévy: Mechanizable Proofs about Parallel Processes.

• Charles Baugh: Chow Parameters in Pseudothreshold Logic.

• Jon Bredeson: On Multiple Input Change Hazard-Free Combinatorial Switching Circuits without Feedback.

• Henry Chuang, Santanu Das: Multiple-Input Change Asynchronous Machines Using Controlled Excitation and Flip-Flops.

• Vaughan Pratt, Frances Yao: On Lower Bounds for Computing the -th Largest Element.

• Philip Spira, Victor Pan: On Finding and Updating Shortest Paths and Spanning Trees.

• Sam Savage: Statistical Indicators of Optimality.

• David Dobkin: On the Optimal Evaluation of a Set of -Linear Forms.

• Matthew Geller, Michael Harrison: Characterizations of LR(0) Languages (Extended Abstract).

• Dennis Mickunas, Victor Schneider: On the Ability to Cover LR(k) Grammars with LR(1), SLR(1), and (1,1) Bounded-Context Grammars.

• Thomas Szymanski, John Williams: Non-Canonical Parsing.

• Joel Seiferas, Michael Fischer, Albert Meyer: Refinements of the Nondeterministic Time and Space Hierarchies.

• Ivan Sudborough: On Tape-Bounded Complexity Classes and Multi-Head Finite Automata.

• William Rounds: Complexity of Recognition in Intermediate-Level Languages.

• William Joyner: Automatic Theorem-Proving and the Decision Problem.

• Hartmut Ehrig, Michael Pfender, Hans Jürgen Schneider: Graph-Grammars: An Algebraic Approach.

• Michael Machtey: A Notion of Helping and Pseudo-Complementation in Lattices of Honest Subrecursive Classes.

• Kurt Mehlhorn: On the Size of Sets of Computable Functions.

• Paul Young: Optimization among Provably Equivalent Programs (Preliminary Abstract).

• Lenore Blum, Manuel Blum: Inductive Inference: A Recursion Theoretic Approach.

• John Cherniavsky: The Complexity of Some Non-Classical Logics.

Open Problems

Hope you get to FOCS 2013 and are able to attend FOCS 2053 too. Ken, however, is occupied with travel 3,000 miles east instead, in meetings of the joint committee of the World Chess Federation and the Association of Chess Professionals in Paris and Tallinn. So he will not be there; instead he will be working on how to stop cheating in chess, and promoting the larger science of his chess project such as this ongoing study of human-computer teams.