Peter Bro Miltersen

131 papers A* 20A 11B 17C 2Misc 4Journal 55Unranked 19
YearRankTypeTitle / Venue / Authors
2023 J jnl
Walrasian pricing in multi-unit auctions.
Artif. Intell.
Simina Brânzei, Aris Filos-Ratsikas, Peter Bro Miltersen, Yulong Zeng
2017 J jnl
Computation of Stackelberg Equilibria of Finite Sequential Games.
ACM Trans. Economics and Comput.
Branislav Bosanský, Simina Brânzei, Kristoffer Arnsfelt Hansen, Troels Bjerre Lund, Peter Bro Miltersen
2017 B conf
Walrasian Pricing in Multi-Unit Auctions.
MFCS
Simina Brânzei, Aris Filos-Ratsikas, Peter Bro Miltersen, Yulong Zeng
2016 J jnl
Envy-Free Pricing in Multi-unit Markets.
CoRR
Simina Brânzei, Aris Filos-Ratsikas, Peter Bro Miltersen, Yulong Zeng
2016 J jnl
Special Section on the Forty-Fifth Annual ACM Symposium on the Theory of Computing (STOC 2013).
SIAM J. Comput.
James Aspnes, Yuval Ishai, Peter Bro Miltersen
2015 A* conf
A Dictatorship Theorem for Cake Cutting.
IJCAI
Simina Brânzei, Peter Bro Miltersen
2015 B conf
Characterization and Computation of Equilibria for Indivisible Goods.
SAGT
Simina Brânzei, Hadi Hosseini, Peter Bro Miltersen
2015 J jnl
Characterization and Computation of Equilibria for Indivisible Goods.
CoRR
Simina Brânzei, Hadi Hosseini, Peter Bro Miltersen
2015 — conf
Computation of Stackelberg Equilibria of Finite Sequential Games.
WINE
Branislav Bosanský, Simina Brânzei, Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, Troels Bjerre Sørensen
2015 J jnl
Computation of Stackelberg Equilibria of Finite Sequential Games.
CoRR
Branislav Bosanský, Simina Brânzei, Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, Troels Bjerre Sørensen
2014 A conf
Semi-algebraic geometry in computational game theory - a consumer's perspective (Invited Talk).
STACS
Peter Bro Miltersen
2014 B conf
The Complexity of Approximating a Trembling Hand Perfect Equilibrium of a Multi-player Game in Strategic Form.
SAGT
Kousha Etessami, Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, Troels Bjerre Sørensen
2014 J jnl
The Complexity of Solving Reachability Games Using Value and Strategy Iteration.
Theory Comput. Syst.
Kristoffer Arnsfelt Hansen, Rasmus Ibsen-Jensen, Peter Bro Miltersen
2014 J jnl
The complexity of approximating a trembling hand perfect equilibrium of a multi-player game in strategic form.
CoRR
Kousha Etessami, Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, Troels Bjerre Sørensen
2014 — conf
Truthful Approximations to Range Voting.
WINE
Aris Filos-Ratsikas, Peter Bro Miltersen
2013 B conf
A Faster Algorithm for Solving One-Clock Priced Timed Games.
CONCUR
Thomas Dueholm Hansen, Rasmus Ibsen-Jensen, Peter Bro Miltersen
2013 B conf
Approximating the Value of a Concurrent Reachability Game in the Polynomial Time Hierarchy.
ISAAC
Søren Kristoffer Stiil Frederiksen, Peter Bro Miltersen
2013 — conf
Efficient Multiparty Protocols via Log-Depth Threshold Formulae - (Extended Abstract).
CRYPTO (2)
Gil Cohen, Ivan Bjerre Damgård, Yuval Ishai, Jonas Kölker, Peter Bro Miltersen, Ran Raz, Ron D. Rothblum
2013 J jnl
Efficient Multiparty Protocols via Log-Depth Threshold Formulae.
Electron. Colloquium Comput. Complex.
Gil Cohen, Ivan Bjerre Damgård, Yuval Ishai, Jonas Kölker, Peter Bro Miltersen, Ran Raz, Ron Rothblum
2013 J jnl
Efficient Multiparty Protocols via Log-Depth Threshold Formulae.
IACR Cryptol. ePrint Arch.
Gil Cohen, Ivan Bjerre Damgård, Yuval Ishai, Jonas Kölker, Peter Bro Miltersen, Ran Raz, Ron D. Rothblum
2013 A conf
Equilibrium analysis in cake cutting.
AAMAS
Simina Brânzei, Peter Bro Miltersen
2013 — conf
Monomial Strategies for Concurrent Reachability Games and Other Stochastic Games.
RP
Søren Kristoffer Stiil Frederiksen, Peter Bro Miltersen
2013 J jnl
Strategy Iteration Is Strongly Polynomial for 2-Player Turn-Based Stochastic Games with a Constant Discount Factor.
J. ACM
Thomas Dueholm Hansen, Peter Bro Miltersen, Uri Zwick
2013 J jnl
Truthful approximations to range voting.
CoRR
Aris Filos-Ratsikas, Peter Bro Miltersen
2012 J jnl
A Faster Algorithm for Solving One-Clock Priced Timed Games
CoRR
Thomas Dueholm Hansen, Rasmus Ibsen-Jensen, Peter Bro Miltersen
2012 J jnl
Deterministic Graphical Games Revisited.
J. Log. Comput.
Daniel Andersson, Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, Troels Bjerre Sørensen
2012 J jnl
Equilibria of Chinese Auctions
CoRR
Simina Brânzei, Clara Forero, Kate Larson, Peter Bro Miltersen
2012 J jnl
Exact Algorithms for Solving Stochastic Games
CoRR
Kristoffer Arnsfelt Hansen, Michal Koucký, Niels Lauritzen, Peter Bro Miltersen, Elias P. Tsigaridas
2012 — conf
Recent Results on Howard's Algorithm.
MEMICS
Peter Bro Miltersen
2012 J jnl
Secret Sharing and Secure Computing from Monotone Formulae.
IACR Cryptol. ePrint Arch.
Ivan Bjerre Damgård, Jonas Kölker, Peter Bro Miltersen
2012 J jnl
Send Mixed Signals -- Earn More, Work Less
CoRR
Peter Bro Miltersen, Or Sheffet
2012 A* conf
Send mixed signals: earn more, work less.
EC
Peter Bro Miltersen, Or Sheffet
2012 A conf
Solving Simple Stochastic Games with Few Coin Toss Positions.
ESA
Rasmus Ibsen-Jensen, Peter Bro Miltersen
2011 A* conf
Exact algorithms for solving stochastic games: extended abstract.
STOC
Kristoffer Arnsfelt Hansen, Michal Koucký, Niels Lauritzen, Peter Bro Miltersen, Elias P. Tsigaridas
2011 J jnl
Solving simple stochastic games with few coin toss positions
CoRR
Rasmus Ibsen-Jensen, Peter Bro Miltersen
2011 A conf
Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor.
ICS
Thomas Dueholm Hansen, Peter Bro Miltersen, Uri Zwick
2011 Misc conf
The Complexity of Solving Reachability Games Using Value and Strategy Iteration.
CSR
Kristoffer Arnsfelt Hansen, Rasmus Ibsen-Jensen, Peter Bro Miltersen
2010 — conf
10171 Abstracts Collection - Equilibrium Computation.
Equilibrium Computation
Edith Elkind, Nimrod Megiddo, Peter Bro Miltersen, Bernhard von Stengel, Vijay V. Vazirani
2010 — ed.
Equilibrium Computation, 25.04. - 30.04.2010
Equilibrium Computation
Edith Elkind, Nimrod Megiddo, Peter Bro Miltersen, Vijay V. Vazirani, Bernhard von Stengel
2010 — conf
Privacy-enhancing auctions using rational cryptography.
BQGT
Peter Bro Miltersen, Jesper Buus Nielsen, Nikos Triandopoulos
2010 J jnl
Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor
CoRR
Thomas Dueholm Hansen, Peter Bro Miltersen, Uri Zwick
2010 B conf
The Computational Complexity of Trembling Hand Perfection and Other Equilibrium Refinements.
SAGT
Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, Troels Bjerre Sørensen
2010 J jnl
The complexity of solving reachability games using value and strategy iteration
CoRR
Kristoffer Arnsfelt Hansen, Rasmus Ibsen-Jensen, Peter Bro Miltersen
2009 — conf
Existence and computation of equilibria of first-price auctions with integral valuations and bids.
AAMAS (2)
Guillaume Escamocher, Peter Bro Miltersen, Rocio Santillan R.
2009 B conf
Hilbert's Thirteenth Problem and Circuit Complexity.
ISAAC
Kristoffer Arnsfelt Hansen, Oded Lachish, Peter Bro Miltersen
2009 J jnl
On the Complexity of Numerical Analysis.
SIAM J. Comput.
Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, Peter Bro Miltersen
2009 A* conf
Privacy-Enhancing Auctions Using Rational Cryptography.
CRYPTO
Peter Bro Miltersen, Jesper Buus Nielsen, Nikos Triandopoulos
2009 B ed.
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
SOFSEM
Mogens Nielsen, Antonín Kucera, Peter Bro Miltersen, Catuscia Palamidessi, Petr Tuma, Frank D. Valencia
2009 B conf
The Complexity of Solving Stochastic Games on Graphs.
ISAAC
Daniel Andersson, Peter Bro Miltersen
2009 A* conf
Winning Concurrent Reachability Games Requires Doubly-Exponential Patience.
LICS
Kristoffer Arnsfelt Hansen, Michal Koucký, Peter Bro Miltersen
2008 — conf
08381 Abstracts Collection - Computational Complexity of Discrete Problems.
Computational Complexity of Discrete Problems
Peter Bro Miltersen, Rüdiger Reischuk, Georg Schnitger, Dieter van Melkebeek
2008 — conf
08381 Executive Summary - Computational Complexity of Discrete Problems.
Computational Complexity of Discrete Problems
Peter Bro Miltersen, Rüdiger Reischuk, Georg Schnitger, Dieter van Melkebeek
2008 — conf
Approximability and Parameterized Complexity of Minmax Values.
WINE
Kristoffer Arnsfelt Hansen, Thomas Dueholm Hansen, Peter Bro Miltersen, Troels Bjerre Sørensen
2008 J jnl
Approximability and parameterized complexity of minmax values
CoRR
Kristoffer Arnsfelt Hansen, Thomas Dueholm Hansen, Peter Bro Miltersen, Troels Bjerre Sørensen
2008 — ed.
Computational Complexity of Discrete Problems, 14.09. - 19.09.2008
Computational Complexity of Discrete Problems
Peter Bro Miltersen, Rüdiger Reischuk, Georg Schnitger, Dieter van Melkebeek
2008 C conf
Deterministic Graphical Games Revisited.
CiE
Daniel Andersson, Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, Troels Bjerre Sørensen
2008 — ed.
Equilibrium Computation, 18.11. - 23.11.2007
Equilibrium Computation
P. Jean-Jacques Herings, Marcin Jurdzinski, Peter Bro Miltersen, Éva Tardos, Bernhard von Stengel
2008 A* conf
Fast algorithms for finding proper strategies in game trees.
SODA
Peter Bro Miltersen, Troels Bjerre Sørensen
2008 A* conf
On Range of Skill.
AAAI
Thomas Dueholm Hansen, Peter Bro Miltersen, Troels Bjerre Sørensen
2008 J jnl
On the computational complexity of solving stochastic mean-payoff games
CoRR
Vladimir Gurvich, Peter Bro Miltersen
2008 J jnl
Privacy-Enhancing First-Price Auctions Using Rational Cryptography.
IACR Cryptol. ePrint Arch.
Peter Bro Miltersen, Jesper Buus Nielsen, Nikos Triandopoulos
2008 J jnl
Special Issue: "Conference on Computational Complexity 2007" Guest Editor's Foreword.
Comput. Complex.
Peter Bro Miltersen
2008 J jnl
Trembling hand perfection is NP-hard
CoRR
Peter Bro Miltersen
2007 — conf
07471 Abstracts Collection - Equilibrium Computation.
Equilibrium Computation
P. Jean-Jacques Herings, Marcin Jurdzinski, Peter Bro Miltersen, Éva Tardos, Bernhard von Stengel
2007 A conf
A near-optimal strategy for a heads-up no-limit Texas Hold'em poker tournament.
AAMAS
Peter Bro Miltersen, Troels Bjerre Sørensen
2007 Misc conf
Finding Equilibria in Games of No Chance.
COCOON
Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, Troels Bjerre Sørensen
2007 J jnl
Simple Recursive Games
CoRR
Daniel Andersson, Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, Troels Bjerre Sørensen
2007 J jnl
The Computational Complexity of One-Dimensional Sandpiles.
Theory Comput. Syst.
Peter Bro Miltersen
2007 J jnl
The cell probe complexity of succinct data structures.
Theor. Comput. Sci.
Anna Gál, Peter Bro Miltersen
2006 J jnl
Circuits on cylinders.
Comput. Complex.
Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, V. Vinay
2006 — conf
Computing Proper Equilibria of Zero-Sum Games.
Computers and Games
Peter Bro Miltersen, Troels Bjerre Sørensen
2006 A* conf
Computing sequential equilibria for two-player games.
SODA
Peter Bro Miltersen, Troels Bjerre Sørensen
2006 Misc conf
Finding Small OBDDs for Incompletely Specified Truth Tables Is Hard.
COCOON
Jesper Torp Kristensen, Peter Bro Miltersen
2006 J jnl
Finding small OBDDs for incompletely specified truth tables is hard
Electron. Colloquium Comput. Complex.
Jesper Torp Kristensen, Peter Bro Miltersen
2006 A conf
On the Complexity of Numerical Analysis.
CCC
Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, Peter Bro Miltersen
2006 — conf
On the Complexity of Numerical Analysis.
Complexity of Boolean Functions
Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, Peter Bro Miltersen
2006 — conf
The Cell Probe Complexity of Succinct Data Structures.
Complexity of Boolean Functions
Anna Gál, Peter Bro Miltersen
2005 J jnl
Derandomizing Arthur-Merlin Games using Hitting Sets.
Comput. Complex.
Peter Bro Miltersen, N. V. Vinodchandran
2005 A* conf
Lower bounds on the size of selection and rank indexes.
SODA
Peter Bro Miltersen
2005 J jnl
On converting CNF to DNF.
Theor. Comput. Sci.
Peter Bro Miltersen, Jaikumar Radhakrishnan, Ingo Wegener
2005 J jnl
On the Complexity of Numerical Analysis
Electron. Colloquium Comput. Complex.
Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, Peter Bro Miltersen
2005 J jnl
Reviewing Bounds on the Circuit Size of the Hardest Functions
Electron. Colloquium Comput. Complex.
Gudmund Skovbjerg Frandsen, Peter Bro Miltersen
2005 J jnl
Reviewing bounds on the circuit size of the hardest functions.
Inf. Process. Lett.
Gudmund Skovbjerg Frandsen, Peter Bro Miltersen
2005 C conf
The Computational Complexity of One-Dimensional Sandpiles.
CiE
Peter Bro Miltersen
2004 B conf
Some Meet-in-the-Middle Circuit Lower Bounds.
MFCS
Kristoffer Arnsfelt Hansen, Peter Bro Miltersen
2003 B conf
Circuits on Cylinders.
FCT
Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, V. Vinay
2003 J jnl
On Converting CNF to DNF
Electron. Colloquium Comput. Complex.
Peter Bro Miltersen, Jaikumar Radhakrishnan, Ingo Wegener
2003 B conf
On Converting CNF to DNF.
MFCS
Peter Bro Miltersen, Jaikumar Radhakrishnan, Ingo Wegener
2003 A* conf
The Cell Probe Complexity of Succinct Data Structures.
ICALP
Anna Gál, Peter Bro Miltersen
2002 J jnl
Are Bitvectors Optimal?
SIAM J. Comput.
Harry Buhrman, Peter Bro Miltersen, Jaikumar Radhakrishnan, Srinivasan Venkatesh
2002 J jnl
Circuits on Cylinders
Electron. Colloquium Comput. Complex.
Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, V. Vinay
2001 J jnl
Deterministic Dictionaries.
J. Algorithms
Torben Hagerup, Peter Bro Miltersen, Rasmus Pagh
2001 J jnl
Lower Bounds for Dynamic Algebraic Problems.
Inf. Comput.
Gudmund Skovbjerg Frandsen, Johan P. Hansen, Peter Bro Miltersen
2001 B conf
On Pseudorandom Generators in NC.
MFCS
Mary Cryan, Peter Bro Miltersen
2000 A* conf
Are bitvectors optimal?
STOC
Harry Buhrman, Peter Bro Miltersen, Jaikumar Radhakrishnan, Srinivasan Venkatesh
2000 A conf
New Bounds for the Language Compression Problem.
CCC
Harry Buhrman, Sophie Laplante, Peter Bro Miltersen
2000 — conf
On the Shannon Function for Partially Defined Boolean Functions.
ICALP Satellite Workshops
Peter Bro Miltersen
1999 A* conf
Derandomizing Arthur-Merlin Games Using Hitting Sets.
FOCS
Peter Bro Miltersen, N. V. Vinodchandran
1999 J jnl
Fusion Trees can be Implemented with AC
Theor. Comput. Sci.
Arne Andersson, Peter Bro Miltersen, Mikkel Thorup
1999 J jnl
Guest Editors' Foreword.
Nord. J. Comput.
Jens Lagergren, Peter Bro Miltersen
1999 J jnl
Linear Hash Functions.
J. ACM
Noga Alon, Martin Dietzfelbinger, Peter Bro Miltersen, Erez Petrank, Gábor Tardos
1999 A conf
Lower Bounds for Dynamic Algebraic Problems.
STACS
Gudmund Skovbjerg Frandsen, Johan P. Hansen, Peter Bro Miltersen
1999 A conf
On Monotone Planar Circuits.
CCC
David A. Mix Barrington, Chi-Jen Lu, Peter Bro Miltersen, Sven Skyum
1999 Misc conf
Super-Polynomial Versus Half-Exponential Circuit Size in the Exponential Hierarchy.
COCOON
Peter Bro Miltersen, N. V. Vinodchandran, Osamu Watanabe
1999 J jnl
The Complexity of Identifying Large Equivalence Classes.
Fundam. Informaticae
Sven Skyum, Gudmund Skovbjerg Frandsen, Peter Bro Miltersen, Peter G. Binderup
1998 A* conf
Error Correcting Codes, Perfect Hashing Circuits, and Deterministic Dynamic Dictionaries.
SODA
Peter Bro Miltersen
1998 J jnl
On Data Structures and Asymmetric Communication Complexity.
J. Comput. Syst. Sci.
Peter Bro Miltersen, Noam Nisan, Shmuel Safra, Avi Wigderson
1998 — conf
On showing lower bounds for external-memory computational geometry problems.
External Memory Algorithms
Lars Arge, Peter Bro Miltersen
1998 A conf
Searching Constant Width Mazes Captures the AC
STACS
David A. Mix Barrington, Chi-Jen Lu, Peter Bro Miltersen, Sven Skyum
1997 J jnl
Dynamic word problems.
J. ACM
Gudmund Skovbjerg Frandsen, Peter Bro Miltersen, Sven Skyum
1997 A* conf
Is Linear Hashing Good?
STOC
Noga Alon, Martin Dietzfelbinger, Peter Bro Miltersen, Erez Petrank, Gábor Tardos
1997 J jnl
Searching constant width mazes captures the AC
Electron. Colloquium Comput. Complex.
David A. Mix Barrington, Chi-Jen Lu, Peter Bro Miltersen, Sven Skyum
1997 B conf
Trans-Dichotomous Algorithms Without Multiplication - Some Upper and Lower Bounds.
WADS
Andrej Brodnik, Peter Bro Miltersen, J. Ian Munro
1996 A* conf
Lower Bounds for Static Dictionaries on RAMs with Bit Operations But No Multiplication.
ICALP
Peter Bro Miltersen
1996 J jnl
Relative to a Random Oracle, NP Is Not Small.
J. Comput. Syst. Sci.
Steven M. Kautz, Peter Bro Miltersen
1996 A* conf
Static Dictionaries on AC
FOCS
Arne Andersson, Peter Bro Miltersen, Søren Riis, Mikkel Thorup
1996 J jnl
The Asymptotic Complexity of Merging Networks.
J. ACM
Peter Bro Miltersen, Mike Paterson, Jun Tarui
1995 B conf
Dynamic Algorithms for the Dyck Languages.
WADS
Gudmund Skovbjerg Frandsen, Thore Husfeldt, Peter Bro Miltersen, Theis Rauhe, Søren Skyum
1995 A* conf
On data structures and asymmetric communication complexity.
STOC
Peter Bro Miltersen, Noam Nisan, Shmuel Safra, Avi Wigderson
1995 J jnl
On the Cell Probe Complexity of Polynomial Evaluation.
Theor. Comput. Sci.
Peter Bro Miltersen
1995 B conf
Tables Should Be Sorted (On Random Access Machines).
WADS
Faith E. Fich, Peter Bro Miltersen
1994 J jnl
Complexity Models for Incremental Computation.
Theor. Comput. Sci.
Peter Bro Miltersen, Sairam Subramanian, Jeffrey Scott Vitter, Roberto Tamassia
1994 A* conf
Lower bounds for union-split-find related problems on random access machines.
STOC
Peter Bro Miltersen
1994 — conf
Relative to a Random Oracle, NP is Not Small.
SCT
Steven M. Kautz, Peter Bro Miltersen
1993 A* conf
Dynamic Word Problems
FOCS
Gudmund Skovbjerg Frandsen, Peter Bro Miltersen, Sven Skyum
1993 A conf
The Bit Probe Complexity Measure Revisited.
STACS
Peter Bro Miltersen
1993 B conf
The Complexity of Finding Replicas Using Equality Tests.
MFCS
Gudmund Skovbjerg Frandsen, Peter Bro Miltersen, Sven Skyum
1993 J jnl
The Complexity of Malign Measures.
SIAM J. Comput.
Peter Bro Miltersen
1992 J jnl
Circuit Depth Relative to a Random Oracle.
Inf. Process. Lett.
Peter Bro Miltersen
1992 A* conf
The Asymptotic Complexity of Merging Networks
FOCS
Peter Bro Miltersen, Mike Paterson, Jun Tarui
1991 — conf
The Complexity of Malign Ensembles.
SCT
Peter Bro Miltersen