Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 46 Issue 5, Sept. 1999

Purely functional, real-time deques with catenation
Haim Kaplan, Robert E. Tarjan
Pages: 577-603
DOI: 10.1145/324133.324139
We describe an efficient, purely functional implementation of deques with catenation. In addition to being an intriguing problem in its own right, finding a purely functional implementation of catenable deques is required to add certain...

Authoritative sources in a hyperlinked environment
Jon M. Kleinberg
Pages: 604-632
DOI: 10.1145/324133.324140
The network structure of a hyperlinked environment can be a rich source of information about the content of the environment, provided we have effective means for understanding it. We develop a set of algorithmic tools for extracting information...

Simple and efficient bounded concurrent timestamping and the traceable use abstraction
Cynthia Dwork, Orli Waarts
Pages: 633-666
DOI: 10.1145/324133.324161
In a timestamping system, processors repeatedly choose timestamps so that the order of the timestamps obtained reflects the real-time order in which they were requested. Concurrent timestamping systems permit...

Linear hash functions
Noga Alon, Martin Dietzfelbinger, Peter Bro Miltersen, Erez Petrank, Gábor Tardos
Pages: 667-683
DOI: 10.1145/324133.324179
Consider the set H of all linear (or affine) transformations between two vector spaces over a finite field F. We study how good ...

Sample-efficient strategies for learning in the presence of noise
Nicolò Cesa-Bianchi, Eli Dichterman, Paul Fischer, Eli Shamir, Hans Ulrich Simon
Pages: 684-719
DOI: 10.1145/324133.324221
In this paper, we prove various results about PAC learning in the presence of malicious noise. Our main interest is the sample size behavior of learning algorithms. We prove the first nontrivial sample complexity lower bound in this model by...

Scheduling multithreaded computations by work stealing
Robert D. Blumofe, Charles E. Leiserson
Pages: 720-748
DOI: 10.1145/324133.324234
This paper studies the problem of efficiently schedulling fully strict (i.e., well-structured) multithreaded computations on parallel computers. A popular and practical method of scheduling this kind of dynamic MIMD-style computation is...

Secrecy by typing in security protocols
Martín Abadi
Pages: 749-786
DOI: 10.1145/324133.324266
We develop principles and rules for achieving secrecy properties in security protocols. Our approach is based on traditional classification techniques, and extends those techniques to handle concurrent processes that use shared-key cryptography....