Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 47 Issue 5, Sept. 2000

Editorial: a bill of rights and responsibilities
Joe Halpern
Pages: 823-825
DOI: 10.1145/355483.355484

Building tractable disjunctive constraints
David Cohen, Peter Jeavons, Peter Jonsson, Manolis Koubarakis
Pages: 826-853
DOI: 10.1145/355483.355485
Many combinatorial search problems can be expressed as 'constraint satisfaction problems'. This class of problems is known to be NP-hard in general, but a number of restricted constraint classes have been identified which ensure tractability....

A neuroidal architecture for cognitive computation
Leslie G. Valiant
Pages: 854-882
DOI: 10.1145/355483.355486
An architecture is described for designing systems that acquire and ma nipulate large amounts of unsystematized, or so-called commonsense, knowledge. Its aim is to exploit to the full those aspects of computational learning that are known to...

Silver exudation
Siu-Wing Cheng, Tamal K. Dey, Herbert Edelsbrunner, Michael A. Facello, Shang-Hua Teng
Pages: 883-904
DOI: 10.1145/355483.355487
A silver is a tetrahedon whose four vertices lie close to a plane and whose orthogonal projection to that plane is a convex quadrilateral with no short edge. Silvers are notoriously common in 3-dimensional Delaunay triangulations even for...

A lower bound on the average-case complexity of shellsort
Tao Jiang, Ming Li, Paul Vitányi
Pages: 905-911
DOI: 10.1145/355483.355488
We demonstrate an &Ohgr;(pn1+1/p ) lower bound on the average-case running time (uniform distribution) of p-pass Shellsort. This is the first nontrivial general lower bound for...

Tight bounds for k-set agreement
Soma Chaudhuri, Maurice Erlihy, Nancy A. Lynch, Mark R. Tuttle
Pages: 912-943
DOI: 10.1145/355483.355489
We prove tight bounds on the time needed to solve k-set agreement. In this problem, each processor starts with an arbitrary input value taken from a fixed set, and halts after choosing an output value. In every...

Periodification scheme: constructing sorting networks with constant period
Mirosław kutyłowski, Krzysztof Loryś, Brigitte Oesterdiekhoff, Rolf Wanka
Pages: 944-967
DOI: 10.1145/355483.355490
We consider comparator networks M that are used repeatedly: while the output produced by M is not sorted, it is fed again into M. Sorting algorithms working in this way are called...