Peter Bro Miltersen

Research output

Research output per year 1991 1999 2001 2005 2006 2007 2008 2009 2012 2013 2014 2023

• 55 Article in proceedings
• 34 Journal article
• 11 Conference article
• 8 Working paper
• 4 More
  • 1 Anthology
  • 1 Book chapter
  • 1 Conference abstract for conference
  • 1 Editorial

Research output per year

Research output per year

Search results

• 2007

  Computing Proper Equilibria of Zero-Sum Games

  Miltersen, P. B. & Sørensen, T. B., 2007, Proceedings of the 5th International Conference on Computers and Games: Computers and Games. Springer, p. 200-211 12 p. (Lecture Notes in Computer Science, Vol. 4630).

  Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review

  • Nash Equilibrium 100%
  8 Citations (Scopus)

• Finding Equilibria in Games of No Chance

  Hansen, K. A., Miltersen, P. B. & Sørensen, T. B., 2007, Computing and Combinatorics: Proc. of 13th Annual International Computing and Combinatorics Conference (COCOON 2007). Lin, G. (ed.). Springer, p. 274-284 10 p. (Lecture Notes in Computer Science, Vol. 4598).

  Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review
  7 Citations (Scopus)

• The Cell Probe Complexity of Succinct Data Structures

  Miltersen, P. B. & Gal, A., 2007, In: Theoretical Computer Science. 379, 3, p. 405-417 13 p.

  Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaper › Journal article › Research › peer-review
  47 Citations (Scopus)

• The Computational Complexity of One-dimensional Sandpiles

  Miltersen, P. B., 2007, In: Theory of Computing Systems. Volume 41, 1, p. 119-125 7 p.

  Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaper › Journal article › Research › peer-review
  14 Citations (Scopus)
• 2006

  Circuits on Cylinders

  Hansen, K. A., Miltersen, P. B. & Vinay, V., 2006, In: Computational Complexity. 15, 1, p. 62-81 20 p.

  Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaper › Journal article › Research › peer-review

  • Computational Power 100%
  4 Citations (Scopus)

• Computing Sequential Equilibria for Two-Player Games

  Miltersen, P. B. & Sørensen, T. B., 2006, Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms. 1 ed. Association for Computing Machinery, p. 107-116 10 p.

  Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review

  • Polynomial Time 100%
  • Linear Programming 50%
  • Linear Program 50%
  • Minimax Strategy 50%
  23 Citations (Scopus)

• Computing sequential equilibria for two-player games.

  Miltersen, P. B., 2006, Proc. 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'06). ACM-SIAM, p. 107-116 10 p.

  Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review

  • Polynomial Time 100%
  • Minimax Strategy 100%
  23 Citations (Scopus)

• Finding small OBDDs for incompletely specified truth tables is hard

  Miltersen, P. B. & Kristensen, J. T., 2006, Computing and Combinatorics: 12th Annual International Conference, COCOON 2006, Taipei, Taiwan, August 15-18, 2006. Proceedings. Chen, D. Z. & Lee, D. T. (eds.). Springer, p. 489-496 8 p. (Lecture Notes in Computer Science, Vol. 4112).

  Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review

  • Integer 100%
  • Truth Table 100%
  • Approximates 50%
  • Boolean Function 50%
  • Directed Graphs 50%
  2 Citations (Scopus)

• Finding small OBDDs for incompletely specified truth tables is hard

  Kristensen, J. T. & Miltersen, P. B., 2006, In: Electronic Colloquium on Computational Complexity. TR06-004, p. 1-6

  Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaper › Journal article › Research

  • Integer 100%
  • Truth Table 100%
  • Approximates 50%
  • Binary Decision 50%
  • Boolean Function 50%
  2 Citations (Scopus)

• On the Complexity of Numerical Analysis

  Miltersen, P. B., Kjeldgaard-Pedersen, J., Burgisser, P. & Allender, E., 2006, Proceedings of the 21st Annual IEEE Conference on Computational Complexity. IEEE Computer Society Press, p. 331-339 9 p.

  Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review

  • Numerical Analysis 100%
  • Traveling Salesman Problem 100%
  • Complexity Class 100%
  • Fundamental Problem 100%
  • Integer 50%
  33 Citations (Scopus)
• 2005

  Derandomizing Arthur-Merlin Games using Hitting Sets

  Miltersen, P. B. & Vinodchandran, N. V., 2005, In: I E E E Conference on Computational Complexity. Proceedings. 14, 3, p. 256-279

  Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaper › Journal article › Research › peer-review

  • Hitting Set 100%
  • Derandomization 50%
  46 Citations (Scopus)

