Publications

Sort by: Date | Author | Title

Arge, L. A. & Miltersen, P. B. (1999). On showing lower bounds for external-memory computational geometry problems. D I M A C S Series in Discrete Mathematics and Theoretical Computer Science, 50, 139-160.

Miltersen, P. B., Vinodchandran, N. V. & Watanabe, O. (1999). Super-Polynomial Versus Half-Exponential Circuit Size in the Exponential Hierarchy. In T. Asano, H. Imai, D. T. Lee, S. Nakano & T. Tokuyama (Eds.), Computing and Combinatorics: 5th Annual International Conference, COCOON'99 Tokyo, Japan, July 26-28, 1999 Proceedings (pp. 210-220). Springer. Lecture Notes in Computer Science Vol. 1627 https://doi.org/10.1007/3-540-48686-0_21

Skyum, S., Frandsen, G. S., Miltersen, P. B. & Binderup, P. G. (1999). The Complexity of Identifying Large Equivalence Classes. Fundamenta Informaticae, 38(1-2), 25-37. https://doi.org/10.3233/FI-1999-381203

Buss, J. F., Frandsen, G. S. & Shallit, J. O. (1999). The Computational Complexity of Some Problems of Linear Algebra. Journal of Computer and System Sciences, 58(3), 572-596. https://doi.org/10.1006/jcss.1998.1608

Miltersen, P. B. (1998). Error correcting codes, perfect hashing circuits, and deterministic dynamic dictionaries. In Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms (pp. 556-563). Association for Computing Machinery.

Miltersen, P. B., Nisan, N., Safra, S. & Wigderson, A. (1998). On data structures and asymmetric communication complexity. Journal of Computer and System Sciences, 57(1), 37-49. https://doi.org/10.1006/jcss.1998.1577

Barrington, D. A. M., Lu, C-J., Miltersen, P. B. & Skyum, S. (1998). Searching constant width mazes captures the AC⁰ hierarchy. In M. Morvan, C. Meinel & D. Krob (Eds.), STACS 98: 15th Annual Symposium on Theoretical Aspects of Computer Science Paris, France, February 25-27, 1998 Proceedings (pp. 73-83). Springer. Lecture Notes in Computer Science Vol. 1373 https://doi.org/10.1007/BFb0028550

Frandsen, G. S. & Skyum, S. (1997). Dynamic maintenance of majority information in constant time per update. Information Processing Letters, 63(2), 75-78. https://doi.org/10.1016/S0020-0190(97)00100-2

Frandsen, G. S., Miltersen, P. B. & Skyum, S. (1997). Dynamic word problems. Association for Computing Machinery. Journal, 44(2), 257-271. https://doi.org/10.1145/256303.256309

Alon, N., Dietzfelbinger, M., Miltersen, P. B., Petrank, E. & Tardos, G. (1997). Is linear hashing good? In Proceedings of the twenty-ninth annual ACM symposium on Theory of computing (pp. 465-474). Association for Computing Machinery. https://doi.org/10.1145/258533.258639

Buss, J. F., Frandsen, G. S. & Shallit, J. O. (1997). The computational complexity of some problems of linear algebra. In R. Reischuk & M. Morvan (Eds.), STACS 97: 14th Annual Symposium on Theoretical Aspects of Computer Science Lübeck, Germany February 27–March 1, 1997 Proceedings (pp. 451-462). Springer. Lecture Notes in Computer Science Vol. 1200 https://doi.org/10.1007/BFb0023480

Brodnik, A., Miltersen, P. B. & Munro, J. I. (1997). Trans-dichotomous algorithms without multiplication - some upper and lower bounds. In F. Dehne, A. Rau-Chaplin, J-R. Sack & R. Tamassia (Eds.), Algorithms and Data Structures: 5th International Workshop, WADS'97 Halifax, Nova Scotia, Canada August 6-8, 1997 Proceedings (pp. 426-436). Springer. Lecture Notes in Computer Science Vol. 1272 https://doi.org/10.1007/3-540-63307-3_80

Miltersen, P. B. (1996). Lower bounds for static dictionaries on RAMs with bit operations but no multiplication. In Automata, Languages and Programming: 23rd International Colloquium, ICALP '96 Paderborn, Germany, July 8-12, 1996 Proceedings (pp. 442-453). Springer. Lecture Notes in Computer Science Vol. 1099 https://doi.org/10.1007/3-540-61440-0_149

Kautz, S. M. & Miltersen, P. B. (1996). Relative to a Random Oracle, NP is not small. Journal of Computer and System Sciences, 235-250. https://doi.org/10.1006/jcss.1996.0065

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

Miltersen, P. B. (1995). On the cell probe complexity of polynomial evaluation. Theoretical Computer Science, 143(1), 167-174. https://doi.org/10.1016/0304-3975(95)80032-5

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. Lecture Notes in Computer Science Vol. 955 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., Valence, M. & Barrington, D. A. M. (1994). Some results on uniform arithmetic circuit complexity. Theory of Computing Systems, 27(2), 105-124. https://doi.org/10.1007/BF01195199

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

Frandsen, G. S., Palsberg, J., Schmidt, E. M. & Sjøgaard, S. (1993). Layout Construction: A Case Study In Algorithm Engineering. Department of Computer Science, Aarhus University.

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. Lecture Notes in Computer Science Vol. 665 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. Lecture Notes in Computer Science Vol. 711 https://doi.org/10.1007/3-540-57182-5_38

Miltersen, P. B. (1993). The complexity of malign measures. S I A M Journal on Computing, 22(1), 147-156. https://doi.org/10.1137/0222012

Sturtivant, C. & Frandsen, G. S. (1993). The computational efficacy of finite-field arithmetic. Theoretical Computer Science, 112(2), 291-309. https://doi.org/10.1016/0304-3975(93)90022-L

Boyar, J., Frandsen, G. S. & Sturtivant, C. (1992). An arithmetic model of computation equivalent to threshold circuits. Theoretical Computer Science, 93(2), 303-319. https://doi.org/10.1016/0304-3975(92)90335-D

Miltersen, P. B. (1992). Circuit depth relative to a random oracle. Information Processing Letters, 42(6), 295-298. https://doi.org/10.1016/0020-0190(92)90225-K

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

Frandsen, G. S. (1991). Parallel Construction of Irreducible Polynomials. Department of Computer Science, Aarhus University.

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

Frandsen, G. S. & Sturtivant, C. (1991). What is an efficient implementation of the λ-calculus? In J. Hughes (Ed.), Functional Programming Languages and Computer Architecture: 5th ACM Conference Cambridge, MA, USA, August 26–30, 1991 Proceedings (pp. 289-312). Springer. Lecture Notes in Computer Science Vol. 523 https://doi.org/10.1007/3540543961_14

Frandsen, G. S. (1985). A Denotational Semantics for Logic Programming. Department of Computer Science, Aarhus University.

Frandsen, G. S. (1985). Learnability. Department of Computer Science, Aarhus University.

Frandsen, G. S. (1985). Logic programming and substitutions. In L. Budach (Ed.), Fundamentals of Computation Theory: FCT '85 Cottbus, GDR, September 9–13, 1985 (pp. 146-158). Springer. Lecture Notes in Computer Science Vol. 199 https://doi.org/10.1007/BFb0028799

Displaying results 151 to 189 out of 189

Sort by: Date | Author | Title

Revised 23.02.2021 -

Jan Frederiksen