# Computational Complexity

### Thursday, February 12, 2004

Journal of Algorithms Editorial Board Bolts to New ACM Journal

Michael Nielsen has a post linking to a post linking to a post noting that the editorial board of the Journal of Algorithms (published by Elsevier) resigned en masse to start a new journal Transactions on Algorithms to be published by ACM.

I won't rehash all of these posts but let me make two points.

1. This move is not without precedent. For example the board of the journal Machine Learning (published by Kluwer) resigned en masse a few years ago to start the online Journal of Machine Learning Research. If publishers like Kluwer and Elsevier continue with their current pricing policies we will continue to see defections. Note though that Kluwer has managed to keep Machine Learning active.
2. From Felten: Computer scientists are lucky, in that most of our best journals and conference proceedings are published by our professional societies at reasonable prices and terms. This is true for American conferences, most non-American theory conferences use Springer's LNCS series. For journals, the professional societies (ACM, IEEE Computer Society, SIAM) publish only a small fraction of computer science journals. While many of the best theory papers go to the Journal of the ACM, Transactions on Algorithms will be ACM's first journal devoted to papers in theoretical computer science.

### Tuesday, February 10, 2004

Minimal Indices

Let's look at some interesting questions about the set of smallest programs. This post relates more to recursion theory than complexity theory. No time bounds today.

Let f1, f2, ... be an enumeration of the partial recursive functions. We say fi≠fj if there is some input x such that either

1. fi(x) halts and fj(x) does not halt, or
2. fj(x) halts and fi(x) does not halt or
3. both fi(x) and fj(x) halt and fi(x)≠fj(x).
Define the set MIN as the set of indices i such that for all j<i, fi≠fj. How hard is the set MIN?

MIN is in Σ2 of the arithmetic hierarchy. For all j<i you need to check that for some input x, one of the three conditions above hold (which might require a ∀ to check that a machine does not halt). We have two unbounded quantifiers (the first "for all" is bounded) so MIN is in Σ2.

In fact this is tight for Turing reductions, every problem in Σ2 reduces to MIN.

For an interesting open question we turn to a variation called MIN*. We say fi*fj if one of the three conditions above hold for infinitely many x. MIN* contains the set of indices i such that for all j<i, fi*fj.

Without too much effort one can show MIN* is in Π3. Marcus Schaefer shows that every language in Π3 can be Turing reduces to an oracle that encodes both MIN* and K where K is the usual halting problem. We would like to remove K which is equivalent to the following open question

Does K Turing reduce to MIN*?

Read Schaefer's paper for details and many more interesting facts about MIN and MIN*.

### Monday, February 09, 2004

The MIT-Berkeley Axis

"I like everybody in this field" Berkeley professor Christos Papadimitriou said during his acceptance speech of the Knuth Award at the 2002 STOC conference. He paused and added "Even those not on the MIT-Berkeley axis whose papers usually do not get accepted into STOC and FOCS."

Papadimitriou was alluding to an earlier time, the 1980s, when indeed STOC and FOCS were dominated by papers (and program committee members) from MIT and Berkeley and those with strong connections with these institutions. When I attended grad school at MIT I grew to believe there was MIT theory and there was bad theory. Once I left MIT and moved off axis to Chicago I discovered whole beautiful areas of CS theory completely ignored during my MIT days.

The MIT-Berkeley axis still exists to some extent but has far less influence than two decades ago. The vagaries of the job market have forced MIT and Berkeley Ph.D.'s to spread out over a large variety of colleges and universities diluting the axis. Also the field has grown too large to be dominated by two institutions or two conferences.