Lawrence Snyder 0001

STOC Conference 1981 Conference Paper

Bounds on Minimax Edge Length for Complete Binary Trees (Extended Abstract)

• Mike Paterson
• Walter L. Ruzzo
• Lawrence Snyder 0001

FOCS Conference 1979 Conference Paper

On a General Method for Maximizing and Minimizing among Certain Geometric Problems (Extended Abstract)

• David P. Dobkin
• Lawrence Snyder 0001

Problems concerned with finding inscribing or circumscribing polygons that maximize some measurement are considered such as: Find an area maximizing triangle inscribed in a given convex polygon. Algorithms solving a number of these problems in linear time are presented. They use the common approach of finding an initial solution with respect to a fixed bounding point and then iteratively transforming this solution into a new solution with respect to a new point. The generality of this approach is discussed and several open problems are noted.

FOCS Conference 1977 Conference Paper

On Uniquely Represented Data Structures (Extended Abstract)

• Lawrence Snyder 0001

A model for searching algorithms is developed which includes most tree-like searching structures such as lists, binary trees, AVL trees and 2, 3-trees. It is shown that no searching algorithm employing a data structure that is uniquely represented (up to isomorphism) can provide search, insert and delete functions all operating faster than c√n time for every n key tree. The c√n bound is shown to be achievable for uniquely represented data structures.

FOCS Conference 1976 Conference Paper

A Linear Time Algorithm for Deciding Security

• Anita K. Jones
• Richard J. Lipton
• Lawrence Snyder 0001

The Folklore is replete with stories of "secure" protection systems being compromised in a matter of hours. This is quite astounding since one is not likely to claim that a system is secure without some sort of proof to support the claim. In practice, proof is not provided and one reason for this is clear: although the protection primitives are apparently quite simple, they may potentially interact in extremely complex ways. Vague and informal arguments, therefore, often overlook subtleties that an adversary can exploit. Precision is not merely desirable for protection systems, it is mandatory.

FOCS Conference 1975 Conference Paper

Synchronization and Computing Capabilities of Linear Asynchronous Structures

• Richard J. Lipton
• Raymond E. Miller
• Lawrence Snyder 0001

A model is defined in which questions concerning delay bounded asynchronous parallel systems may be investigated. Persistence and determinacy are introduced for this model. These two conditions are shown to be sufficient to guarantee that a synchronous execution policy can be relaxed to an asynchronous execution policy with no change to the result of the computation. In addition, the asynchronous execution time is only (D+1) times the synchronous execution time, where D is the delay bound. A wide class of recognition problems is identified which can be solved by linear asynchronous structures. Also, it is shown that synchronization problems, similar to the "firing squad synchronization problem, " cannot be solved by delay bounded asynchronous systems.