Peter Bro Miltersen

Thomas Dueholm Hansen, Peter Bro Miltersen, Uri Zwick: Strategy Iteration Is Strongly Polynomial for 2-Player Turn-Based Stochastic Games with a Constant Discount Factor. J. ACM 60(1): 1 (2013)

Daniel Andersson, Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, Troels Bjerre Sørensen: Deterministic Graphical Games Revisited. J. Log. Comput. 22(2): 165-178 (2012)

Rasmus Ibsen-Jensen, Peter Bro Miltersen: Solving Simple Stochastic Games with Few Coin Toss Positions. ESA 2012: 636-647

Peter Bro Miltersen: Recent Results on Howard's Algorithm. MEMICS 2012: 53-56

Peter Bro Miltersen, Or Sheffet: Send mixed signals: earn more, work less. ACM Conference on Electronic Commerce 2012: 234-247

Thomas Dueholm Hansen, Rasmus Ibsen-Jensen, Peter Bro Miltersen: A Faster Algorithm for Solving One-Clock Priced Timed Games. CoRR abs/1201.3498 (2012)

Peter Bro Miltersen, Or Sheffet: Send Mixed Signals -- Earn More, Work Less. CoRR abs/1202.1483 (2012)

Kristoffer Arnsfelt Hansen, Michal Koucký, Niels Lauritzen, Peter Bro Miltersen, Elias P. Tsigaridas: Exact Algorithms for Solving Stochastic Games. CoRR abs/1202.3898 (2012)

Simina Brânzei, Clara Forero, Kate Larson, Peter Bro Miltersen: Equilibria of Chinese Auctions. CoRR abs/1208.0296 (2012)

Ivan Bjerre Damgård, Jonas Kölker, Peter Bro Miltersen: Secret Sharing and Secure Computing from Monotone Formulae. IACR Cryptology ePrint Archive 2012: 536 (2012)

Kristoffer Arnsfelt Hansen, Rasmus Ibsen-Jensen, Peter Bro Miltersen: The Complexity of Solving Reachability Games Using Value and Strategy Iteration. CSR 2011: 77-90

Thomas Dueholm Hansen, Peter Bro Miltersen, Uri Zwick: Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor. ICS 2011: 253-263

Kristoffer Arnsfelt Hansen, Michal Koucký, Niels Lauritzen, Peter Bro Miltersen, Elias P. Tsigaridas: Exact algorithms for solving stochastic games: extended abstract. STOC 2011: 205-214

Rasmus Ibsen-Jensen, Peter Bro Miltersen: Solving simple stochastic games with few coin toss positions. CoRR abs/1112.5255 (2011)

Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, Troels Bjerre Sørensen: The Computational Complexity of Trembling Hand Perfection and Other Equilibrium Refinements. SAGT 2010: 198-209

Kristoffer Arnsfelt Hansen, Rasmus Ibsen-Jensen, Peter Bro Miltersen: The complexity of solving reachability games using value and strategy iteration. CoRR abs/1007.1812 (2010)

Thomas Dueholm Hansen, Peter Bro Miltersen, Uri Zwick: Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor. CoRR abs/1008.0530 (2010)

Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, Peter Bro Miltersen: On the Complexity of Numerical Analysis. SIAM J. Comput. 38(5): 1987-2006 (2009)

Guillaume Escamocher, Peter Bro Miltersen, Rocio Santillan R.: Existence and computation of equilibria of first-price auctions with integral valuations and bids. AAMAS (2) 2009: 1227-1228

Peter Bro Miltersen, Jesper Buus Nielsen, Nikos Triandopoulos: Privacy-Enhancing Auctions Using Rational Cryptography. CRYPTO 2009: 541-558

Daniel Andersson, Peter Bro Miltersen: The Complexity of Solving Stochastic Games on Graphs. ISAAC 2009: 112-121

Kristoffer Arnsfelt Hansen, Oded Lachish, Peter Bro Miltersen: Hilbert's Thirteenth Problem and Circuit Complexity. ISAAC 2009: 153-162

Kristoffer Arnsfelt Hansen, Michal Koucký, Peter Bro Miltersen: Winning Concurrent Reachability Games Requires Doubly-Exponential Patience. LICS 2009: 332-341

Mogens Nielsen, Antonín Kucera, Peter Bro Miltersen, Catuscia Palamidessi, Petr Tuma, Frank D. Valencia (Eds.): SOFSEM 2009: Theory and Practice of Computer Science, 35th Conference on Current Trends in Theory and Practice of Computer Science, Spindleruv Mlýn, Czech Republic, January 24-30, 2009. Proceedings. Lecture Notes in Computer Science 5404, Springer 2009, isbn 978-3-540-95890-1

