Publications

Sort by: Date | Author | Title

Frandsen, G. S., Hansen, J. P. & Miltersen, P. B. (2001). Lower Bounds for Dynamic Algebraic Problems. Information and Computation, 171(2), 333-349. https://doi.org/10.1006/inco.2001.3046

Cryan, M. & Miltersen, P. B. (2001). On pseudorandom generators in NC⁰. In J. Sgall, A. Pultr & P. Kolman (Eds.), Mathematical Foundations of Computer Science 2001: Lecture Notes in Computer Science (Lecture Notes in Computer Science 2136 ed., Vol. 2136/2001, pp. 272-284). Springer.

Buhrman, H., Miltersen, P. B., Radhakrishnan, J. & Venkatesh, S. (2000). Are bitvectors optimal? In Proceedings of the thirty-second annual ACM symposium on Theory of computing (pp. 449-458). Association for Computing Machinery. https://doi.org/10.1145/335305.335357

Buhrman, H., Miltersen, P. B. & Laplante, S. (2000). New bounds for the language compression problem. In 15th Annual IEEE Conference on Computational Complexity, 2000. Proceedings. (pp. 126-130). IEEE Computer Society Press. https://doi.org/10.1109/CCC.2000.856742

Frandsen, G. S. (2000). On the Density of Normal Bases in Finite Fields. Finite Fields and Their Applications, 6(1), 23-38. https://doi.org/10.1006/ffta.1999.0263

Miltersen, P. B. (2000). On the Shannon function for partially defined Boolean functions. In Proceedings of the Workshop on Boolean Functions and Applications

Miltersen, P. B. & Vinodchandran, N. V. (1999). Derandomizing Arthur-Merlin games using hitting sets. In Proceedings of the 40th annual Foundations of Computer Science (pp. 71-80). IEEE Computer Society Press. https://doi.org/10.1109/SFFCS.1999.814579

Andersson, A., Miltersen, P. B. & Thorup, M. (1999). Fusion trees can be implemented with AC⁰ instructions only . Theoretical Computer Science, 215, 337-344. https://doi.org/10.1016/S0304-3975(98)00172-8

Alon, N., Dietzfelbinger, M., Miltersen, P. B., Petrank, E. & Tardos, G. (1999). Linear hash functions. Journal of the ACM, 46(5), 667-683. https://doi.org/10.1145/324133.324179

Frandsen, G. S., Hansen, J. P. & Miltersen, P. B. (1999). Lower bounds for dynamic algebraic problems. Lecture Notes in Computer Science, 362-372. https://doi.org/10.1007/3-540-49116-3

Barrington, D. A. M., Lu, C.-J., Miltersen, P. B. & Skyum, S. (1999). On monotone planar circuits. In Fourteenth Annual IEEE Conference on Computational Complexity, 1999. Proceedings. (pp. 24-31). IEEE Computer Society Press. https://doi.org/10.1109/CCC.1999.766259

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. 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. 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. Journal of the ACM, 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. 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. 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. 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. Journal of the ACM, 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. 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. 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. (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. 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. https://doi.org/10.1007/BFb0028799

Displaying results 201 to 250 out of 250

Sort by: Date | Author | Title

Revised 01.09.2025