• Lower bounds on the size of rank and selection indexes

  Miltersen, P. B., 2005, Proceedings of the Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, p. 11-12 2 p.

  Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review

• On converting CNF to DNF

  Miltersen, P. B., Radhakrishnan, J. & Wegener, I., 2005, In: Theoretical Computer Science. 347, p. 325-335 11 p.

  Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaper › Journal article › Research › peer-review

  33 Citations (Scopus)

• On the Complexity of Numerical Analysis

  Allender, E., Bürgisser, P., Kjeldgaard-Pedersen, J. & Miltersen, P. B., 2005, In: Electronic Colloquium on Computational Complexity. TR05-037, p. 1-12

  Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaper › Journal article › Research

  • Traveling Salesman Problem 100%
  • Complexity Class 100%
  • Polynomial Time 100%
  • Fundamental Problem 100%
  • Real Number 100%

• Reviewing Bounds on the Circuit Size of the Hardest Functions

  Frandsen, G. S. & Miltersen, P. B., 2005, In: Information Processing Letters. 95, 2, p. 354-357 4 p.

  Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaper › Journal article › Research › peer-review
  12 Citations (Scopus)

• The Computational Complexity of One-Dimensional Sandpiles

  Miltersen, P. B., 2005, New Computational Paradigms: First Conference on Computability in Europe, CiE 2005, Amsterdam, The Netherlands, June 8-12, 2005. Proceedings. Cooper, S. B., Löwe, B. & Torenvliet, L. (eds.). Springer, p. 342-350 9 p. (Lecture Notes in Computer Science, Vol. 3526).

  Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review
  1 Citation (Scopus)
• 2004

  Some Meet-in-the-middle Circuit Lower Bounds

  Hansen, K. A. & Miltersen, P. B., 2004, Mathematical Foundations of Computer Science 2004: 29th International Symposium, MFCS 2004, Prague, Czech Republic, August 22-27, 2004. Proceedings. Fiala, J., Koubek, V. & Kratochvil, J. (eds.). Springer, p. 334-345 12 p. (Lecture Notes in Computer Science, Vol. 3153).

  Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review

  • Circuit Complexity 100%
  • Strongest Result 100%
  • Polynomial 100%
  • Electronic Circuit 100%
  19 Citations (Scopus)
• 2003

  Circuits on Cylinders

  Hansen, K. A., Miltersen, P. B. & Vinay, V., 2003, Fundamentals of Computation Theory. Springer, p. 171-182 12 p. (Lecture Notes in Computer Science, Vol. 2751).

  Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review
  5 Citations (Scopus)

• On converting CNF to DNF

  Miltersen, P. B., Radhakrishnan, J. & Wegener, I., 2003, Mathematical Foundations of Computer Science 2003: 28th International Symposium, MFCS 2003, Bratislava, Slovakia, August 25-29, 2003, Proceedings. Rovan, B. & Vojtás, P. (eds.). Springer, p. 612-621 10 p. (Lecture Notes in Computer Science, Vol. 2747).

  Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review
  2 Citations (Scopus)

• The Cell Probe Complexity of Succinct Data Structures

  Gal, A. & Miltersen, P. B., 2003, Automata, Languages and Programming: 30th International Colloquium, ICALP 2003 Eindhoven, The Netherlands, June 30 - July 4, 2003 Proceedings. Baeten, J. C. M., Lenstra, J. K., Parrow, J. & Wöeginger, G. J. (eds.). Springer, p. 442-453 12 p. (Lecture Notes in Computer Science, Vol. 2719).

  Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research

  • Polynomial Evaluation 100%
  • Problem Structuring 100%
  • Even Function 50%
  29 Citations (Scopus)
• 2002

  Are Bitvectors Optimal?

  Buhrman, H., Miltersen, P. B., Radhakrishnan, J. & Venkatesh, S., 2002, In: S I A M Journal on Computing. 31, 6, p. 1723-1744 22 p.

  Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaper › Journal article › Research › peer-review

  • Randomized Algorithm 100%
  62 Citations (Scopus)

• Circuits on Cylinders

  Hansen, K. A., Miltersen, P. B. & Vinay, V., 2002, In: Electronic Colloquium on Computational Complexity. TR02-066, 11 p.

  Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaper › Journal article › Research › peer-review
• 2001

  Derandomizing complexity classes

  Miltersen, P. B., Rajasekaran, S. (Editor), Pardalos, P. M. (Editor), Reif, J. H. (Editor) & Rolim, J. D. P. (Editor), 2001, Handbook on Randomized Computing: Combinatorial Optimization, Vol. 9. chapter 19 ed. Kluwer Academic Publishers (Springer), Vol. II, chapter 19. p. 843-935 92 p.

  Research output: Contribution to book/anthology/report/proceeding › Book chapter › Research

  • Integer 100%
  • Polynomial 100%
  • Probability Theory 100%
  • Binary Representation 100%
  • Run Test 100%

