Publications

Sort by: Date | Author | Title

Hansen, T. D., Miltersen, P. B. & Sørensen, T. B. (2008). On Range of Skill. In Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence: Constraints, Satisfiability, and Search (pp. 277-282). AAAI Press.

Miltersen, P. B., Gurvich, V. & Andersson, D. (2008). The Complexity of Solving Stochastic Games on Graphs. Department of Computer Science, Aarhus University. http://www.daimi.au.dk/~bromille/Papers/mean.pdf

Miltersen, P. B. (2008). Trembling hand perfection is NP-hard. http://arxiv.org/PS_cache/arxiv/pdf/0812/0812.0492v1.pdf

Miltersen, P. B. & Sørensen, T. B. (2007). A Near-Optimal Strategy for a Heads-Up No-Limit Texas Hold'em Poker Tournament. In Proceedings of the 6th International Joint Conference on Autonomous Agents and Multiagent Systems (pp. 1168-1175) http://www.daimi.au.dk/~bromille/Papers/aamaspoker.pdf

Miltersen, P. B. & Sørensen, T. B. (2007). Computing Proper Equilibria of Zero-Sum Games. In Proceedings of the 5th International Conference on Computers and Games: Computers and Games (pp. 200-211). Springer. https://doi.org/10.1007/978-3-540-75538-8_18

Hansen, K. A. (2007). Computing Symmetric Boolean Functions by Circuits with Few Exact Threshold Gates. In G. Lin (Ed.), Computing and Combinatorics: 13th Annual International Conference, COCOON 2007, Banff, Canada, July 16-19, 2007. Proceedings (pp. 448-458). Springer. https://doi.org/10.1007/978-3-540-73545-8_44

Brodal, G. S., Georgiadis, L., Hansen, K. A. & Katriel, I. (2007). Dynamic Matchings in Convex Bipartite Graphs. In L. Kucera & A. Kucera (Eds.), Proc. 32nd International Symposium on Mathematical Foundations of Computer Science (pp. 406-417). Springer. https://doi.org/10.1007/978-3-540-74456-6_37

Hansen, K. A., Miltersen, P. B. & Sørensen, T. B. (2007). Finding Equilibria in Games of No Chance. In G. Lin (Ed.), Computing and Combinatorics: Proc. of 13th Annual International Computing and Combinatorics Conference (COCOON 2007) (pp. 274-284). Springer. https://doi.org/10.1007/978-3-540-73545-8_28

Miltersen, P. B. & Gal, A. (2007). The Cell Probe Complexity of Succinct Data Structures. Theoretical Computer Science, 379(3), 405-417. https://doi.org/10.1016/j.tcs.2007.02.047

Miltersen, P. B. (2007). The Computational Complexity of One-dimensional Sandpiles. Theory of Computing Systems, Volume 41(1), 119-125. https://doi.org/10.1007/s00224-006-1341-8

Hansen, K. A., Miltersen, P. B. & Vinay, V. (2006). Circuits on Cylinders. Computational Complexity, 15(1), 62-81. https://doi.org/10.1007/s00037-006-0207-4

Miltersen, P. B. (2006). Computing sequential equilibria for two-player games. In Proc. 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'06) (pp. 107-116). ACM-SIAM.

Miltersen, P. B. & Sørensen, T. B. (2006). Computing Sequential Equilibria for Two-Player Games. In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms (1 ed., pp. 107-116). Association for Computing Machinery.

Hansen, K. A. (2006). Constant Width and Constant Depth Computation.

Hansen, K. A. (2006). Constant Width Planar Computation Characterizes ACC⁰. Theory of Computing Systems, 39(1), 79-92. https://doi.org/10.1007/s00224-005-1258-7

Kristensen, J. T. & Miltersen, P. B. (2006). Finding small OBDDs for incompletely specified truth tables is hard. Electronic Colloquium on Computational Complexity, (TR06-004), 1-6. http://eccc.hpi-web.de/eccc-reports/2006/TR06-004/index.html

Miltersen, P. B. & Kristensen, J. T. (2006). Finding small OBDDs for incompletely specified truth tables is hard. In D. Z. Chen & D. T. Lee (Eds.), Computing and Combinatorics: 12th Annual International Conference, COCOON 2006, Taipei, Taiwan, August 15-18, 2006. Proceedings (pp. 489-496). Springer. https://doi.org/10.1007/11809678_51

Hansen, K. A. (2006). Lower Bounds for Circuits with Few Modular Gates using Exponential Sums. Electronic Colloquium on Computational Complexity, 13(79). http://eccc.hpi-web.de/eccc-reports/2006/TR06-079/index.html

