Browsing LCS Technical Memos (1974 - 2003) by Author "Rivest, Ronald L."
Now showing items 1-15 of 15
-
An Application of Number Theory to the Organization of Raster Graphics Memory
(1984-04)A high-resolution raster-graphics display is usually combined with processing power and a memory organization that facilitates basic graphics operations. For many applications, including interactive text processing, the ... -
Estimateing a Probability using Finite Memory
(1983-11) -
A Fast Multiport Memory Based on Single-port Memory Cells
(1991-07)We present a new design for dual-port memories that uses single-port memory cells but guarantees fast deterministic read/write access. The basic unit of storage is the word, rather than the bit, and addresses conflicts ... -
Game Tree Searching by Min/Max Approximation
(1986-09) -
Inferring Decision Trees Using the Minimum Description Length Principle
(1987-09)We explore the use of Rissanen's Minimum Description Length Principle for the construction of decision trees. Empirical results comparing this approach to other methods are given. -
K+1 Heads are Better Than K
(1976-09)There are languages which can be recognized by a deterministic (k+1)-headed one-way finite automaton but which cannot be recognized by a k-headed one-way (deterministic or non-deterministic) finite automaton. Furthermore, ... -
The Markov Chain Tree Theorem
(1983-11)Let M be a finite first-order stationary Markov chain. We define an arborescence to be a set of edges in the directed graph for M having at most one edge out of every vertex, no cyles, and maximum cardinality. The weight ... -
The MD4 Message Digest Algorithm
(1990-10)The MD4 message digest algorithm takes an input message of arbitrary length and produces an output 128-bit "fingerprint" or "message digest," in such a way that it is (hopefully) computationally infeasible to produce two ... -
Metal Poker
(1979-02)Can two potentially dishonest players play a fair game of poker without using any cards (e.g. over the phone)? This paper provides the following answers: 1. No. (Rigorous mathematical proof supplied. 2. Yes. (Correct & ... -
A Method for Obtaining Digital Signatures and Public-key Cryptosystems
(1977-04)We present an encryption method with the novel property that publicly revealing an encryption key does not thereby reveal the corresponding decryption key. This has two important consequences. 1. Couriers or other secure ... -
The Mutual Exclusion Problem for Unreliable Processes
(1977-04)Consider n processes operating asynchronously in parallel, each of which maintains a single "public" variable which can be read (but not written) by the other processes. We show that the processes can synchronize their ... -
Network Control by Bayesian Broadcast
(1985-09) -
On the Worst-case Behavior of String-searching Algorithms
(1976-04)Any algorithm for finding a pattern of length k in a string of length n must examine at least n-k+1 of the characters of the string in the worst case. By considering the pattern 00…0, we prove that this is the best possible ... -
Optimal Arrangement of Keys in a Hash Table
(1976-07)When open addressing is used to resolve collisions in a hash table, a given set of keys may be arranged in many ways; typically this depends on the order in which the keys are inserted. We show that arrangements minimizing ... -
Randomized Encryption Techniques
(1983-01)A randomized encryption procedure enciphers a message by randomly choosing a ciphertext from a set of ciphertexts corresponding to the message under the current encryption key. At the cost of increasing the required ...
