1. Introduction Universal hashing is theory at its best! Hashing started out as a purely heuristic method for implementing symbol tables. It moved into the hardcore theory of algorithms with Carter...
Approximability and Parameterized Complexity of Minmax Values ⋆ (2009)
Kristoffer Arnsfelt Hansen, Thomas Dueholm Hansen, Peter Bro Miltersen, Troels Bjerre Sørensen
Abstract. We consider approximating the minmax value of a multiplayer game in strategic form. Tightening recent bounds by Borgs et al., we observe that approximating the value with a precision of ɛ...
On the complexity of numerical analysis (2009)
Eric Allender, Peter B Ürgisser, Johan Kjeldgaard-pedersen, Peter Bro Miltersen
Abstract. We study two quite different approaches to understanding the complexity of fundamental problems in numerical analysis: • The Blum-Shub-Smale model of computation over the reals. • A...
Deterministic Graphical Games Revisited ⋆ (2008)
Daniel Andersson, Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, Troels Bjerre Sørensen
Abstract. We revisit the deterministic graphical games of Washburn. A deterministic graphical game can be described as a simple stochastic game (a notion due to Anne Condon), except that we allow...
On the computational complexity of solving stochastic mean-payoff games (2008)
Gurvich, Vladimir, Miltersen, Peter Bro
We consider some well-known families of two-player, zero-sum, perfect information games that can be viewed as special cases of Shapley's stochastic games. We show that the following tasks are...
Trembling hand perfection is NP-hard (2008)
It is NP-hard to decide if a given pure-strategy Nash equilibrium of a given three-player game in strategic form with integer payoffs is trembling hand perfect.
Approximability and parameterized complexity of minmax values (2008)
Hansen, Kristoffer Arnsfelt, Hansen, Thomas Dueholm, Miltersen, Peter Bro, Sørensen, Troels Bjerre
We consider approximating the minmax value of a multi-player game in strategic form. Tightening recent bounds by Borgs et al., we observe that approximating the value with a precision of epsilon log...
Kim Skak Larsen, Peter Bro Miltersen, Erik Meineche, A. Gill, ...
Lueker [L] shows that when the coin values are large and represented in binary, the problem of nding an optimal representation of a given x is NP-hard. Here we show: Theorem 5.1 It is coNP-complete...
Daniel Andersson, Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, Troels Bjerre Sørensen
Abstract. We define the class of simple recursive games. A simple recursive game is defined as a simple stochastic game (a notion due to Anne Condon), except that we allow arbitrary real payoffs but...
Finding small OBDDs for incompletely specified truth tables is hard (2008)
Jesper Torp Kristensen, Peter Bro Miltersen
Abstract. We present an efficient reduction mapping undirected graphs G with n = 2 k vertices for integers k to tables of partially specified Boolean functions g: {0, 1} 4k+1 → {0, 1, ⊥} so that...
Eric Allender, Johan Kjeldgaard-pedersen, Peter Bürgisser, Peter Bro Miltersen
We study two quite different approaches to understanding the complexity of fundamental problems in numerical analysis: • The Blum-Shub-Smale model of computation over the reals. • A problem we...
Finding Equilibria in Games of No Chance (2008)
Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, Troels Bjerre Sørensen
Abstract. We consider finding maximin strategies and equilibria of explicitly given extensive form games with imperfect information but with no moves of chance. We show that a maximin pure strategy...
Fast algorithms for finding proper strategies in game trees (2008)
Peter Bro Miltersen, Troels Bjerre Sørensen
We show how to find a normal form proper equilibrium in behavior strategies of a given two-player zero-sum extensive form game with imperfect information but perfect recall. Our algorithm solves a...
Computing Proper Equilibria of Zero-Sum Games (2008)
Peter Bro Miltersen, Troels Bjerre Sørensen
Abstract. We show that a proper equilibrium of a matrix game can be found in polynomial time by solving a linear (in the number of pure strategies of the two players) number of linear programs of...
Peter Bro Miltersen, Troels Bjerre Sørensen
algorithms for finding proper strategies in game trees
Eric Allender, Johan Kjeldgaard-pedersen, Peter Bürgisser, Peter Bro Miltersen
We study two quite different approaches to understanding the complexity of fundamental problems in numerical analysis: • The Blum-Shub-Smale model of computation over the reals. • A problem we...
The Computational Complexity of One-Dimensional (2008)
Abstract. We prove that the one-dimensional sandpile prediction problem is in AC 1. The previously best known upper bound on the AC i-scale was AC 2. We also prove that it is not in AC 1−ɛ for any...
Vladimir Gurvich, Peter Bro Miltersen
the computational complexity of solving stochastic mean-payoff
Trembling hand perfection is NP-hard (note) (2008)
It is NP-hard to decide if a given pure strategy Nash equilibrium of a given three-player game in strategic form with integer payoffs is trembling hand perfect. 1
08381 Executive Summary -- Computational Complexity of Discrete Problems (2008)
Miltersen, Peter Bro, Reischuk, Rüdiger, Schnitger, Georg, Van Melkebeek, Dieter
Estimating the computational complexity of discrete problems constitutes one of the central and classical topics in the theory of computation. Mathematicians and computer scientists have long tried...
08381 Abstracts Collection -- Computational Complexity of Discrete Problems (2008)
Miltersen, Peter Bro, Reischuk, Rüdiger, Schnitger, Georg, Van Melkebeek, Dieter
From the 14th of September to the 19th of September, the Dagstuhl Seminar 08381 ``Computational Complexity of Discrete Problems'' was held in Schloss Dagstuhl - Leibniz Center for Informatics. During...
Peter Bro Miltersen, N. V. Vinodchandran
Super-polynomial versus half-exponential circuit size in the exponential hierarchy
Noga Alon, Martin Dietzfelbinger, Peter Bro Miltersen, Erez Petrank
Consider the set H of all linear (or ane) transformations between two vector spaces over a nite eld F. We study how good H is as a class of hash functions, namely we consider hashing a set S of size...
On the Shannon function for partially dened Boolean functions (2007)
Andreev, Clementi and Rolim considered the Shannon function for partially dened Boolean functions and derived an expression for the value of this function. They proved the expression correct for a...
Abstract. We prove (for fixed k) that at least (2007)
Gudmund Skovbjerg Fr, Peter Bro Miltersen, Sven Skyum
tests and no more than 2 k ( n 2)+O(n) equality tests are needed in the worst case to determine whether a given set of n elements contains a subset of k identical elements. The upper bound is an...
Dynamic Algebraic Problems (2007)
Lower Bounds For, Johan P. Hansen, Peter Bro Miltersen, Gudmund Skovbjerg Frandsen, Gudmund Skovbjerg Frandsen
et al.:
Error Correcting Codes, Perfect Hashing (2007)
Peter Bro Miltersen, Peter Bro Miltersen
Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent BRICS...
log n = log log n) is Necessary and Sufficient (2007)
Arne Andersson, Peter Bro Miltersen, Sren Riis, Mikkel Thorup
et al.:
Two Notes on the Computational Complexity of (2007)
One-dimensional Sandpiles, Peter Bro Miltersen, Peter Bro Miltersen
on the
Derandomizing Arthur-Merlin Games using Hitting Sets (2007)
Vinodchandran N. Variyam, Peter Bro Miltersen, Peter Bro Miltersen, Ran N, Peter Bro
Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent BRICS...
Faith Fich, Peter Bro Miltersen
should be sorted (on random access machines) BRICS Basic Research in Computer Science Tables should be sorted (on random access machines)
Peter Bro Miltersen, Noam Nisan, Avi Wigderson
In this paper we consider two-party communication complexity, the ``asymmetric case'', when the input sizes of the two players differ significantly. Most of previous work on communication...
RAMs: Query time \Theta( (2007)
Arne Andersson, Arne Andersson, Peter Bro Miltersen, Peter Bro Miltersen, Sren Riis, Sren Riis, ...
log n = log log n) is necessary and sufficient
Noga Alon, Martin Dietzfelbinger, Peter Bro Miltersen, Erez Petrank
Consider the set H of all linear (or affine) transformations between two vector spaces over a finite field F. We study how good H is as a class of hash functions, namely we consider hashing a set S...
Gudmund Skovbjerg Fr, Johan P. Hansen, Peter Bro Miltersen
We consider dynamic evaluation of algebraic functions (matrix multiplication, determinant, convolution, Fourier transform, etc.) in the model of Reif and Tate; i.e., if f(x1,..., xn) = (y1,..., ym)...
The Cell Probe Complexity of Succinct Data Structures (2007)
We show lower bounds in the cell probe model for the redundancy/query time tradeoff of solutions to static data structure problems.
Noga Alon, Martin Dietzfelbinger, Peter Bro Miltersen, Gábor Tardos
The research of P. Bro Miltersen was supported by the ESPRIT Long Term Research Programme of
Andersson, Daniel, Hansen, Kristoffer Arnsfelt, Miltersen, Peter Bro, Sorensen, Troels Bjerre
We define the class of "simple recursive games". A simple recursive game is defined as a simple stochastic game (a notion due to Anne Condon), except that we allow arbitrary real payoffs but disallow...
Equilibrium Computation Dagstuhl Seminar (2007)
Herings, Jean-Jacques, Jurdzinski, Marcin, Miltersen, Peter Bro, Tardos, Eva, Stengel, Bernhard Von
From 18 to 23 November 2007, the Dagstuhl Seminar 07471 'Equilibrium Computation" was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, sev- eral...
Computing a quasi-perfect equilibrium of a two-player game (2007)
Peter Bro Miltersen, Troels Bjerre Sørensen
Refining an algorithm due to Koller, Megiddo and von Stengel, we show how to apply Lemke’s algorithm for solving linear complementarity programs to compute a quasi-perfect equilibrium in behavior...
A near-optimal strategy for a heads-up no-limit Texas Hold’em poker tournament (2007)
We analyze a heads-up no-limit Texas Hold’em poker tournament with a fixed small blind of 300 chips, a fixed big blind of 600 chips and a total amount of 8000 chips on the table (until recently,...
Hansen, Kristoffer Arnsfelt, Miltersen, Peter Bro, Vinay, V
We consider the computational power of constant width polynomial size cylindrical circuits and nondeterministic branching pro-grams. We show that every function computed by a...
Hansen, Kristoffer Arnsfelt, Miltersen, Peter Bro, Vinay, V
We consider the computational power of constant width polynomial size cylindrical circuits and nondeterministic branching pro-grams. We show that every function computed by a...
Computing sequential equilibria for two-player games (2006)
Peter Bro Miltersen, Troels Bjerre Sørensen
Koller, Megiddo and von Stengel showed how to efficiently compute minimax strategies for two-player extensive-form zero-sum games with imperfect information but perfect recall using linear...
Computing sequential equilibria for two-player games (2006)
Peter Bro Miltersen, Troels Bjerre Sørensen
Koller, Megiddo and von Stengel showed how to efficiently compute minimax strategies for two-player extensive-form zero-sum games with imperfect information but perfect recall using linear...
On the complexity of numerical analysis (2006)
Eric Allender, Peter Bürgisser, Johan Kjeldgaard-pedersen, Peter Bro Miltersen
We study two quite different approaches to understanding the complexity of fundamental problems in numerical analysis. We show that both hinge on the question of understanding the complexity of the...
The Cell Probe Complexity of Succinct Data Structures (2006)
Gál, Anna, Miltersen, Peter Bro
In the cell probe model with word size 1 (the bit probe model), a static data structure problem is given by a map $f: {0,1}^n imes {0,1}^m ightarrow {0,1}$, where ${0,1}^n$ is a set of possible data...
On the Complexity of Numerical Analysis (2006)
Allender, Eric, Bürgisser, Peter, Kjeldgaard-Pedersen, Johan, Miltersen, Peter Bro
We study two quite different approaches to understanding the complexity of fundamental problems in numerical analysis. We show that both hinge on the question of understanding the complexity of the...
Reviewing bounds on the circuit size of the hardest functions (2005)
Gudmund Skovbjerg Frandsen, Peter Bro Miltersen, Copyright C, Gudmund Skovbjerg Fr, Peter Bro, Gudmund Skovbjerg Frandsen, ...
Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent BRICS...
Some Meet-in-the-Middle Circuit Lower Bounds (2004)
Kristoffer Arnsfelt Hansen, Kristo#er Arnsfelt Hansen, Peter Bro Miltersen
We observe that a combination of known top-down and bottom-up lower bound techniques of circuit complexity may yield new circuit lower bounds.
The cell probe complexity of succinct data structures (2003)
Abstract. We show lower bounds in the cell probe model for the redundancy/query time tradeoff of solutions to static data structure problems. 1
On converting CNF to DNF (2003)
Peter Bro Miltersen, Jaikumar Radhakrishnan, Ingo Wegener
Abstract. We study how big the blow-up in size can be when one switches between the CNF and DNF representations of boolean functions. For a function f: {0, 1} n → {0, 1}, cnfsize(f) denotes the...
Anna Gál, Peter Bro Miltersen, Copyright C, Anna Gál, Peter Bro Miltersen, Anna Gál, ...
Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent BRICS...
The cell probe complexity of succinct data structures (2003)
In the cell probe model with word size 1 (the bit probe model), a static data structure problem is given by a map f: {0, 1} n ×{0, 1} m → {0, 1}, where {0, 1} n is a set of possible data to be...
This document in subdirectoryRS/02/50/ Circuits on Cylinders (2002)
Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, V. Vinay, Copyright C, Kristoffer Arnsfelt Hansen, Peter Bro, ...
Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent BRICS...
On pseudorandom generators in NC 0 (2001)
Mary Cryan, Peter Bro Miltersen
Abstract. In this paper we consider the question of whether NC 0 circuits can generate pseudorandom distributions. While we leave the general question unanswered, we show • Generators computed by...
Deterministic Dictionaries (2000)
Torben Hagerup, Johann Wolfgang, Peter Bro Miltersen, Rasmus Pagh
this paper, our primary interest lies in obtaining static dictionaries with optimal query time and minimal space consumption that can be constructed rapidly by deterministic algorithms. By general...
Are Bitvectors Optimal? (2000)
Harry Buhrman, Peter Bro Miltersen, Jaikumar Radhakrishnan, Srinivasan Venkatesh, H. Buhrman, P. B. Miltersen, ...
We study the static membership problem: Given a set S of at most n keys drawn from a universe of size m, store it so that queries of the form "Is x in S?" can be answered quickly. We study...
Deterministic Dictionaries (2000)
Torben Hagerup, Peter Bro Miltersen, Rasmus Pagh
this paper, our primary interest lies in obtaining static dictionaries with optimal query time and minimal space consumption that can be constructed rapidly by deterministic algorithms. By general...
Super-polynomial versus half-exponential circuit size in the exponential hierarchy (1999)
Vinodchandran N. Variyam, Peter Bro Miltersen, Peter Bro Miltersen, Ran N, Osamu Watanabe, Osamu Watanabe
et al.: Half-Exponential
Martin Dietzfelbinger, Peter Bro Miltersen, G Abor Tardos, Noga Alon, Noga Alon, Erez Petrank, ...
et al.:
Lower Bounds for Dynamic Algebraic Problems (1999)
Gudmund Skovbjerg, Johan P. Hansen, Peter Bro Miltersen
We consider dynamic evaluation of algebraic functions (matrix multiplication, determinant, convolution, Fourier transform, etc.) in the model of Reif and Tate; i.e., if f(x 1 ; : : : ; xn ) = (y 1 ;...
Lower Bounds for Dynamic Algebraic Problems (1999)
Gudmund Skovbjerg Frandsen, Johan P. Hansen, Peter Bro Miltersen
We consider dynamic evaluation of algebraic functions (matrix multiplication, determinant, convolution, Fourier transform, etc.) in the model of Reif and Tate; i.e., if f(x 1 ; : : : ; xn ) = (y 1 ;...
Fusion trees can be implemented with AC 0 instructions only. Theoretical Computer Science (1999)
Peter Bro Miltersen, Mikkel Thorup, Arne Andersson, Arne Andersson
is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent publications in the BRICS Report Series. Copies...
Two Notes on the Computational Complexity of One-Dimensional Sandpiles (1999)
We prove that the one-dimensional sandpile prediction problem is in AC 1 . The previously best known upper bound on the AC i -scale was AC 2 . We also prove that it is not in AC 1 for any constant...
Cell Probe Complexity - a Survey (1999)
The cell probe model is a general, combinatorial model of data structures. We give a survey of known results about the cell probe complexity of static and dynamic data structure problems, with an...
Cell probe complexity - a survey (1999)
Abstract The cell probe model is a general, combinatorial model of data structures. We give a survey of known results about the cell probe complexity of static and dynamic data structure problems,...
Two Notes on the Computational Complexity of (1999)
One-dimensional Sandpiles, Peter Bro Miltersen, Copyright C, Peter Bro Miltersen, Peter Bro Miltersen
Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent BRICS...
Derandomizing Arthur-Merlin games using hitting sets (1999)
Vinodchandran N. Variyam, Copyright C, Peter Bro Miltersen, Peter Bro Miltersen, Ran N, Peter Bro, ...
Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent BRICS...
circuit size in the exponential hierarchy (1999)
Peter Bro Miltersen, Vinodchandran N. Variyam, Copyright C, Peter Bro Miltersen, Ran N, Osamu Watanabe, ...
Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent BRICS...
The Complexity of Identifying Large Equivalence (1998)
Gudmund Skovbjerg Frandsen, Peter Bro Miltersen, Sven Skyum, Peter G. Binderup, Peter G. Binderup, Gudmund S. Frandsen, ...
et al.:
On data structures and asymmetric communication complexity (1998)
Peter Bro Miltersen, Peter Bro Miltersen, Noam Nisan, Noam Nisan, Avi Wigderson, Avi Wigderson
is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent publications in the BRICS Report Series. Copies...
Searching constant width mazes captures the AC 0 hierarchy (1998)
Chi-jen Lu, Peter Bro Miltersen, Sven Skyum
Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent BRICS...
Searching Constant Width Mazes Captures the (1998)
Hierarchy David Mix, Chi-jen Lu, Peter Bro Miltersen, Sven Skyum
We show that searching a width k maze is complete for \Pi k , i.e., for the k'th level of the AC 0 hierarchy. Equivalently, st-connectivity for width k grid graphs is complete for \Pi k . As an...
Error Correcting Codes, Perfect Hashing Circuits, and Deterministic Dynamic Dictionaries (1998)
We consider dictionaries of size n over the finite universe U = f0; 1g w and introduce a new technique for their implementation: error correcting codes. The use of such codes makes it possible to...
Searching constant width mazes captures the AC0 hierarchy (1998)
Chi-Jen Lu, Peter Bro Miltersen, Sven Skyum
We show that searching a width k maze is complete for \Pi k , i.e., for the k'th level of the AC 0 hierarchy. Equivalently, st-connectivity for width k grid graphs is complete for \Pi k . As an...
Searching constant width mazes captures the AC 0 hierarchy (1998)
Chi-jen Lu, Peter Bro Miltersen, Sven Skyum, Peter Bro, Miltersen Sven Skyum
Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent BRICS...
Peter G. Binderup, Gudmund Skovbjerg Frandsen, Peter Bro Miltersen, Sven Skyum, Peter G. Binderup, Gudmund S. Frandsen, ...
Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent BRICS...
On data structures and asymmetric communication complexity (1998)
Peter Bro Miltersen, Noam Nisan, Peter Bro, Miltersen Noam, Nisan Shmuel Safra, Avi Wigderson, ...
Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent...
Lower Bounds, Andrej Brodnik, Peter Bro Miltersen, J. Ian Munro
et al.: Trans-Dichotomous
Trans-Dichotomous Algorithms Without Multiplication - Some Upper and Lower Bounds (1997)
Andrej Brodnik, Peter Bro Miltersen, J. Ian Munro
. We show that on a RAM with addition, subtraction, bitwise Boolean operations and shifts, but no multiplication, there is a transdichotomous solution to the static dictionary problem using linear...
Trans-Dichotomous Algorithms Without Multiplication - Some Upper and Lower Bounds (1997)
Andrej Brodnik, Peter Bro Miltersen, J. Ian Munro
. We show that on a RAM with addition, subtraction, bitwise Boolean operations and shifts, but no multiplication, there is a transdichotomous solution to the static dictionary problem using linear...
Noga Alon, Martin Dietzfelbinger, Peter Bro Miltersen, Erez Petrank, Gábor Tardos
Consider the set H of all linear (or affine) transformations between two vector spaces over a finite field F . We study how good H is as a class of hash functions, namely we consider hashing a set S...
Trans-Dichotomous Algorithms without Multiplication (1997)
Lower Bounds, Andrej Brodnik, Peter Bro Miltersen, J. Ian Munro, Andrej Brodnik, Peter Bro Miltersen, ...
Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent BRICS...
Rams Query, Arne Andersson, Peter Bro Miltersen, Mikkel Thorup
In this paper we consider solutions to the static dictionary problem on AC 0 RAMs, i.e. random access machines where the only restriction on the finite instruction set is that all computational...
Lower bounds for static dictionaries on RAMs with bit operations but no multiplication (1996)
. We consider solving the static dictionary problem with n keys from the universe f0; : : : ; m \Gamma 1g on a RAM with direct and indirect addressing, conditional jump, addition, bitwise Boolean...
The Asymptotic Complexity of Merging Networks (1996)
Peter Bro Miltersen, Mike Paterson
Abstract. Let Mm, n) be the minimum number of comparators needed in a comparator network that merges m elements x, < x2 zz... ZG x, and n elements y, 5 y, <... s y,, where n t m. Batcher’s...
Dynamic algorithms for the Dyck languages (1995)
Gudmund Skovbjerg Frandsen, Gudmund Skovbjerg Frandsen, Thore Husfeldt, Thore Husfeldt, Peter Bro Miltersen, Peter Bro Miltersen, ...
is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent publications in the BRICS Report Series. Copies...
Dynamic algorithms for the Dyck languages (1995)
Gudmund Skovbjerg Frandsen, Thore Husfeldt, Peter Bro Miltersen, Theis Rauhe, Sren Skyum
Abstract. We study Dynamic Membership problems for the Dyck languages, the class of strings of properly balanced parentheses. We also study the Dynamic Word problem for the free group. We present...
Tables Should Be Sorted (on Random Access Machines) (1995)
Faith Fich, Peter Bro Miltersen
. We consider the problem of storing an n element subset S of a universe of size m, so that membership queries (is x 2 S?) can be answered efficiently. The model of computation is a random access...
The Asymptotic Complexity of Merging Networks (Extended Abstract) (1995)
Peter Bro Miltersen, Mike Paterson
) Peter Bro Miltersen y Mike Paterson z Jun Tarui z January 16, 1995 Abstract Let M (m; n) be the minimum number of comparators in a comparator network that merges two ordered chains x 1 x 2 : : : xm...
On the Cell Probe Complexity of Polynomial Evaluation (1995)
We consider the cell probe complexity of the polynomial evaluation problem with preprocessing of coefficients, for polynomials of degree at most n over a finite field K. We show that the trivial cell...
Dynamic Algorithms for the Dyck Languages (1995)
Gudmund Skovbjerg Frandsen, Gudmund Skovbjerg Frandsen, Thore Husfeldt, Thore Husfeldt, Søren Skyum, Peter Bro Miltersen, ...
We study dynamic membership problems for the Dyck languages, the class of strings of properly balanced parentheses. We also study the Dynamic Word problem for the free group. We present deterministic...
Dynamic algorithms for the Dyck languages (1995)
Gudmund Skovbjerg Frandsen, Gudmund Skovbjerg Frandsen, Thore Husfeldt, Thore Husfeldt, Peter Bro Miltersen, Peter Bro Miltersen, ...
Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent...
Lower bounds for Union-Split-Find related problems on random access machines (1994)
We prove \Omega\Gamma p log log n) lower bounds on the random access machine complexity of several dynamic, partially dynamic and static data structure problems, including the union-split-find...
Relative to a Random Oracle, NP Is Not Small (1994)
Steven Kautz, Peter Bro Miltersen
Resource-bounded measure as originated by Lutz is an extension of classical measure theory which provides a probabilistic means of describing the relative sizes of complexity classes. Lutz has...
Lower bounds for Union-Split-Find related problems on random access machines (1994)
We prove \Omega\Gamma p log log n) lower bounds on the random access machine complexity of several dynamic, partially dynamic and static data structure problems, including the Union-Split-Find...
Complexity Models for Incremental Computation (1994)
Peter Bro, Peter Bro Miltersen, Sairam Subramanian, Jeffrey Scott Vitter, Roberto Tamassia
We present a new complexity theoretic approach to incremental computation. We define complexity classes that capture the intuitive notion of incremental efficiency and study their relation to...
Complexity Models for Incremental Computation (1994)
Peter B. Miltersen, Jeffresy S. Vitter, Peter Bro Miltersen, Sairam Subramanian, Sairam Subramanian, Jeffrey Scott Vitter, ...
We present a new complexity theoretic approach to incremental computation. We define complexity classes that capture the intuitive notion of incremental efficiency and study their relation to...
Relative to a random oracle, NP is not small (1994)
Steven M. Kautz, Peter Bro Miltersen
Resource-bounded measure as originated by Lutz is an extension of classical measure theory which provides a probabilistic means of describing the relative sizes of complexity classes. Lutz has...
The bit probe complexity measure revisited (1993)
Abstract. A static data structure problem consists of a set of data D, a set of queries Q and a function f with domain D \ThetaQ. Given a space bound b, a (good) solution to the problem is an...
Gudmund Skovbjerg Frandsen, Frandsen Peter, Peter Bro Miltersen, Sven Skyum
Let M be a fixed finite monoid. We consider the problem of implementing a data type containing a vector x = (x1 ; x2 ; : : : ; xn) 2 M n , initially (1; 1; : : : ; 1), with two kinds of operations,...
The Complexity of Finding Replicas Using Equality Tests (1993)
Gudmund Skovbjerg Frandsen, Peter Bro Miltersen, Sven Skyum
We prove (for fixed k) that at least 1 k-1 ( n 2 ) - O(n) equality tests and no more than 2 k ( n 2 ) + O(n) equality tests are needed in the worst case to determine whether a given set of n elements...
Gudmund Skovbjerg Frandsen, Peter Bro Miltersen, Sven Skyum
Let M be a fixed finite monoid. We consider the problem of implementing a data type containing a vector x = (x 1 , x 2 , . . . , x n ) # M n , initially (1, 1, . . . , 1) with two kinds of...
The Asymptotic Complexity of Merging Networks (1992)
Peter Bro Miltersen, Mike Paterson, Jun Tarui, Coventry Cv Al
Let M (m; n) be the minimum number of comparators needed in a comparator network that merges m elements x 1 x 2 : : : xm and n elements y 1 y 2 : : : y n , where n m. Batcher's odd-even merge...
The Complexity of Malign Ensembles (1991)
We analyze the concept of malignness, which is the property of probability ensembles of making the average case running time equal to the worst case running time for a class of algorithms. We derive...
This document in subdirectoryRS/97/16/ Linear Hashing
Noga Alon, Martin Dietzfelbinger, Peter Bro Miltersen, Erez Petrank, Gábor Tardos, Noga Alon, ...
Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent BRICS...
Circuits, and Deterministic Dynamic Dictionaries
Peter Bro Miltersen, Peter Bro Miltersen
Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent BRICS...
Lower Bounds For, Gudmund Skovbjerg Frandsen, Johan P. Hansen, Peter Bro Miltersen, Gudmund Skovbjerg Fr, Peter Bro Miltersen
Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent BRICS...
Arne Andersson, Peter Bro Miltersen, Søren Riis, Mikkel Thorup, Arne Andersson, Peter Bro Miltersen, ...
Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent BRICS...
This document in subdirectoryRS/03/45/ On Converting CNF to DNF
Peter Bro Miltersen, Jaikumar Radhakrishnan, Ingo Wegener, Copyright C, Peter Bro Miltersen, Ingo Wegener, ...
Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent BRICS...