Export Citations
Save this search
Please login to be able to save your searches and receive alerts for new content matching your search criteria.
- ArticleOctober 1985
Slimming down search structures: A functional approach to algorithm design
SFCS '85: Proceedings of the 26th Annual Symposium on Foundations of Computer SciencePages 165–174https://doi.org/10.1109/SFCS.1985.51We establish new upper bounds on the complexity of several "rectangle" problems. Our results include, for instance, optimal algorithms for range counting and rectangle searching in two dimensions. These involve linear space implementations of range ...
- ArticleOctober 1985
An optimal parallel algorithm for integer sorting
SFCS '85: Proceedings of the 26th Annual Symposium on Foundations of Computer SciencePages 496–504https://doi.org/10.1109/SFCS.1985.9We assume a parallel RAM model which allows both concurrent writes and concurrent reads of global memory. Our algorithms are randomized: each processor is allowed an independent random number generator. However our stated resource bounds hold for worst ...
- ArticleOctober 1985
Separating the polynomial-time hierarchy by oracles
SFCS '85: Proceedings of the 26th Annual Symposium on Foundations of Computer SciencePages 1–10https://doi.org/10.1109/SFCS.1985.49We present exponential lower bounds on the size of depth-k Boolean circuits for computing certain functions. These results imply that there exists an oracle set A such that, relative to A, all the levels in the polynomial-time hierarchy are distinct, ...
- ArticleOctober 1985
Robin hood hashing
SFCS '85: Proceedings of the 26th Annual Symposium on Foundations of Computer SciencePages 281–288https://doi.org/10.1109/SFCS.1985.48This paper deals with hash tables in which conflicts are resolved by open addressing. The initial contribution is a very simple insertion procedure which (in comparison to the standard approach) has the effect of dramatically reducing the variance of ...
- ArticleOctober 1985
On information flow and sorting: New upper and lower bounds for VLSI circuits
SFCS '85: Proceedings of the 26th Annual Symposium on Foundations of Computer SciencePages 208–221https://doi.org/10.1109/SFCS.1985.39This work comprises two parts: lower bounds and upper bounds in VLSI circuits. The upper bounds are for the sorting problem: we describe a large number of constructions for sorting N numbers in the range [0,M] for the standard VLSI bit model. Among ...
- ArticleOctober 1985
Efficient string matching in the presence of errors
SFCS '85: Proceedings of the 26th Annual Symposium on Foundations of Computer SciencePages 126–136https://doi.org/10.1109/SFCS.1985.22Consider the string matching problem where differences between characters of the pattern and characters of the text are allowed. Each difference is due to either a mismatch between a character of the text and a character of the pattern or a superfluous ...
- ArticleOctober 1985
Average case lower bounds on the construction and searching of partial orders
SFCS '85: Proceedings of the 26th Annual Symposium on Foundations of Computer SciencePages 303–311https://doi.org/10.1109/SFCS.1985.13It is very well known in computer science that partially ordered files are easier to search. In the worst case, for example, a totally unordered file requires no preprocessing, but Ώ(n) time to search, while a totally ordered file requires Ώ(n log n) ...