• Deterministic Dictionaries

  Hagerup, T., Miltersen, P. B. & Pagh, R., 2001, In: J. Algorithms. 41, 1, p. 69-85 17 p.

  Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaper › Journal article › Research › peer-review

• Deterministic Dictionaries

  Hagerup, T., Miltersen, P. B. & Pagh, R., 2001, In: Journal of Algorithms. 41, p. 69-85 17 p.

  Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaper › Journal article › Research › peer-review

  88 Citations (Scopus)

• Lower Bounds for Dynamic Algebraic Problems

  Frandsen, G. S., Hansen, J. P. & Miltersen, P. B., 2001, In: Information and Computation. 171, 2, p. 333-349 17 p.

  Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaper › Journal article › Research › peer-review
  16 Citations (Scopus)

• On pseudorandom generators in NC⁰

  Cryan, M. & Miltersen, P. B., 2001, Mathematical Foundations of Computer Science 2001: Lecture Notes in Computer Science. Sgall, J., Pultr, A. & Kolman, P. (eds.). Lecture Notes in Computer Science 2136 ed. Springer, Vol. 2136/2001. p. 272-284 13 p.

  Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research

  • Statistical Test 100%
• 2000

  Are bitvectors optimal?

  Buhrman, H., Miltersen, P. B., Radhakrishnan, J. & Venkatesh, S., 2000, Proceedings of the thirty-second annual ACM symposium on Theory of computing. Association for Computing Machinery, p. 449-458 10 p.

  Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review
  35 Citations (Scopus)

• New bounds for the language compression problem

  Buhrman, H., Miltersen, P. B. & Laplante, S., 2000, 15th Annual IEEE Conference on Computational Complexity, 2000. Proceedings. . IEEE Computer Society Press, p. 126-130 5 p.

  Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review
  11 Citations (Scopus)

• On the Shannon function for partially defined Boolean functions

  Miltersen, P. B., 2000, Proceedings of the Workshop on Boolean Functions and Applications.

  Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research
• 1999

  Derandomizing Arthur-Merlin games using hitting sets

  Miltersen, P. B. & Vinodchandran, N. V., 1999, Proceedings of the 40th annual Foundations of Computer Science. IEEE Computer Society Press, p. 71-80 10 p.

  Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review
  55 Citations (Scopus)

• Fusion trees can be implemented with AC⁰ instructions only

  Andersson, A., Miltersen, P. B. & Thorup, M., 1999, In: Theoretical Computer Science. 215, p. 337-344 7 p.

  Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaper › Journal article › Research › peer-review
  36 Citations (Scopus)

• Linear hash functions

  Alon, N., Dietzfelbinger, M., Miltersen, P. B., Petrank, E. & Tardos, G., 1999, In: Association for Computing Machinery. Journal. 46, 5, p. 667-683 16 p.

  Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaper › Journal article › Research › peer-review
  31 Citations (Scopus)

• Lower bounds for dynamic algebraic problems

  Frandsen, G. S., Hansen, J. P. & Miltersen, P. B., 1999, In: Lecture Notes in Computer Science. p. 362-372 11 p.

  Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaper › Conference article › Research › peer-review
  4 Citations (Scopus)

• On monotone planar circuits

  Barrington, D. A. M., Lu, C.-J., Miltersen, P. B. & Skyum, S., 1999, Fourteenth Annual IEEE Conference on Computational Complexity, 1999. Proceedings. . IEEE Computer Society Press, p. 24-31 7 p.

  Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review
  23 Citations (Scopus)

• On showing lower bounds for external-memory computational geometry problems

  Arge, L. A. & Miltersen, P. B., 1999, In: D I M A C S Series in Discrete Mathematics and Theoretical Computer Science. 50, p. 139-160 21 p.

  Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaper › Journal article › Research

• Super-Polynomial Versus Half-Exponential Circuit Size in the Exponential Hierarchy

  Miltersen, P. B., Vinodchandran, N. V. & Watanabe, O., 1999, Computing and Combinatorics: 5th Annual International Conference, COCOON'99 Tokyo, Japan, July 26-28, 1999 Proceedings. Asano, T., Imai, H., Lee, D. T., Nakano, S.-I. & Tokuyama, T. (eds.). Springer, p. 210-220 11 p. (Lecture Notes in Computer Science, Vol. 1627).

  Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review
  36 Citations (Scopus)

