Please note: This is a beta version of the new dblp website.
You can find the classic dblp view of this page here.
You can find the classic dblp view of this page here.
Peter Bro Miltersen
2010 – today
- 2013
[j25]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)- [c59]
- [c58]Thomas Dueholm Hansen, Rasmus Ibsen-Jensen, Peter Bro Miltersen: A Faster Algorithm for Solving One-Clock Priced Timed Games. CONCUR 2013: 531-545
- [c57]Gil Cohen, Ivan Bjerre Damgård, Yuval Ishai, Jonas Kölker, Peter Bro Miltersen, Ran Raz, Ron D. Rothblum: Efficient Multiparty Protocols via Log-Depth Threshold Formulae - (Extended Abstract). CRYPTO (2) 2013: 185-202
- [c56]Søren Kristoffer Stiil Frederiksen, Peter Bro Miltersen: Monomial Strategies for Concurrent Reachability Games and Other Stochastic Games. RP 2013: 122-134
- [i22]Aris Filos-Ratsikas, Peter Bro Miltersen: Truthful approximations to range voting. CoRR abs/1307.1766 (2013)
- [i21]Gil Cohen, Ivan Bjerre Damgård, Yuval Ishai, Jonas Kölker, Peter Bro Miltersen, Ran Raz, Ron Rothblum: Efficient Multiparty Protocols via Log-Depth Threshold Formulae. Electronic Colloquium on Computational Complexity (ECCC) 20: 107 (2013)
- [i20]Gil Cohen, Ivan Bjerre Damgård, Yuval Ishai, Jonas Kölker, Peter Bro Miltersen, Ran Raz, Ron D. Rothblum: Efficient Multiparty Protocols via Log-Depth Threshold Formulae. IACR Cryptology ePrint Archive 2013: 480 (2013)
- 2012
- [j24]Daniel Andersson, Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, Troels Bjerre Sørensen: Deterministic Graphical Games Revisited. J. Log. Comput. 22(2): 165-178 (2012)
- [c55]Rasmus Ibsen-Jensen, Peter Bro Miltersen: Solving Simple Stochastic Games with Few Coin Toss Positions. ESA 2012: 636-647
- [c54]
- [c53]Peter Bro Miltersen, Or Sheffet: Send mixed signals: earn more, work less. ACM Conference on Electronic Commerce 2012: 234-247
- [i19]Thomas Dueholm Hansen, Rasmus Ibsen-Jensen, Peter Bro Miltersen: A Faster Algorithm for Solving One-Clock Priced Timed Games. CoRR abs/1201.3498 (2012)
- [i18]Peter Bro Miltersen, Or Sheffet: Send Mixed Signals -- Earn More, Work Less. CoRR abs/1202.1483 (2012)
- [i17]Kristoffer Arnsfelt Hansen, Michal Koucký, Niels Lauritzen, Peter Bro Miltersen, Elias P. Tsigaridas: Exact Algorithms for Solving Stochastic Games. CoRR abs/1202.3898 (2012)
- [i16]Simina Brânzei, Clara Forero, Kate Larson, Peter Bro Miltersen: Equilibria of Chinese Auctions. CoRR abs/1208.0296 (2012)
- [i15]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)
- 2011
- [c52]Kristoffer Arnsfelt Hansen, Rasmus Ibsen-Jensen, Peter Bro Miltersen: The Complexity of Solving Reachability Games Using Value and Strategy Iteration. CSR 2011: 77-90
- [c51]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
- [c50]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
- [i14]Rasmus Ibsen-Jensen, Peter Bro Miltersen: Solving simple stochastic games with few coin toss positions. CoRR abs/1112.5255 (2011)
- 2010
- [c49]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
- [i13]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)
- [i12]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)
2000 – 2009
- 2009
- [j23]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)
- [c48]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
- [c47]Peter Bro Miltersen, Jesper Buus Nielsen, Nikos Triandopoulos: Privacy-Enhancing Auctions Using Rational Cryptography. CRYPTO 2009: 541-558
- [c46]Daniel Andersson, Peter Bro Miltersen: The Complexity of Solving Stochastic Games on Graphs. ISAAC 2009: 112-121
- [c45]Kristoffer Arnsfelt Hansen, Oded Lachish, Peter Bro Miltersen: Hilbert's Thirteenth Problem and Circuit Complexity. ISAAC 2009: 153-162
- [c44]Kristoffer Arnsfelt Hansen, Michal Koucký, Peter Bro Miltersen: Winning Concurrent Reachability Games Requires Doubly-Exponential Patience. LICS 2009: 332-341
- [e2]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
- 2008
- [j22]Peter Bro Miltersen: Special Issue: "Conference on Computational Complexity 2007" Guest Editor's Foreword. Computational Complexity 17(2): 147-148 (2008)
- [c43]Thomas Dueholm Hansen, Peter Bro Miltersen, Troels Bjerre Sørensen: On Range of Skill. AAAI 2008: 277-282
- [c42]Daniel Andersson, Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, Troels Bjerre Sørensen: Deterministic Graphical Games Revisited. CiE 2008: 1-10
- [c41]Peter Bro Miltersen, Troels Bjerre Sørensen: Fast algorithms for finding proper strategies in game trees. SODA 2008: 874-883
- [c40]Kristoffer Arnsfelt Hansen, Thomas Dueholm Hansen, Peter Bro Miltersen, Troels Bjerre Sørensen: Approximability and Parameterized Complexity of Minmax Values. WINE 2008: 684-695
- [e1]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
- [i11]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)
- [i10]Vladimir Gurvich, Peter Bro Miltersen: On the computational complexity of solving stochastic mean-payoff games. CoRR abs/0812.0486 (2008)
- [i9]
- [i8]Peter Bro Miltersen, Jesper Buus Nielsen, Nikos Triandopoulos: Privacy-Enhancing First-Price Auctions Using Rational Cryptography. IACR Cryptology ePrint Archive 2008: 418 (2008)
- 2007
- [j21]Peter Bro Miltersen: The Computational Complexity of One-Dimensional Sandpiles. Theory Comput. Syst. 41(1): 119-125 (2007)
- [j20]Anna Gál, Peter Bro Miltersen: The cell probe complexity of succinct data structures. Theor. Comput. Sci. 379(3): 405-417 (2007)
- [c39]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
- [c38]Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, Troels Bjerre Sørensen: Finding Equilibria in Games of No Chance. COCOON 2007: 274-284
- [c37]P. Jean-Jacques Herings, Marcin Jurdzinski, Peter Bro Miltersen, Éva Tardos, Bernhard von Stengel: 07471 Abstracts Collection - Equilibrium Computation. Equilibrium Computation 2007
- [i7]Daniel Andersson, Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, Troels Bjerre Sørensen: Simple Recursive Games. CoRR abs/0711.1055 (2007)
- 2006
- [j19]Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, V. Vinay: Circuits on cylinders. Computational Complexity 15(1): 62-81 (2006)
- [c36]Peter Bro Miltersen, Troels Bjerre Sørensen: Computing Proper Equilibria of Zero-Sum Games. Computers and Games 2006: 200-211
- [c35]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
- [c34]Jesper Torp Kristensen, Peter Bro Miltersen: Finding Small OBDDs for Incompletely Specified Truth Tables Is Hard. COCOON 2006: 489-496
- [c33]Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, Peter Bro Miltersen: On the Complexity of Numerical Analysis. Complexity of Boolean Functions 2006
- [c32]Anna Gál, Peter Bro Miltersen: The Cell Probe Complexity of Succinct Data Structures. Complexity of Boolean Functions 2006
- [c31]Peter Bro Miltersen, Troels Bjerre Sørensen: Computing sequential equilibria for two-player games. SODA 2006: 107-116
- [i6]Jesper Torp Kristensen, Peter Bro Miltersen: Finding small OBDDs for incompletely specified truth tables is hard. Electronic Colloquium on Computational Complexity (ECCC)(004) (2006)
- 2005
- [j18]Peter Bro Miltersen, N. V. Vinodchandran: Derandomizing Arthur-Merlin Games using Hitting Sets. Computational Complexity 14(3): 256-279 (2005)
- [j17]Gudmund Skovbjerg Frandsen, Peter Bro Miltersen: Reviewing bounds on the circuit size of the hardest functions. Inf. Process. Lett. 95(2): 354-357 (2005)
- [j16]Peter Bro Miltersen, Jaikumar Radhakrishnan, Ingo Wegener: On converting CNF to DNF. Theor. Comput. Sci. 347(1-2): 325-335 (2005)
- [c30]
- [c29]
- [i5]Gudmund Skovbjerg Frandsen, Peter Bro Miltersen: Reviewing Bounds on the Circuit Size of the Hardest Functions. Electronic Colloquium on Computational Complexity (ECCC)(032) (2005)
- [i4]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)
- 2004
- [c28]Kristoffer Arnsfelt Hansen, Peter Bro Miltersen: Some Meet-in-the-Middle Circuit Lower Bounds. MFCS 2004: 334-345
- 2003
- [c27]
- [c26]Anna Gál, Peter Bro Miltersen: The Cell Probe Complexity of Succinct Data Structures. ICALP 2003: 332-344
- [c25]Peter Bro Miltersen, Jaikumar Radhakrishnan, Ingo Wegener: On Converting CNF to DNF. MFCS 2003: 612-621
- [i3]Peter Bro Miltersen, Jaikumar Radhakrishnan, Ingo Wegener: On Converting CNF to DNF. Electronic Colloquium on Computational Complexity (ECCC) 10(017) (2003)
- 2002
- [j15]Harry Buhrman, Peter Bro Miltersen, Jaikumar Radhakrishnan, Srinivasan Venkatesh: Are Bitvectors Optimal? SIAM J. Comput. 31(6): 1723-1744 (2002)
- [i2]Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, V. Vinay: Circuits on Cylinders. Electronic Colloquium on Computational Complexity (ECCC)(066) (2002)
- 2001
- [j14]Gudmund Skovbjerg Frandsen, Johan P. Hansen, Peter Bro Miltersen: Lower Bounds for Dynamic Algebraic Problems. Inf. Comput. 171(2): 333-349 (2001)
- [j13]Torben Hagerup, Peter Bro Miltersen, Rasmus Pagh: Deterministic Dictionaries. J. Algorithms 41(1): 69-85 (2001)
- [c24]
- 2000
- [c23]Harry Buhrman, Sophie Laplante, Peter Bro Miltersen: New Bounds for the Language Compression Problem. IEEE Conference on Computational Complexity 2000: 126-130
- [c22]Peter Bro Miltersen: On the Shannon Function for Partially Defined Boolean Functions. ICALP Satellite Workshops 2000: 253-258
- [c21]Harry Buhrman, Peter Bro Miltersen, Jaikumar Radhakrishnan, Srinivasan Venkatesh: Are bitvectors optimal? STOC 2000: 449-458
1990 – 1999
- 1999
- [j12]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)
- [j11]Noga Alon, Martin Dietzfelbinger, Peter Bro Miltersen, Erez Petrank, Gábor Tardos: Linear Hash Functions. J. ACM 46(5): 667-683 (1999)
- [j10]
- [j9]Arne Andersson, Peter Bro Miltersen, Mikkel Thorup: Fusion Trees can be Implemented with AC0 Instructions Only. Theor. Comput. Sci. 215(1-2): 337-344 (1999)
- [c20]David A. Mix Barrington, Chi-Jen Lu, Peter Bro Miltersen, Sven Skyum: On Monotone Planar Circuits. IEEE Conference on Computational Complexity 1999: 24-
- [c19]Peter Bro Miltersen, N. V. Vinodchandran, Osamu Watanabe: Super-Polynomial Versus Half-Exponential Circuit Size in the Exponential Hierarchy. COCOON 1999: 210-220
- [c18]Peter Bro Miltersen, N. V. Vinodchandran: Derandomizing Arthur-Merlin Games Using Hitting Sets. FOCS 1999: 71-80
- [c17]Gudmund Skovbjerg Frandsen, Johan P. Hansen, Peter Bro Miltersen: Lower Bounds for Dynamic Algebraic Problems. STACS 1999: 362-372
- 1998
- [j8]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)
- [c16]Peter Bro Miltersen: Error Correcting Codes, Perfect Hashing Circuits, and Deterministic Dynamic Dictionaries. SODA 1998: 556-563
- [c15]David A. Mix Barrington, Chi-Jen Lu, Peter Bro Miltersen, Sven Skyum: Searching Constant Width Mazes Captures the AC0 Hierarchy. STACS 1998: 73-83
- 1997
- [j7]Gudmund Skovbjerg Frandsen, Peter Bro Miltersen, Sven Skyum: Dynamic word problems. J. ACM 44(2): 257-271 (1997)
- [c14]Noga Alon, Martin Dietzfelbinger, Peter Bro Miltersen, Erez Petrank, Gábor Tardos: Is Linear Hashing Good? STOC 1997: 465-474
- [c13]Andrej Brodnik, Peter Bro Miltersen, J. Ian Munro: Trans-Dichotomous Algorithms Without Multiplication - Some Upper and Lower Bounds. WADS 1997: 426-439
- [i1]David A. Mix Barrington, Chi-Jen Lu, Peter Bro Miltersen, Sven Skyum: Searching constant width mazes captures the AC0 hierarchy. Electronic Colloquium on Computational Complexity (ECCC) 4(44) (1997)
- 1996
- [j6]Peter Bro Miltersen, Mike Paterson, Jun Tarui: The Asymptotic Complexity of Merging Networks. J. ACM 43(1): 147-165 (1996)
- [j5]Steven M. Kautz, Peter Bro Miltersen: Relative to a Random Oracle, NP Is Not Small. J. Comput. Syst. Sci. 53(2): 235-250 (1996)
- [c12]Arne Andersson, Peter Bro Miltersen, Søren Riis, Mikkel Thorup: Static Dictionaries on AC0 RAMs: Query Time Theta(sqrt(log n/log log n)) is Necessary and Sufficient. FOCS 1996: 441-450
- [c11]Peter Bro Miltersen: Lower Bounds for Static Dictionaries on RAMs with Bit Operations But No Multiplication. ICALP 1996: 442-453
- 1995
- [j4]Peter Bro Miltersen: On the Cell Probe Complexity of Polynomial Evaluation. Theor. Comput. Sci. 143(1): 167-174 (1995)
- [c10]Peter Bro Miltersen, Noam Nisan, Shmuel Safra, Avi Wigderson: On data structures and asymmetric communication complexity. STOC 1995: 103-111
- [c9]Gudmund Skovbjerg Frandsen, Thore Husfeldt, Peter Bro Miltersen, Theis Rauhe, Søren Skyum: Dynamic Algorithms for the Dyck Languages. WADS 1995: 98-108
- [c8]Faith E. Fich, Peter Bro Miltersen: Tables Should Be Sorted (On Random Access Machines). WADS 1995: 482-493
- 1994
- [j3]Peter Bro Miltersen, Sairam Subramanian, Jeffrey Scott Vitter, Roberto Tamassia: Complexity Models for Incremental Computation. Theor. Comput. Sci. 130(1): 203-236 (1994)
- [c7]Steven M. Kautz, Peter Bro Miltersen: Relative to a Random Oracle, NP is Not Small. Structure in Complexity Theory Conference 1994: 162-174
- [c6]Peter Bro Miltersen: Lower bounds for union-split-find related problems on random access machines. STOC 1994: 625-634
- 1993
- [j2]
- [c5]Gudmund Skovbjerg Frandsen, Peter Bro Miltersen, Sven Skyum: Dynamic Word Problems. FOCS 1993: 470-479
- [c4]Gudmund Skovbjerg Frandsen, Peter Bro Miltersen, Sven Skyum: The Complexity of Finding Replicas Using Equality Tests. MFCS 1993: 463-472
- [c3]
- 1992
- [j1]Peter Bro Miltersen: Circuit Depth Relative to a Random Oracle. Inf. Process. Lett. 42(6): 295-298 (1992)
- [c2]Peter Bro Miltersen, Mike Paterson, Jun Tarui: The Asymptotic Complexity of Merging Networks. FOCS 1992: 236-246
- 1991
- [c1]Peter Bro Miltersen: The Complexity of Malign Ensembles. Structure in Complexity Theory Conference 1991: 164-171
Coauthor Index
data released under the ODC-BY 1.0 license. See also our legal information page
last updated on 2013-10-02 11:13 CEST by the dblp team