The copyrights for journal and conference proceedings papers generally belong to the publisher of the journal or proceedings. All papers may be downloaded for personal or research purposes only. Publication list.

On-line Publications (in rough reverse chronological order):

Thomas Dueholm Hansen, Rasmus Ibsen-Jensen and Peter Bro Miltersen,
A faster algorithm for solving one-clock priced timed games,
Preprint, 2012. Click here

Rasmus Ibsen-Jensen and Peter Bro Miltersen,
Solving simple stochastic games with few coin toss positions,
Preprint, 2011. Click here

Peter Bro Miltersen,
Discounted stochastic games poorly approximate undiscounted ones,
Note, 2011. Click here

Kristoffer Arnsfelt Hansen, Michal Koucký, Niels Lauritzen, Peter Bro Miltersen and Elias P. Tsigaridas
Exact algorithms for solving stochastic games
STOC'11. Click here.

Kristoffer Arnsfelt Hansen, Rasmus Ibsen-Jensen and Peter Bro Miltersen
The complexity of solving reachability games using value and strategy iteration
CSR'11. Click here.

Thomas Dueholm Hansen, Peter Bro Miltersen and Uri Zwick
Strategy Iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor
ICS'11. Click here.

Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, and Troels Bjerre Sørensen,
The computational complexity of trembling hand perfection and other equilibrium refinements.
SAGT'10. Click here.

Peter Bro Miltersen and Troels Bjerre Sørensen,
Computing a quasi-perfect equilibrium of a two-player game,
Economic Theory, 2010. Click here.
Subsumes (except for some motivating discussion for computer scientists):
Computing sequential equilibria for two-player games,
SODA'06. For the SODA proceedings version, click here

Kristoffer Arnsfelt Hansen, Oded Lachish and Peter Bro Miltersen
Hilbert's thirteenth problem and circuit complexity
ISAAC'09. Click here.

Daniel Andersson and Peter Bro Miltersen
The complexity of solving stochastic games on graphs
ISAAC'09. Click here.

Peter Bro Miltersen, Jesper Buus Nielsen and Nikos Triandopoulos,
Privacy-enhancing auctions using rational cryptography
CRYPTO'09. Click here.

Kristoffer Arnsfelt Hansen, Michal Koucký, Peter Bro Miltersen,
Winning concurrent reachability games requires doubly-exponential patience.
LICS'09. Click here.

Guillaume Escamocher, Peter Bro Miltersen, and Rocio Santillan-Rodriguez,
Existence and computation of equilibria of first-price auctions with integral valuations and bids.
AAMAS'09. Click here. for AAMAS version and here for draft of longer version.

Kristoffer Arnsfelt Hansen, Thomas Dueholm Hansen, Peter Bro Miltersen, and Troels Bjerre Sørensen,
Approximability and parameterized complexity of minmax values.
WINE'08. Click here.

Thomas Dueholm Hansen, Peter Bro Miltersen, and Troels Bjerre Sørensen,
On range of skill.
AAAI'08. Click here.

Daniel Andersson, Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, and Troels Bjerre Sørensen,
Deterministic graphical games revisited.
CiE'08. Click here. Full version in Journal of Logic and Computation.

Peter Bro Miltersen and Troels Bjerre Sørensen,
Fast algorithms for finding proper strategies in game trees.
SODA'08. Click here for proceedings version (no proofs) and here for submitted version (proofs).

Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, and Troels Bjerre Sørensen,
Finding equilibria in games of no chance.
COCOON'07. Click here.

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

Jesper Torp Kristensen and Peter Bro Miltersen,
Finding small OBDDs for incompletely specified truth tables is hard.
COCOON'06. Click here.

Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen and Peter Bro Miltersen,
On the complexity of numerical analysis,
SIAM Journal on Computing, to appear. A preliminary version appeared at CCC'06. Click here for the full version.

Peter Bro Miltersen and Troels Bjerre Sørensen,
Computing proper equilibria of zero-sum games,
Computers and Games'06. Click here.

Peter Bro Miltersen,
The computational complexity of one-dimensional sandpiles
CiE'05 and Theory of Computing Systems, to appear. Click here.

Gudmund S. Frandsen and Peter Bro Miltersen
Reviewing bounds on the circuit size of the hardest functions.
Information Processing Letters 95. Click here.

Peter Bro Miltersen,
Lower bounds on the size of selection and rank indexes.
SODA'05. Click here.

Kristoffer Arnsfelt Hansen and Peter Bro Miltersen,
Some meet-in-the-middle circuit lower bounds.
MFCS'04. Click here.

Peter Bro Miltersen, Jaikumar Radhakrishnan and Ingo Wegener,
On converting CNF to DNF.
MFCS'03 and Theoretical Compuer science 347. Click here

Kristoffer Arnsfelt Hansen, Peter Bro Miltersen and V Vinay
Circuits on cylinders.
FCT'03 and Computational Complexity. Click here

Anna Gál and Peter Bro Miltersen,
The cell probe complexity of succinct data structures.
ICALP'03 (received EATCS best paper award). Click here.

Mary Cryan and Peter Bro Miltersen,
On pseudorandom generators in NC0.
MFCS'01. Click here

Torben Hagerup, Peter Bro Miltersen, Rasmus Pagh
Deterministic dictionaries.
Journal of Algorithms 41. Click here

