cthombor@luke.d.umn.edu (Clark Thomborson) (12/10/90)
At the last FOCS conference, I offered to try to set up a newsgroup for
the purpose of posting abstracts of papers accepted into FOCS and STOC.
The idea is that, after preparing a final draft for publication, an author
will post the finalized title and abstract in this public place, as a
service to the theory community. I don't think this group should be
moderated.
I realize we could use comp.theory for this purpose, but I for one am
unwilling to wade through all the random questions, claims, and flames
in that discussion group in order to find notices and brief descriptions
of "solid" results.
However, at the risk of diluting the utility of the new group, I propose
we expand the charter of the group to include notice of any article
or tech report that is "in press" or recently published, if that article
falls within the STOC/FOCS domain of interest. Notices of journal articles
are especially germane here, I would say, if they are the "finalized" version
of a STOC or FOCS paper. We would thus have a straightforward mechanism for
continuing David Johnson's bibliographic project.
Note that one should only post to comp.theory.abstracts AFTER a final
draft has been submitted for publication.
Postings to this group should follow a standard bibliographic format
(preferably LaTex, but refer and Scribe formats would be acceptable).
This will save a bit of typing whenever someone is able to cut-and-paste
into their bibliographic database.
Postings should also clearly indicate whether the author is willing to
supply preprints. The NOTE field of a LaTex bibliographic would seem
an appropriate place to put access information as well as an indication
of whether this article is a "later" version of a previously-published
article.
I'd suggest using LaTex's ANNOTE field for abstracts.
Here, then, is a possible posting to comp.theory.abstracts:
___________________________________________________________________
Subject: FOCS-31 paper, "Asymptotically Tight Bounds For Computing with
Faulty Arrays of Processors (Extended Abstract)"
@inproceedings{KKLM90,
AUTHOR = "C. Kaklamanis and
A. R. Karlin and
F. T. Leighton and
V. Milenkovic and
P. Raghavan and
S. Rao and
C. Thomborson and
A. Tsantilas",
TITLE = "Asymptotically Tight Bounds For Computing with
Faulty Arrays of Processors (Extended Abstract)",
BOOKTITLE = FOCS-31,
YEAR = 1990,
NOTE = "Preprints of this article may be obtained by sending email
prior to October 7, 1990 to cthombor@cs-gw.d.umn.edu. After this
date, please make your own copy from the published proceedings.",
ANNOTE = "In the paper, we analyze the computational power of 2- and
3-dimensional processor arrays that contain a potentially large number
of faults. We consider both a random and a worst-case fault model,
and we prove that in either scenario, low-dimensional arrays are
surprisingly fault-tolerant. For example, we show how to emulate an
$n \sqrt{\log{n}} \times n \sqrt{\log{n}}$ fault-free array on an
$n \times n$ array containing $\Theta(n^2)$ random faults with slowdown
$O(\log n)$, the same slowdown that is used by a fault-free $n \times n$
array to perform the simulation. We also show how to route, sort, and
perform systolic algorithms for problems such as matrix multiplication in
optimal time on faulty arrays. In many cases, the running time is the
same as if there were no faults in the array (up to constant factors).
On the negative side, we show that any constant congestion embedding
of an $n \times n$ fault-free array on an $n \times n$ array with
$\Theta(n^2)$ random faults (or $\Theta(\log n)$ worst-case faults)
requires dilation $\Theta (\log n)$. For 3-d arrays, we use knot
theory to prove that the required dilation is $\Theta(\sqrt{\log n})$."
}