Michael L. Fredman

STOC Conference 1998 Conference Paper

Information Theoretic Implications for Pairing Heaps

• Michael L. Fredman

TCS Journal 1996 Journal Article

Products of finite state machines with full coverage

• David M. Cohen
• Michael L. Fredman

Given a collection of finite state machines, M i, with the same input alphabet, let M be the product machine, M = ΠM j. In general, not every state in M is reachable. A natural question is whether there are any inherent limits to the number of reachable states in a system that is the product of many small finite state machines. This note constructs a family of product machines M where the number of states is doubly exponential in the number of states in any individual machine M i and every product state is reachable. Products of finite state machines such as discussed in this note occur when analyzing large collections of independently designed telecommunications services. These examples raise the possibility that product finite state machines modeling systems of independently designed services may have different characteristics from finite state machines modeling communications protocols. Consequently, analyzing collections of telecommunications services may require new heuristic methods.

SODA Conference 1993 Conference Paper

Data Structures for Traveling Salesmen

• Michael L. Fredman
• David S. Johnson 0001
• Lyle A. McGeoch
• G. Ostheimer

FOCS Conference 1993 Conference Paper

Optimal Bi-Weighted Binary Trees and the Complexity of Maintaining Partial Sums

• Haripriyan Hampapuram
• Michael L. Fredman

Let A be an array. The partial sum problem concerns the design of a data structure for implementing the following operations. The operation update(j, x) has the effect, A[j]/spl larr/A[j]+x, and the query operation sum(j) returns the partial sum, /spl Sigma//sub i=1//sup j/A[i]. Our interest centers upon the optimal efficiency with which sequences of such operations can be performed, and we derive new upper and lower bounds in the semi-group model of computation. Our analysis relates the optimal complexity of the partial sum problem to optimal binary trees relative to a type of weighting scheme that defines the notion of bi-weighted binary tree. >

STOC Conference 1990 Conference Paper

BLASTING through the Information Theoretic Barrier with FUSION TREES

• Michael L. Fredman
• Dan E. Willard

FOCS Conference 1990 Conference Paper

Trans-dichotomous Algorithms for Minimum Spanning Trees and Shortest Paths

• Michael L. Fredman
• Dan E. Willard

The fusion tree method is extended to develop a linear-time algorithm for the minimum spanning tree problem and an O(m+n log n/log log n) implementation of Dijkstra's shortest-path algorithm for a graph with n vertices and m edges. The shortest-path algorithm surpasses information-theoretic limitations. The extension of the fusion tree method involves the development of a new data structure, the atomic heap. The atomic heap accommodates heap (priority queue) operations in constant amortized time under suitable polylog restrictions on the heap size. The linear-time minimum spanning tree algorithm results from a direct application of the atomic heap. To obtain the shortest path algorithm, the atomic heap is used as a building block to construct a new data structure, the AF-heap, which has no size restrictions and surpasses information theoretic limitations. The AF-heap belongs to the Fibonacci heap family. >

STOC Conference 1989 Conference Paper

The Cell Probe Complexity of Dynamic Data Structures

• Michael L. Fredman
• Michael E. Saks