Peter Bro Miltersen,
Derandomizing complexity classes.
Book chapter in Handbook of Randomized Computing, Kluwer Academic Publishers, 2001. Click here.

Peter Bro Miltersen,
On the Shannon function for partially defined Boolean functions.
Workshop on Boolean Functions and Applications '00. Click here.

Harry Buhrman, Sophie Laplante, Peter Bro Miltersen,
Improved bounds for the language compression problem
CCC'00. Click here.

Harry Buhrman, Peter Bro Miltersen, Jaikumar Radhakrishnan, Venkatesh Srinivasan,
Are bitvectors optimal?
STOC'00 and Siam Journal on Computing 31. Click here.

Peter Bro Miltersen,
Cell probe complexity - a survey
Invited talk/paper at Advances in Data Structures (Pre-conference workshop of FSTTCS'99). Click here for the paper and here for the talk.

Peter Bro Miltersen and N.V. Vinodchandran
Derandomizing Arthur-Merlin games using hitting sets.
FOCS'99 and Computational Complexity 14. Click here.

Peter Bro Miltersen, N.V. Vinodchandran, and Osamu Watanabe
Super-polynomial versus half-exponential circuit size in the exponential hierarchy.
COCOON'99. Click here.

David A. Mix Barrington, Chi-Jen Lu, Peter Bro Miltersen, and Sven Skyum,
On monotone planar circuits
CCC'99. Click here.

Gudmund S. Frandsen, Johan P. Hansen, and Peter Bro Miltersen,
Lower bounds for dynamic algebraic problems.
STACS'99, (in shortened version). Click here for US format, click here for European format of the full version.

Lars Arge and Peter Bro Miltersen,
On showing lower bounds for external-memory computational geometry problems.
EMA&VIS'98. Click here.

David A. Mix Barrington, Chi-Jen Lu, Peter Bro Miltersen, and Sven Skyum,
Searching constant width mazes captures the AC0-hierarchy.
STACS'98. Click here.

Peter Bro Miltersen,
Error correcting codes, perfect hashing circuits, and deterministic dynamic dictionaries.
SODA'98. Click here.

Andrej Brodnik, Peter Bro Miltersen, and J. Ian Munro,
Trans-dichotomous algorithms without multiplication - some upper and lower bounds
WADS'97. Click here.

Noga Alon, Martin Dietzfelbinger, Peter Bro Miltersen, Erez Petrank, and Gabor Tardos,
Linear hash functions
Journal of the ACM. Click here. Preliminary version appeared at STOC'97 under the name "Is linear hashing good?".

Arne Andersson, Peter Bro Miltersen, and Mikkel Thorup,
Fusion trees can be implemented with AC0 instructions only.
Theoretical Computer Science. For the BRICS tech report, click here.

Arne Andersson, Peter Bro Miltersen, Søren Riis, and Mikkel Thorup,
Static dictionaries on AC0 RAMs: Query time is necessary and sufficient.
FOCS'96. For the DIKU tech report, click here.

Peter Bro Miltersen,
 Lower bounds for static dictionaries on RAMs with bit operations but no multiplication.
ICALP'96. For the version appearing at the conference, click here.

Faith Fich, Peter Bro Miltersen,
Tables should be sorted (on random access machines),
WADS'95. For the version appearing at the conference, click here.

Gudmund S. Frandsen, Thore Husfeldt, Peter Bro Miltersen, Theis Rauhe, Søren Skyum,
Dynamic algorithms for the Dyck languages,
 WADS'95. For the BRICS tech report, click here

Peter Bro Miltersen, Noam Nisan, Shmuel Safra, Avi Wigderson,
On data structures and asymmetric communication complexity,
JCSS and STOC'95. For the full version, click here

Peter Bro Miltersen,
On the cell probe complexity of polynomial evaluation,
Theoretical Computer Science 143 . Click here.

Steve Kautz, Peter Bro Miltersen,
Relative to a random oracle, NP is not small,
STRUCTURES'94 and Journal of Computer and System Sciences 53. For the full version, click here.

Peter Bro Miltersen,
Lower bounds for Union-Split-Find related problems on random access machines,
STOC'94. For the conference paper, click here.

Peter Bro Miltersen, Sairam Subramanian, Roberto Tamassia, Jeff Vitter,
Complexity models for incremental computation,
Theoretical Computer Science 130. Click here.

Gudmund S. Frandsen, Peter Bro Miltersen, Sven Skyum,
Dynamic word problems,
FOCS'93 and Journal of the ACM. For the full version, click here.

Gudmund S. Frandsen, Peter Bro Miltersen, Sven Skyum,
The complexity of finding replicas using equality tests, MFCS'93 .
Extended version:
Peter G. Binderup, Gudmund S. Frandsen, Peter Bro Miltersen, Sven Skyum,
The Complexity of Identifying Large Equivalence Classes.
Fundamentae Informaticae 38. Click here.

Peter Bro Miltersen,
The bit probe complexity measure revisited,
STACS'93. Click here.

Peter Bro Miltersen, Mike Paterson, Jun Tarui
The asymptotic complexity of merging networks,
FOCS'92 and Journal of the ACM 43. For the full version, click here.

Peter Bro Miltersen,
Circuit depth relative to a random oracle,
Information Processing Letters 42. Click here.

Peter Bro Miltersen,
The complexity of malign ensembles,
STRUCTURES'91 and Siam Journal on Computing 22 . For the conference version, click here

Back to my homepage