Export Citations
Save this search
Please login to be able to save your searches and receive alerts for new content matching your search criteria.
- ArticleDecember 1985
One-way functions and pseudorandom generators
STOC '85: Proceedings of the seventeenth annual ACM symposium on Theory of computingPages 363–365https://doi.org/10.1145/22145.22185One-way are those functions which are easy to compute, but hard to invert on a non-negligible fraction of instances. The existence of such functions with some additional assumptions was shown to be sufficient for generating perfect pseudorandom strings |...
- ArticleDecember 1985
Self-organizing sequential search and Hilbert's inequalities
STOC '85: Proceedings of the seventeenth annual ACM symposium on Theory of computingPages 217–223https://doi.org/10.1145/22145.22170In this paper we describe a general technique which can be used to solve an old problem in analyzing self-organizing sequential search. We prove that the average time required for the move-to-front heuristic is no more than π/2 times that of the optimal ...
- ArticleDecember 1985
The two-processor scheduling problem is in R-NC
STOC '85: Proceedings of the seventeenth annual ACM symposium on Theory of computingPages 11–21https://doi.org/10.1145/22145.22147The two-processor scheduling problem is perhaps the most basic problem in scheduling theory, and several efficient algorithms have been discovered for it. However, these algorithms are inherently sequential in nature. We give a fast parallel (R-NC) ...