Publications

Andersson, A., Miltersen, P. B., Riis, S. & Thorup, M. (1996). Static dictionaries on AC⁰ RAMs: query time (√log n/log log n) is necessary and sufficient. In 37th Annual Symposium on Foundations of Computer Science, 1996. Proceedings. (pp. 441-450). IEEE Computer Society Press. https://doi.org/10.1109/SFCS.1996.548503

Miltersen, P. B., Paterson, M. & Tarui, J. (1996). The asymptotic complexity of merging networks. Association for Computing Machinery. Journal, 43(1), 147-165. https://doi.org/10.1145/227595.227693

Frandsen, G. S., Husfeldt, T., Miltersen, P. B., Rauhe, T. & Skyum, S. (1995). Dynamic algorithms for the Dyck languages. In S. G. Akl, F. Dehne, J.-R. Sack & N. Santoro (Eds.), Algorithms and Data Structures: 4th International Workshop, WADS '95 Kingston, Canada, August 16-18, 1995 Proceedings (pp. 98-108). Springer. https://doi.org/10.1007/3-540-60220-8_54

Miltersen, P. B., Nisan, N., Safra, S. & Wigderson, A. (1995). On data structures and asymmetric communication complexity. In Proceedings of the twenty-seventh annual ACM symposium on Theory of computing (pp. 103-111). Association for Computing Machinery. https://doi.org/10.1145/225058.225093

Fich, F. & Miltersen, P. B. (1995). Tables should be sorted (on random access machines). In S. G. Akl, F. Dehne, J.-R. Sack & N. Santoro (Eds.), Algorithms and Data Structures: 4th International Workshop, WADS '95 Kingston, Canada, August 16-18, 1995 Proceedings (pp. 482-493). Springer. https://doi.org/10.1007/3-540-60220-8_87

Miltersen, P. B., Subramanian, S., Vitter, J. S. & Tamassia, R. (1994). Complexity models for incremental computation. Theoretical Computer Science, 130(1), 203-236. https://doi.org/10.1016/0304-3975(94)90159-7

Miltersen, P. B. (1994). Lower bounds for union-split-find related problems on random access machines. In Proceedings of the twenty-sixth annual ACM symposium on Theory of computing (pp. 625-634). Association for Computing Machinery. https://doi.org/10.1145/195058.195415

Kautz, S. M. & Miltersen, P. B. (1994). Relative to a Random Oracle, NP is not small. In Proceedings of the Ninth Annual Structure in Complexity Theory Conference, 1994. (pp. 162-174). IEEE Computer Society Press.

Frandsen, G. S., Miltersen, P. B. & Skyum, S. (1993). Dynamic Word Problems. In 34th Annual Symposium on Foundations of Computer Science, 1993. Proceedings. (pp. 470-479). IEEE Computer Society Press. https://doi.org/10.1109/SFCS.1993.366840

Miltersen, P. B. (1993). The bit probe complexity measure revisited. In P. Enjalbert, A. Finkel & K. W. Wagner (Eds.), STACS 93: 10th Annual Symposium on Theoretical Ascpects of Computer Science Würzburg, Germany, February 25-27, 1993 Proceedings (pp. 662-671). Springer. https://doi.org/10.1007/3-540-56503-5_65

Frandsen, G. S., Miltersen, P. B. & Skyum, S. (1993). The complexity of finding replicas using equality tests. In A. M. Borzyszkowsji & S. Sokolowski (Eds.), Mathematical Foundations of Computer Science 1993: 18th International Symposium, MFCS'93 Gdansk, Poland, August 30-September 3, 1993 Proceedings (pp. 463-472). Springer. https://doi.org/10.1007/3-540-57182-5_38

Miltersen, P. B., Paterson, M. & Tarui, J. (1992). The asymptotic complexity of merging networks. In 33rd Annual Symposium on Foundations of Computer Science, 1992. Proceedings. (pp. 236-246). IEEE Computer Society Press. https://doi.org/10.1109/SFCS.1992.267768

Miltersen, P. B. (1991). The complexity of malign ensembles. In Proceedings of the Sixth Annual Structure in Complexity Theory Conference, 1991. (pp. 164-171). IEEE Computer Society Press. https://doi.org/10.1109/SCT.1991.160257

Displaying results 201 to 216 out of 216

Revised 23.08.2023