• The Complexity of Identifying Large Equivalence Classes

  Skyum, S., Frandsen, G. S., Miltersen, P. B. & Binderup, P. G., 1999, In: Fundamenta Informaticae. 38, 1-2, p. 25-37 12 p.

  Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaper › Journal article › Research

  • Equivalence Class 100%
  • Equivalence Test 100%
  • Worst Case 33%
  • Upper Bound 33%
  2 Citations (Scopus)
• 1998

  Error correcting codes, perfect hashing circuits, and deterministic dynamic dictionaries

  Miltersen, P. B., 1998, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms. Association for Computing Machinery, p. 556-563 7 p.

  Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review

  16 Citations (Scopus)

• On data structures and asymmetric communication complexity

  Miltersen, P. B., Nisan, N., Safra, S. & Wigderson, A., 1998, In: Journal of Computer and System Sciences. 57, 1, p. 37-49 12 p.

  Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaper › Journal article › Research › peer-review
  172 Citations (Scopus)

• Searching constant width mazes captures the AC⁰ hierarchy

  Barrington, D. A. M., Lu, C.-J., Miltersen, P. B. & Skyum, S., 1998, STACS 98: 15th Annual Symposium on Theoretical Aspects of Computer Science Paris, France, February 25-27, 1998 Proceedings. Morvan, M., Meinel, C. & Krob, D. (eds.). Springer, p. 73-83 10 p. (Lecture Notes in Computer Science, Vol. 1373).

  Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review
  31 Citations (Scopus)
• 1997

  Dynamic word problems

  Frandsen, G. S., Miltersen, P. B. & Skyum, S., 1997, In: Association for Computing Machinery. Journal. 44, 2, p. 257-271 14 p.

  Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaper › Journal article › Research › peer-review
  31 Citations (Scopus)

• Is linear hashing good?

  Alon, N., Dietzfelbinger, M., Miltersen, P. B., Petrank, E. & Tardos, G., 1997, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing. Association for Computing Machinery, p. 465-474 10 p.

  Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review
  4 Citations (Scopus)

• Trans-dichotomous algorithms without multiplication - some upper and lower bounds

  Brodnik, A., Miltersen, P. B. & Munro, J. I., 1997, Algorithms and Data Structures: 5th International Workshop, WADS'97 Halifax, Nova Scotia, Canada August 6-8, 1997 Proceedings. Dehne, F., Rau-Chaplin, A., Sack, J.-R. & Tamassia, R. (eds.). Springer, p. 426-436 10 p. (Lecture Notes in Computer Science, Vol. 1272).

  Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review
  24 Citations (Scopus)
• 1996

  Lower bounds for static dictionaries on RAMs with bit operations but no multiplication

  Miltersen, P. B., 1996, Automata, Languages and Programming: 23rd International Colloquium, ICALP '96 Paderborn, Germany, July 8-12, 1996 Proceedings. Springer, p. 442-453 11 p. (Lecture Notes in Computer Science, Vol. 1099).

  Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review
  20 Citations (Scopus)

• Relative to a Random Oracle, NP is not small

  Kautz, S. M. & Miltersen, P. B., 1996, In: Journal of Computer and System Sciences. p. 235-250 15 p.

  Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaper › Journal article › Research › peer-review
  6 Citations (Scopus)

• Static dictionaries on AC⁰ RAMs: query time (√log n/log log n) is necessary and sufficient

  Andersson, A., Miltersen, P. B., Riis, S. & Thorup, M., 1996, 37th Annual Symposium on Foundations of Computer Science, 1996. Proceedings.. IEEE Computer Society Press, p. 441-450 10 p.

  Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review
  24 Citations (Scopus)

• The asymptotic complexity of merging networks

  Miltersen, P. B., Paterson, M. & Tarui, J., 1996, In: Association for Computing Machinery. Journal. 43, 1, p. 147-165

  Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaper › Journal article › Research › peer-review
  13 Citations (Scopus)
• 1995

  Dynamic algorithms for the Dyck languages

  Frandsen, G. S., Husfeldt, T., Miltersen, P. B., Rauhe, T. & Skyum, S., 1995, Algorithms and Data Structures: 4th International Workshop, WADS '95 Kingston, Canada, August 16-18, 1995 Proceedings. Akl, S. G., Dehne, F., Sack, J.-R. & Santoro, N. (eds.). Springer, p. 98-108 10 p.

  Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review

  • Data Structure 100%
  • Randomized Algorithm 100%
  • Dynamic Algorithms 100%
  8 Citations (Scopus)

• On data structures and asymmetric communication complexity

  Miltersen, P. B., Nisan, N., Safra, S. & Wigderson, A., 1995, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing. Association for Computing Machinery, p. 103-111 8 p.

  Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review