Peter Bro Miltersen: Special Issue: "Conference on Computational Complexity 2007" Guest Editor's Foreword. Computational Complexity 17(2): 147-148 (2008)

Thomas Dueholm Hansen, Peter Bro Miltersen, Troels Bjerre Sørensen: On Range of Skill. AAAI 2008: 277-282

Daniel Andersson, Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, Troels Bjerre Sørensen: Deterministic Graphical Games Revisited. CiE 2008: 1-10

Peter Bro Miltersen, Troels Bjerre Sørensen: Fast algorithms for finding proper strategies in game trees. SODA 2008: 874-883

Kristoffer Arnsfelt Hansen, Thomas Dueholm Hansen, Peter Bro Miltersen, Troels Bjerre Sørensen: Approximability and Parameterized Complexity of Minmax Values. WINE 2008: 684-695

P. Jean-Jacques Herings, Marcin Jurdzinski, Peter Bro Miltersen, Éva Tardos, Bernhard von Stengel (Eds.): Equilibrium Computation, 18.11. - 23.11.2007. Dagstuhl Seminar Proceedings 07471, Internationales Begegnungs- und Forschungszentrum fuer Informatik (IBFI), Schloss Dagstuhl, Germany 2008

Kristoffer Arnsfelt Hansen, Thomas Dueholm Hansen, Peter Bro Miltersen, Troels Bjerre Sørensen: Approximability and parameterized complexity of minmax values. CoRR abs/0806.4344 (2008)

Vladimir Gurvich, Peter Bro Miltersen: On the computational complexity of solving stochastic mean-payoff games. CoRR abs/0812.0486 (2008)

Peter Bro Miltersen: Trembling hand perfection is NP-hard. CoRR abs/0812.0492 (2008)

Peter Bro Miltersen, Jesper Buus Nielsen, Nikos Triandopoulos: Privacy-Enhancing First-Price Auctions Using Rational Cryptography. IACR Cryptology ePrint Archive 2008: 418 (2008)

Peter Bro Miltersen: The Computational Complexity of One-Dimensional Sandpiles. Theory Comput. Syst. 41(1): 119-125 (2007)

Anna Gál, Peter Bro Miltersen: The cell probe complexity of succinct data structures. Theor. Comput. Sci. 379(3): 405-417 (2007)

Peter Bro Miltersen, Troels Bjerre Sørensen: A near-optimal strategy for a heads-up no-limit Texas Hold'em poker tournament. AAMAS 2007: 191

Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, Troels Bjerre Sørensen: Finding Equilibria in Games of No Chance. COCOON 2007: 274-284

P. Jean-Jacques Herings, Marcin Jurdzinski, Peter Bro Miltersen, Éva Tardos, Bernhard von Stengel: 07471 Abstracts Collection - Equilibrium Computation. Equilibrium Computation 2007

Daniel Andersson, Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, Troels Bjerre Sørensen: Simple Recursive Games. CoRR abs/0711.1055 (2007)

Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, V. Vinay: Circuits on cylinders. Computational Complexity 15(1): 62-81 (2006)

Peter Bro Miltersen, Troels Bjerre Sørensen: Computing Proper Equilibria of Zero-Sum Games. Computers and Games 2006: 200-211

Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, Peter Bro Miltersen: On the Complexity of Numerical Analysis. IEEE Conference on Computational Complexity 2006: 331-339

Jesper Torp Kristensen, Peter Bro Miltersen: Finding Small OBDDs for Incompletely Specified Truth Tables Is Hard. COCOON 2006: 489-496

Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, Peter Bro Miltersen: On the Complexity of Numerical Analysis. Complexity of Boolean Functions 2006

Anna Gál, Peter Bro Miltersen: The Cell Probe Complexity of Succinct Data Structures. Complexity of Boolean Functions 2006

Peter Bro Miltersen, Troels Bjerre Sørensen: Computing sequential equilibria for two-player games. SODA 2006: 107-116

Jesper Torp Kristensen, Peter Bro Miltersen: Finding small OBDDs for incompletely specified truth tables is hard. Electronic Colloquium on Computational Complexity (ECCC)(004) (2006)

Peter Bro Miltersen, N. V. Vinodchandran: Derandomizing Arthur-Merlin Games using Hitting Sets. Computational Complexity 14(3): 256-279 (2005)