Hansen, K. A. (2006). On Modular Counting with Polynomials. In 21st Annual IEEE Conference on Computational Complexity (CCC'06) (pp. 202-212). IEEE Computer Society Press. https://doi.org/10.1109/CCC.2006.29

Miltersen, P. B., Kjeldgaard-Pedersen, J., Burgisser, P. & Allender, E. (2006). On the Complexity of Numerical Analysis. In Proceedings of the 21st Annual IEEE Conference on Computational Complexity (pp. 331-339). IEEE Computer Society Press.

Miltersen, P. B. & Vinodchandran, N. V. (2005). Derandomizing Arthur-Merlin Games using Hitting Sets. Computational Complexity, 14(3), 256-279. https://doi.org/10.1007/s00037-005-0197-7

Hansen, K. A. & Chattopadhyay, A. (2005). Lower Bounds for Circuits with Few Modular and Symmetric Gates. In L. Caires, G. F. Italiano, L. Monteiro, C. Palamidessi & M. Yung (Eds.), Automata, Languages and Programming: 32nd International Colloquium, ICALP 2005, Lisbon, Portugal, July 11-15, 2005. Proceedings (pp. 994-1005). Springer. https://doi.org/10.1007/11523468_80

Miltersen, P. B. (2005). Lower bounds on the size of rank and selection indexes. In Proceedings of the Symposium on Discrete Algorithms (pp. 11-12). Society for Industrial and Applied Mathematics.

Miltersen, P. B., Radhakrishnan, J. & Wegener, I. (2005). On converting CNF to DNF. Theoretical Computer Science, 347, 325-335.

Allender, E., Bürgisser, P., Kjeldgaard-Pedersen, J. & Miltersen, P. B. (2005). On the Complexity of Numerical Analysis. Electronic Colloquium on Computational Complexity, (TR05-037), 1-12.

Frandsen, G. S. & Miltersen, P. B. (2005). Reviewing Bounds on the Circuit Size of the Hardest Functions. Information Processing Letters, 95(2), 354-357. https://doi.org/10.1016/j.ipl.2005.03.009

Miltersen, P. B. (2005). The Computational Complexity of One-Dimensional Sandpiles. In S. B. Cooper, B. Löwe & L. Torenvliet (Eds.), New Computational Paradigms: First Conference on Computability in Europe, CiE 2005, Amsterdam, The Netherlands, June 8-12, 2005. Proceedings (pp. 342-350). Springer. https://doi.org/10.1007/11494645_42

Hansen, K. A. (2004). Constant Width Planar Computation Characterizes ACC⁰. In V. Diekert & M. Habib (Eds.), STACS 2004: 21st Annual Symposium on Theoretical Aspects of Computer Science, Montpellier, France, March 25-27, 2004. Proceedings (pp. 44-55). Springer. https://doi.org/10.1007/978-3-540-24749-4_5

Hansen, K. A. & Miltersen, P. B. (2004). Some Meet-in-the-middle Circuit Lower Bounds. In J. Fiala, V. Koubek & J. Kratochvil (Eds.), Mathematical Foundations of Computer Science 2004: 29th International Symposium, MFCS 2004, Prague, Czech Republic, August 22-27, 2004. Proceedings (pp. 334-345). Springer. https://doi.org/10.1007/978-3-540-28629-5_24

Hansen, K. A., Miltersen, P. B. & Vinay, V. (2003). Circuits on Cylinders. In Fundamentals of Computation Theory (pp. 171-182). Springer. https://doi.org/10.1007/978-3-540-45077-1_17

Miltersen, P. B., Radhakrishnan, J. & Wegener, I. (2003). On converting CNF to DNF. In B. Rovan & P. Vojtás (Eds.), Mathematical Foundations of Computer Science 2003: 28th International Symposium, MFCS 2003, Bratislava, Slovakia, August 25-29, 2003, Proceedings (pp. 612-621). Springer. https://doi.org/10.1007/978-3-540-45138-9_55

Gal, A. & Miltersen, P. B. (2003). The Cell Probe Complexity of Succinct Data Structures. In J. C. M. Baeten, J. K. Lenstra, J. Parrow & G. J. Wöeginger (Eds.), Automata, Languages and Programming: 30th International Colloquium, ICALP 2003 Eindhoven, The Netherlands, June 30 - July 4, 2003 Proceedings (pp. 442-453). Springer. https://doi.org/10.1007/3-540-45061-0_28

Buhrman, H., Miltersen, P. B., Radhakrishnan, J. & Venkatesh, S. (2002). Are Bitvectors Optimal? S I A M Journal on Computing, 31(6), 1723-1744. https://doi.org/10.1137/S0097539702405292

Hansen, K. A., Miltersen, P. B. & Vinay, V. (2002). Circuits on Cylinders. Electronic Colloquium on Computational Complexity, (TR02-066).

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

Hagerup, T., Miltersen, P. B. & Pagh, R. (2001). Deterministic Dictionaries. Journal of Algorithms, 41, 69-85.

Hagerup, T., Miltersen, P. B. & Pagh, R. (2001). Deterministic Dictionaries. J. Algorithms, 41(1), 69-85.

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

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

Displaying results 151 to 200 out of 224

Sort by: Date | Author | Title

Revised 01.09.2025