Author name cluster
Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.
I&C Journal 2009 Journal Article
In 1981, Paris and Wilkie indicated it was an open question whether I Σ 0 would satisfy the Second Incompleteness Theorem for Herbrand deduction. We will show that some specially formulated axiomizations for I Σ 0 can evade the Herbrandized version of the Second Incompleteness Theorem.
I&C Journal 1992 Journal Article
Consider a file which arranges records in sequential order, and stores them with possible empty spaces in M consecutive pages of memory. We develop an insertion-deletion algorithm which runs in a worst-case time approximately proportional to log2 M divided by the page-size when the set of manipulated records has cardinality O(M).
SODA Conference 1992 Conference Paper
STOC Conference 1990 Conference Paper
FOCS Conference 1990 Conference Paper
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. >
I&C Journal 1989 Journal Article
Fredman has shown that Ω(log k N) lower bounds the complexity for doing aggregate orthogonal range queries on a set of N records in a dynamic environment, where the computing machine can use only addition for calculating aggregates. We introduce a natural k-dimensional analog to the Karlsson-Munro-Robertson (1985, in “The 12th ICALP Symposium, ” pp. 318–327) contiguous segment assumption. This assumption is shown to be sufficient to extend Fredman's formalism so that subtraction as well as addition may be included in the Ω(log k N) lower bound. Since subtraction operations are known to speed up orthogonal range queries for static data structures with polylog memory redunduncy, it is significant that subtraction is not also helpful in a dynamic environment. The techniques introduced in Section 2 are stated in very general terms because they should have applications to other types of problems, besides those we consider.
I&C Journal 1989 Journal Article
Several articles have noted the usefulness of a retrieval algorithm called sequential interpolation search, and Yao and Yao have proven a lower bound log logN−O(1), showing this algorithm is actually optimal up to an additive constant on unindexed files of sizeNgenerated by the uniform probability distribution. We generalize the latter to show log logN− log logP−O(1) lower bounds the complexity of any retrieval algorithm withPparallel processors for searching an unindexed file of sizeN. This result is surprising because we also show how to obtain an upper bound that matches the lower bound up to an additive constant with a procedure that actually usesno parallel processingoutside its last iteration (at which time our proposal turns onPprocessors in parallel). Our first theorem therefore states thatparallel processing before the literally last iterationin the search of an unindexed ordered file hasnearly no usefulness. Two further surprising facts are that the preceding result holds even when communication between the parallel processing units involvesno delayand that the parallel algorithms are actuallyinherently slowerthan their sequential counterparts when each invocation of the SIMD machine invokes a communication step withany typeof nonzerodelay. The presentation in the first two chapters of this paper is quite informal, so that the reader can quickly grasp the underlying intuition.
STOC Conference 1984 Conference Paper
STOC Conference 1982 Conference Paper