Thursday, February 12, 2004
Journal of Algorithms Editorial Board Bolts to New ACM Journal
Michael Nielsen has a
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.
- This move is not without precedent. For example the board of the
Learning (published by Kluwer) resigned en
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
- 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
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
Define the set MIN as the set of indices i such that for all j<i,
fi≠fj. How hard is the set MIN?
- fi(x) halts and fj(x) does not halt, or
- fj(x) halts and fi(x) does not halt or
- both fi(x) and fj(x) halt and
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,
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.