Dynamic data structure problems involve the representation of data in memory in such a way as to permit certain types of modifications of the data (updates) and certain types of questions about the data (queries). This paradigm encompasses many fundamental problems in computer science. The purpose of this paper is to prove new lower and upper bounds on the time per operation to implement solutions to some familiar dynamic data structure problems including list representation, subset ranking, partial sums, and the set union problem. The main features of our lower bounds are: They hold in the cell probe model of computation (A. Yao [18]) in which the time complexity of a sequential computation is defined to be the number of words of memory that are accessed. (The number of bits b in a single word of memory is a parameter of the model). All other computations are free. This model is at least as powerful as a random access machine and allows for unusual representation of data, indirect addressing etc. This contrasts with most previous lower bounds which are proved in models (e.g., algebraic, comparison, pointer manipulation) which require restrictions on the way data is represented and manipulated. The lower bound method presented here can be used to derive amortized complexities, worst case per operation complexities, and randomized complexities. The results occasionally provide (nearly tight) tradeoffs between the number R of words of memory that are read per operation, the number W of memory words rewritten per operation and the size b of each word. For the problems considered here there is a parameter n that represents the size of the data set being manipulated and for these problems b = log n is a natural register size to consider. By letting b vary, our results illustrate the effect of register size on time complexity. For instance, one consequence of the results is that for some of the problems considered here, increasing the register size from log n to polylog( n ) only reduces the time complexity by a constant factor. On the other hand, decreasing the register size from log n to 1 increases time complexity by a log n factor for one of the problems we consider and only a loglog n factor for some other problems. The first two specific data structure problems for which we obtain bounds are: List Representation. This problem concerns the representation of an ordered list of at most n (not necessarily distinct) elements from the universe U = {1, 2,…, n }. The operations to be supported are report( k ), which returns the k th element of the list, insert( k , u ) which inserts element u into the list between the elements in positions k - 1 and k , delete( k ), which deletes the k th item. Subset Rank. This problem concerns the representation of a subset S of U = {1, 2,…, n }. The operations that must be supported are the updates “insert item j into the set” and “delete item j from the set” and the queries rank( j ), which returns the number of elements in S that are less than or equal to j . The natural word size for these problems is b = log n , which allows an item of U or an index into the list to be stored in one register. One simple solution to the list representation problem is to maintain a vector v , whose k th entry contains the k th item of the list. The report operation can be done in constant time, but the insert and delete operations may take time linear in the length of the list. Alternatively, one could store the items of the list with each element having a pointer to its predecessor and successor in the list. This allows for constant time updates (given a pointer to the appropriate location), but requires linear cost for queries. This problem can be solved must more efficiently by use of balanced trees (such as AVL trees). When b = log n , the worst case cost per operation using AVL trees is O (log n ). If instead b = 1, so that each bit access costs 1, then the AVL three solution requires O (log 2 n ) per operation. It is not hard to find similar upper bounds for the subset rank problem (the algorithms for this problem are actually simpler than AVL trees). The question is: are these upper bounds bet possible? Our results show that the upper bounds for the case of log n bit registers are within a loglog n factor of optimal. On the other hand, somewhat surprisingly, for the case of single bit registers there are implementations for both of these problems that run in time significantly faster than O (log 2 n ) per operation. Let CPROBE( b ) denote the cell probe computational model with register size b . Theorem 1. If b ≤ (log n ) t for some t , then any CPROBE( b ) implementation of either list representation or the subset rank requires Ω(log n /loglog n ) amortized time per operation. Theorem 2. Subset rank and list representation have CPROBE(1) implementations with respective complexities O ((log n )(loglog n )) and O ((log n )(loglog n ) 2 ) per operation. Paul Dietz (personal communication) has found an implementation of list representation with log n bit registers that requires only O (log n /loglog n ) time per operation, and thus the result of theorem 1 is best possible. The lower bounds of theorem 1 are derived from lower bounds for a third problem: Partial sum mode k. An array A [1],…, A [ N ] of integers mod k is to be represented. Updates are add( i , δ) which implements A [ i ] ← A [ i ] + δ; and queries are sum(j) which returns Σ i ≤ j A [ i ] (mod k ). This problem is demoted PS(n, k). Our main lower bound theorems provide tradeoffs between the number of register rewrites and register reads as a function of n , k , and b . Two corollaries of these results are: Theorem 3. Any CPROBE( b ) implementation of PS(n, 2) (partial sums mod 2) requires Ω(log n /(loglog n + log b )) amortized time per operation, and for b ≥ log n , there is an implementation that achieves this. In particular, if b = Θ((log n ) c ) for some constant c , then the optimal time complexity of PS(n, 2) is θ(log n /loglog n ). Theorem 4. Any CPROBE(1) implementation of PS(n, n) with single bit registers requires Ω((log n /loglog n ) 2 ) amortized time per operation, and there is an implementation that achieves O (log 2 n ) time per operation. It can be shown that a lower bound of PS(n, 2) is also a lower bound for both list representation and subset rank (the details, which are not difficult, are omitted from this report), and thus theorem 1 follows from theorem 3. The results of theorem 4 make an interesting contrast with those of theorem 2. For the three problems, list representation, subset rank and PS(n, k), there are standard algorithms that can be implemented on a CPROBE(log n ) that use time O (log n per operation, and their implementations on CPROBE(1) require O (log 2 n ) time. Theorem 4 says that for the problem PS(n, n) this algorithm is essentially best possible, while theorem 2 says that for list representation and rank, the algorithm can be significantly improved. In fact, the rank problem an be viewed as a special case of PS(n, n) where the variables take on values on {0, 1}, and apparently this specialization is enough to reduce the complexity on a CPROBE(1) by a factor of log n /loglog n , even though on a CPROBE(log n ) the complexities of the two problems differ by no more than a loglog n factor. The third problem we consider is the set union problem. This problem concerns the design of a data structure for the on-line manipulation of sets in the following setting. Initially, there are n singleton sets {1}, {2},…, { n } with i chosen as the name of the set { i }. Our data structure is required to implement two operations, Find( j ), and Union( A , B , C ). The operation Find( j ) returns the name of the set containing j . The operation Union( A , B , C ) combines the sets with names A and B . The names of the existing sets at any moment must be unique and chosen to be integers in the range from 1 to 2 n . The sets existing at any time are disjoint and define a partition of the elements into equivalence classes. A well known data structure for the set union problem represents the sets as trees and stores the name of a set in the root of its corresponding tree. A Union operation is performed by attaching the root of the smaller set as a child of the root of the larger set (weight rule). A Find operation is implemented by following the path from the appropriate node to the root of the tree containing it, and then redirecting to the root the parent pointers of the nodes encountered along this path (path compression). From now on we consider sequences of Union and Find operations consisting of n -1 Union operations and m Find operations with m ≥ n . Tarjan [14] demonstrated that the above algorithm requires time θ( m α( m , n )), where α( m , n ) is an inverse to Ackermann's function, to execute n -1 Union and m Find operations. In particular, if m = θ( n ), then the running time is almost, but not quite, linear. Tarjan conjectured [14] that no linear time algorithm exists for the set union problem, and provided significant evidence in favor of this conjecture (which we discuss in the following section). We affirm Tarjan's conjecture in the CPROBE(log n ) model. Theorem 5. Any CPROBE(log n ) implementation of the set union problem requires Ω( m α( m , n )) time to execute m Find's and n -1 Union's, beginning with n singleton sets. N. Blum [2] has given a log n /loglog n algorithm (worst case time per operation) for the set union problem. This algorithm is also optimal in the CPROBE(polylog n ) model. The following Section provides further discussion of these results, Section 3 outlines our lower bound method, and Section 4 contains some proofs.

FOCS Conference 1988 Conference Paper

Three Stacks

• Michael L. Fredman
• Deborah L. Goldsmith

The storage allocation for three stacks has been traditionally accomplished by using pointers to store the stacks as linked lists or by relocating the stacks within memory when collisions take place. The former approach requires additional space to store the pointers, and the latter approach requires additional time. The authors explore the extent to which some additional space or time is required to maintain three stacks. They provide a formal setting for this topic and establish upper and lower complexity bounds on various aspects. >

FOCS Conference 1984 Conference Paper

Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms

• Michael L. Fredman
• Robert Endre Tarjan

In this paper we develop a new data structure for implementing heaps (priority queues). Our structure, Fibonacci heaps (abbreviated F-heaps), extends the binomial queues proposed by Vuillemin and studied further by Brown. F-heaps support arbitrary deletion from an n-item heap in 0(log n) amortized time and all other standard heap operations in 0(1) amortized time. Using F-heaps we are able to obtain improved running times for several network optimization algorithms.

FOCS Conference 1983 Conference Paper

Hash Functions for Priority Queues

• Miklós Ajtai
• Michael L. Fredman
• János Komlós

The complexity of priority queue operations is analyzed with respect to the cell probe computational model of A. Yao. A method utilizing families of hash functions is developed which permits priority queue operations to be implemented in constant worst case time provided that a size constraint is satisfied. The minimum necessary size of a family of hash functions for computing the rank function is estimated and contrasted with the minimum size required for perfect hashing.

FOCS Conference 1982 Conference Paper

Storing a Sparse Table with O(1) Worst Case Access Time

• Michael L. Fredman
• János Komlós
• Endre Szemerédi

We describe a data structure for representing a set of n items from a universe of m items, which uses space n+o(n) and accommodates membership queries in constant time. Both the data structure and the query algorithm are easy to implement.

TCS Journal 1981 Journal Article

Inherent complexity trade-offs for range query problems

• Walter A. Burkhard
• Michael L. Fredman
• Daniel J. Kleitman

FOCS Conference 1980 Conference Paper

The Inherent Complexity of Dynamic Data Structures which Accommodate Range Queries

• Michael L. Fredman

A formal framework is presented in which to explore the complexity issues of data structures which accommodate various types of range queries. Within this framework, a systematic and reasonably tractable method for assessing inherent complexity is developed. Included among the interesting results are the following: the fact that non-linear lower bounds are readily accessible, and the existence of a complexity gap between linear time and n log n time.

STOC Conference 1979 Conference Paper

A Near Optimal Data Structure for a Type of Range Query Problem

• Michael L. Fredman

TCS Journal 1976 Journal Article

How good is the information theory bound in sorting?

• Michael L. Fredman

We define a sorting problem on an n element set S to be a family 〈A 1, …, Ar 〉 of disjoint subsets of the set of n! linear orderings on S. Given an ordering ω ∈ ∪ j A j, we want to determine to which subset Aj the ordering ω belongs by performing a sequence of comparisons between the elements of S. The classical sorting problem corresponds to the case where the subsets Aj comprise the n! singleton sets of orderings. If a sorting problem is defined by r nonempty subsets Aj, then the information theory bound states that at least log2 r comparisons are required to solve that problem in the worst case. The purpose of this paper is to investigate the accuracy of this bound. While we show that it is usually very weak, we are nevertheless able to define a large class of problems for which this bound is good. As an application, we show that if X and Y are n element sets of real numbers, then the n 2 element set X + Y can be sorted with O (n 2) comparisons, improving upon the n 2 log2 n bound established by Harper et al. The problem of sorting X + Y was posed by Berkelamp.

FOCS Conference 1975 Conference Paper

On the Decision Tree Complexity of the Shortest Path Problems

• Michael L. Fredman

STOC Conference 1975 Conference Paper

Two Applications of a Probabilistic Search Technique: Sorting x + y and Building Balanced Search Trees

• Michael L. Fredman

Let X = {x 1 ,...,x N } and Y = {y 1 ,...,y N } be sets of N real numbers. We denote by X + Y the multiset {x i + y j ; 1 ≤ i, j ≤ N} of size N 2 . Berklekamp has posed the problem of sorting X + Y. Harper, Payne, Savage and Strauss [1] show that N 2 1og 2 N comparisons suffice to sort X + Y, thereby saving a factor of 2 over sorting without exploiting the structure of X + Y. (Given u in X + Y, we assume that we know the i,j indices such that u = x i + y j .) Furthermore, they show that this bound is tight for a restricted class of comparison algorithms. However, without their restriction the order of magnitude comparison complexity of this problem has remained an open question. In this paper we show that X + Y can be sorted with O(N 2 ) comparisons. Our proof is unusual for this type of problem in that we do not explicitly exhibit an algorithm. Instead, it is a particular application of a more general search technique whose behavior is easily related to information theoretic lower bounds. In the context of sorting, this search method translates into an insertion sort, where the insertions are not performed by means of the usual binary search, but rather as off-centered searches designed so that each comparison, roughly speaking, equally divides the space of remaining possibilities. We draw attention to this search technique because it might find application to other problems, and we illustrate this possibility with a second application.