Gudmund Skovbjerg Frandsen, Peter Bro Miltersen: Reviewing bounds on the circuit size of the hardest functions. Inf. Process. Lett. 95(2): 354-357 (2005)

Peter Bro Miltersen, Jaikumar Radhakrishnan, Ingo Wegener: On converting CNF to DNF. Theor. Comput. Sci. 347(1-2): 325-335 (2005)

Peter Bro Miltersen: The Computational Complexity of One-Dimensional Sandpiles. CiE 2005: 342-348

Peter Bro Miltersen: Lower bounds on the size of selection and rank indexes. SODA 2005: 11-12

Gudmund Skovbjerg Frandsen, Peter Bro Miltersen: Reviewing Bounds on the Circuit Size of the Hardest Functions. Electronic Colloquium on Computational Complexity (ECCC)(032) (2005)

Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, Peter Bro Miltersen: On the Complexity of Numerical Analysis. Electronic Colloquium on Computational Complexity (ECCC)(037) (2005)

Kristoffer Arnsfelt Hansen, Peter Bro Miltersen: Some Meet-in-the-Middle Circuit Lower Bounds. MFCS 2004: 334-345

Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, V. Vinay: Circuits on Cylinders. FCT 2003: 171-182

Anna Gál, Peter Bro Miltersen: The Cell Probe Complexity of Succinct Data Structures. ICALP 2003: 332-344

Peter Bro Miltersen, Jaikumar Radhakrishnan, Ingo Wegener: On Converting CNF to DNF. MFCS 2003: 612-621

Peter Bro Miltersen, Jaikumar Radhakrishnan, Ingo Wegener: On Converting CNF to DNF. Electronic Colloquium on Computational Complexity (ECCC) 10(017) (2003)

Harry Buhrman, Peter Bro Miltersen, Jaikumar Radhakrishnan, Srinivasan Venkatesh: Are Bitvectors Optimal? SIAM J. Comput. 31(6): 1723-1744 (2002)

Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, V. Vinay: Circuits on Cylinders. Electronic Colloquium on Computational Complexity (ECCC)(066) (2002)

Gudmund Skovbjerg Frandsen, Johan P. Hansen, Peter Bro Miltersen: Lower Bounds for Dynamic Algebraic Problems. Inf. Comput. 171(2): 333-349 (2001)

Torben Hagerup, Peter Bro Miltersen, Rasmus Pagh: Deterministic Dictionaries. J. Algorithms 41(1): 69-85 (2001)

Mary Cryan, Peter Bro Miltersen: On Pseudorandom Generators in NC. MFCS 2001: 272-284

Harry Buhrman, Sophie Laplante, Peter Bro Miltersen: New Bounds for the Language Compression Problem. IEEE Conference on Computational Complexity 2000: 126-130

Peter Bro Miltersen: On the Shannon Function for Partially Defined Boolean Functions. ICALP Satellite Workshops 2000: 253-258

Harry Buhrman, Peter Bro Miltersen, Jaikumar Radhakrishnan, Srinivasan Venkatesh: Are bitvectors optimal? STOC 2000: 449-458

Sven Skyum, Gudmund Skovbjerg Frandsen, Peter Bro Miltersen, Peter G. Binderup: The Complexity of Identifying Large Equivalence Classes. Fundam. Inform. 38(1-2): 25-37 (1999)

Noga Alon, Martin Dietzfelbinger, Peter Bro Miltersen, Erez Petrank, Gábor Tardos: Linear Hash Functions. J. ACM 46(5): 667-683 (1999)

Jens Lagergren, Peter Bro Miltersen: Guest Editors' Foreword. Nord. J. Comput. 6(2): 135-136 (1999)

Arne Andersson, Peter Bro Miltersen, Mikkel Thorup: Fusion Trees can be Implemented with AC⁰ Instructions Only. Theor. Comput. Sci. 215(1-2): 337-344 (1999)

David A. Mix Barrington, Chi-Jen Lu, Peter Bro Miltersen, Sven Skyum: On Monotone Planar Circuits. IEEE Conference on Computational Complexity 1999: 24-

Peter Bro Miltersen, N. V. Vinodchandran, Osamu Watanabe: Super-Polynomial Versus Half-Exponential Circuit Size in the Exponential Hierarchy. COCOON 1999: 210-220

Peter Bro Miltersen, N. V. Vinodchandran: Derandomizing Arthur-Merlin Games Using Hitting Sets. FOCS 1999: 71-80

