[ACM Press the twenty-fifth annual ACM symposium - San Diego, California, United States (1993.05.16-1993.05.18)] Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 - More deterministic simulation in logspace

[ACM Press the twenty-fifth annual ACM s

✍ Nisan, Noam; Zuckerman, David 📂 Article 📅 1993 🏛 ACM Press ⚖ 807 KB

We show that any randomized space(S) algorithm which uses only poly(S) random bits can be simulated deterministically in space(S), for S(n) ~log n. Of independent interest is our main technical tool: a procedure which extracts randomness from a defective random source using a small additional number

[ACM Press the twenty-fifth annual ACM s

[ACM Press the twenty-fifth annual ACM symposium - San Diego, California, United States (1993.05.16-1993.05.18)] Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 - Multiple matching of rectangular patterns

✍ Idury, Ramana M.; Schäffer, Alejandro A. 📂 Article 📅 1993 🏛 ACM Press ⚖ 933 KB

[ACM Press the twenty-fifth annual ACM s

[ACM Press the twenty-fifth annual ACM symposium - San Diego, California, United States (1993.05.16-1993.05.18)] Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 - Thermodynamics of computation and information distance

✍ Bennett, Charles H.; Gács, Péter; Li, Ming; Vitányi, Paul M. B.; Zurek, Wojciech 📂 Article 📅 1993 🏛 ACM Press ⚖ 976 KB

[ACM Press the twenty-fifth annual ACM s

[ACM Press the twenty-fifth annual ACM symposium - San Diego, California, United States (1993.05.16-1993.05.18)] Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 - Wait-free k -set agreement is impossible

✍ Saks, Michael; Zaharoglou, Fotios 📂 Article 📅 1993 🏛 ACM Press ⚖ 931 KB

[ACM Press the twenty-fifth annual ACM s

[ACM Press the twenty-fifth annual ACM symposium - San Diego, California, United States (1993.05.16-1993.05.18)] Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 - A parallel approximation algorithm for positive linear programming

✍ Luby, Michael; Nisan, Noam 📂 Article 📅 1993 🏛 ACM Press ⚖ 602 KB

[ACM Press the twenty-fifth annual ACM s

[ACM Press the twenty-fifth annual ACM symposium - San Diego, California, United States (1993.05.16-1993.05.18)] Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 - A linear time algorithm for finding tree-decompositions of small treewidth

✍ Bodlaender, Hans L. 📂 Article 📅 1993 🏛 ACM Press ⚖ 833 KB