Gudmund Skovbjerg Frandsen, Johan P. Hansen, Peter Bro Miltersen: Lower Bounds for Dynamic Algebraic Problems. STACS 1999: 362-372

Peter Bro Miltersen, Noam Nisan, Shmuel Safra, Avi Wigderson: On Data Structures and Asymmetric Communication Complexity. J. Comput. Syst. Sci. 57(1): 37-49 (1998)

Peter Bro Miltersen: Error Correcting Codes, Perfect Hashing Circuits, and Deterministic Dynamic Dictionaries. SODA 1998: 556-563

David A. Mix Barrington, Chi-Jen Lu, Peter Bro Miltersen, Sven Skyum: Searching Constant Width Mazes Captures the AC⁰ Hierarchy. STACS 1998: 73-83

Gudmund Skovbjerg Frandsen, Peter Bro Miltersen, Sven Skyum: Dynamic word problems. J. ACM 44(2): 257-271 (1997)

Noga Alon, Martin Dietzfelbinger, Peter Bro Miltersen, Erez Petrank, Gábor Tardos: Is Linear Hashing Good? STOC 1997: 465-474

Andrej Brodnik, Peter Bro Miltersen, J. Ian Munro: Trans-Dichotomous Algorithms Without Multiplication - Some Upper and Lower Bounds. WADS 1997: 426-439

David A. Mix Barrington, Chi-Jen Lu, Peter Bro Miltersen, Sven Skyum: Searching constant width mazes captures the AC⁰ hierarchy. Electronic Colloquium on Computational Complexity (ECCC) 4(44) (1997)

Peter Bro Miltersen, Mike Paterson, Jun Tarui: The Asymptotic Complexity of Merging Networks. J. ACM 43(1): 147-165 (1996)

Steven M. Kautz, Peter Bro Miltersen: Relative to a Random Oracle, NP Is Not Small. J. Comput. Syst. Sci. 53(2): 235-250 (1996)

Arne Andersson, Peter Bro Miltersen, Søren Riis, Mikkel Thorup: Static Dictionaries on AC⁰ RAMs: Query Time Theta(sqrt(log n/log log n)) is Necessary and Sufficient. FOCS 1996: 441-450

Peter Bro Miltersen: Lower Bounds for Static Dictionaries on RAMs with Bit Operations But No Multiplication. ICALP 1996: 442-453

Peter Bro Miltersen: On the Cell Probe Complexity of Polynomial Evaluation. Theor. Comput. Sci. 143(1): 167-174 (1995)

Peter Bro Miltersen, Noam Nisan, Shmuel Safra, Avi Wigderson: On data structures and asymmetric communication complexity. STOC 1995: 103-111

Gudmund Skovbjerg Frandsen, Thore Husfeldt, Peter Bro Miltersen, Theis Rauhe, Søren Skyum: Dynamic Algorithms for the Dyck Languages. WADS 1995: 98-108

Faith E. Fich, Peter Bro Miltersen: Tables Should Be Sorted (On Random Access Machines). WADS 1995: 482-493

Peter Bro Miltersen, Sairam Subramanian, Jeffrey Scott Vitter, Roberto Tamassia: Complexity Models for Incremental Computation. Theor. Comput. Sci. 130(1): 203-236 (1994)

Steven M. Kautz, Peter Bro Miltersen: Relative to a Random Oracle, NP is Not Small. Structure in Complexity Theory Conference 1994: 162-174

Peter Bro Miltersen: Lower bounds for union-split-find related problems on random access machines. STOC 1994: 625-634

Peter Bro Miltersen: The Complexity of Malign Measures. SIAM J. Comput. 22(1): 147-156 (1993)

Gudmund Skovbjerg Frandsen, Peter Bro Miltersen, Sven Skyum: Dynamic Word Problems. FOCS 1993: 470-479

Gudmund Skovbjerg Frandsen, Peter Bro Miltersen, Sven Skyum: The Complexity of Finding Replicas Using Equality Tests. MFCS 1993: 463-472

Peter Bro Miltersen: The Bit Probe Complexity Measure Revisited. STACS 1993: 662-671

Peter Bro Miltersen: Circuit Depth Relative to a Random Oracle. Inf. Process. Lett. 42(6): 295-298 (1992)

Peter Bro Miltersen, Mike Paterson, Jun Tarui: The Asymptotic Complexity of Merging Networks. FOCS 1992: 236-246

Peter Bro Miltersen: The Complexity of Malign Ensembles. Structure in Complexity Theory Conference 1991: 164-171