Arrow Research search

Author name cluster

Peter Bro Miltersen

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

27 papers
2 author rows

Possible papers

27

AIJ Journal 2023 Journal Article

Walrasian pricing in multi-unit auctions

  • Simina Brânzei
  • Aris Filos-Ratsikas
  • Peter Bro Miltersen
  • Yulong Zeng

Multi-unit auctions are a paradigmatic model of resource allocation, where a seller brings multiple units of a good to a set of buyers equipped with monetary budgets. It is well known that Walrasian equilibria do not always exist in this model, however compelling relaxations such as Walrasian envy-free pricing do. We design a best possible envy-free and prior-free mechanism for multi-unit auctions with budgets. When the market is even mildly competitive, the approximation ratios of this mechanism are small constants for both the revenue and welfare objectives, and in fact for welfare the approximation converges to 1 as the market becomes fully competitive. We also give an impossibility theorem, showing that truthfulness requires discarding resources and is thus incompatible with (Pareto) efficiency.

Details DOI

MFCS Conference 2017 Conference Paper

Walrasian Pricing in Multi-Unit Auctions

  • Simina Brânzei
  • Aris Filos-Ratsikas
  • Peter Bro Miltersen
  • Yulong Zeng

Multi-unit auctions are a paradigmatic model, where a seller brings multiple units of a good, while several buyers bring monetary endowments. It is well known that Walrasian equilibria do not always exist in this model, however compelling relaxations such as Walrasian envy-free pricing do. In this paper we design an optimal envy-free mechanism for multi-unit auctions with budgets. When the market is even mildly competitive, the approximation ratios of this mechanism are small constants for both the revenue and welfare objectives, and in fact for welfare the approximation converges to 1 as the market becomes fully competitive. We also give an impossibility theorem, showing that truthfulness requires discarding resources, and in particular, is incompatible with (Pareto) efficiency.

Details

IJCAI Conference 2015 Conference Paper

A Dictatorship Theorem for Cake Cutting

  • Simina Br
  • acirc; nzei
  • Peter Bro Miltersen

We consider discrete protocols for the classical Steinhaus cake cutting problem. Under mild technical conditions, we show that any deterministic strategy-proof protocol for two agents in the standard Robertson-Webb query model is dictatorial, that is, there is a fixed agent to which the protocol allocates the entire cake. For n > 2 agents, a similar impossibility holds, namely there always exists an agent that gets the empty piece (i. e. no cake). In contrast, we exhibit randomized protocols that are truthful in expectation and compute approximately fair allocations.

PDF Details

STOC Conference 2011 Conference Paper

Exact algorithms for solving stochastic games: extended abstract

  • Kristoffer Arnsfelt Hansen
  • Michal Koucký 0001
  • Niels Lauritzen
  • Peter Bro Miltersen
  • Elias P. Tsigaridas

Shapley's discounted stochastic games, Everett's recursive games and Gillette's undiscounted stochastic games are classical models of game theory describing two-player zero-sum games of potentially infinite duration. We describe algorithms for exactly solving these games. When the number of positions of the game isbconstant, our algorithms run in polynomial time.

Details

AAMAS Conference 2007 Conference Paper

A Near-Optimal Strategy for a Heads-Up No-Limit Texas Hold'em Poker Tournament

  • Peter Bro Miltersen
  • Troels Bjerre Sørensen

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, these parameters defined the headsup endgame of sit-n-go tournaments on the popular Party-Poker. com online poker site). Due to the size of this game, a computation of an optimal (i. e. minimax) strategy for the game is completely infeasible. However, combining an algorithm due to Koller, Megiddo and von Stengel with concepts of Everett and suggestions of Sklansky, we compute an optimal jam/fold strategy, i. e. a strategy that would be optimal if any bet made by the player playing by the strategy (but not bets of his opponent) had to be his entire stack. Our computations establish that the computed strategy is nearoptimal for the unrestricted tournament (i. e. , with post-flop play being allowed) in the rigorous sense that a player playing by the computed strategy will win the tournament with a probability within 1. 4 percentage points of the probability that an optimal strategy (allowing post-flop play) would give.

PDF

TCS Journal 2007 Journal Article

The cell probe complexity of succinct data structures

  • Anna Gál
  • Peter Bro Miltersen

We consider time-space tradeoffs for static data structure problems in the cell probe model with word size 1 (the bit probe model). In this model, the goal is to represent n -bit data with s = n + r bits such that queries (of a certain type) about the data can be answered by reading at most t bits of the representation. Ideally, we would like to keep both s and t small, but there are tradeoffs between the values of s and t that limit the possibilities of keeping both parameters small. In this paper, we consider the case of succinct representations, where s = n + r for some redundancy r ≪ n. For a Boolean version of the problem of polynomial evaluation with preprocessing of coefficients, we show a lower bound on the redundancy–query time tradeoff of the form ( r + 1 ) t ≥ Ω ( n / log n ). In particular, for very small redundancies r, we get an almost optimal lower bound stating that the query algorithm has to inspect almost the entire data structure (up to a logarithmic factor). We show similar lower bounds for problems satisfying a certain combinatorial properties of a coding theoretic flavor, and obtain ( r + 1 ) t ≥ Ω ( n ) for certain problems. Previously, no ω ( m ) lower bounds were known on t in the general model for explicit Boolean problems, even for very small redundancies. By restricting our attention to systematic or index structures ϕ satisfying ϕ ( x ) = x ⋅ ϕ ∗ ( x ) for some map ϕ ∗ (where ⋅ denotes concatenation), we show similar lower bounds on the redundancy–query time tradeoff for the natural data structuring problems of Prefix Sum and Substring Search.

Details DOI

TCS Journal 2005 Journal Article

On converting CNF to DNF

  • Peter Bro Miltersen
  • Jaikumar Radhakrishnan
  • Ingo Wegener

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 minimum number of clauses in a CNF for f; similarly, dnfsize ( f ) denotes the minimum number of terms in a DNF for f. For 0 ⩽ m ⩽ 2 n - 1, let dnfsize ( m, n ) be the maximum dnfsize ( f ) for a function f: { 0, 1 } n → { 0, 1 } with cnfsize ( f ) ⩽ m. We show that there are constants c 1, c 2 ⩾ 1 and ε > 0, such that for all large n and all m ∈ [ 1 ε n, 2 ε n ], we have 2 n - c 1 ( n / log ( m / n ) ) ⩽ dnfsize ( m, n ) ⩽ 2 n - c 2 ( n / log ( m / n ) ). In particular, when m is the polynomial n c, we get dnfsize ( n c, n ) = 2 n - θ ( c - 1 ( n / log n ) ).

Details DOI

MFCS Conference 2004 Conference Paper

Some Meet-in-the-Middle Circuit Lower Bounds

  • Kristoffer Arnsfelt Hansen
  • Peter Bro Miltersen

Abstract We observe that a combination of known top-down and bottom-up lower bound techniques of circuit complexity may yield new circuit lower bounds. An important example is this: Razborov and Wigderson showed that a certain function f in ACC 0 cannot be computed by polynomial size circuits consisting of two layers of MAJORITY gates at the top and a layer of AND gates at the bottom. We observe that a simple combination of their result with the Håstad switching lemma yields the following seemingly much stronger result: The same function f cannot be computed by polynomial size circuits consisting of two layers of MAJORITY gates at the top and an arbitrary AC 0 circuit feeding the MAJORITY gates.

Details

MFCS Conference 2003 Conference Paper

On Converting CNF to DNF

  • 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}, \({\mathsf{cnfsize}}\left(f\right)\) denotes the minimum number of clauses in a CNF for f; similarly, \({\mathsf{dnfsize}}\left(f\right)\) denotes the minimum number of terms in a DNF for f. For 0≤ m ≤ 2 n − 1, let \({\mathsf{dnfsize}}\left(m, n\right)\) be the maximum \({\mathsf{dnfsize}}\left(f\right)\) for a function f: {0, 1} n →{0, 1} with \({\mathsf{cnfsize}}\left(f\right) \leq m\). We show that there are constants c 1, c 2 ≥ 1 and ε > 0, such that for all large n and all \(m \in [ \frac{1}{\epsilon}n, 2^{\epsilon{n}}]\), we have $$ 2^{n -- c_1\frac{n}{\log(m/n)}}~ \leq~ {\mathsf{dnfsize}}(m, n) ~\leq~ 2^{n-c_2 \frac{n}{\log(m/n)}}. $$ In particular, when m is the polynomial n c, we get \({\mathsf{dnfsize}} (n^c, n) = 2^{n -\theta(c^{-1}\frac{n}{\log n})}\).

Details

I&C Journal 2001 Journal Article

Lower Bounds for Dynamic Algebraic Problems

  • 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, …, x n )=(y 1, …, y m ) is an algebraic problem, we consider serving online requests of the form “change input x i to value v” or “what is the value of output y i? ” We present techniques for showing lower bounds on the worst case time complexity per operation for such problems. The first gives lower bounds in a wide range of rather powerful models (for instance, history dependent algebraic computation trees over any infinite subset of a field, the integer RAM, and the generalized real RAM model of Ben-Amram and Galil). Using this technique, we show optimal Ω(n) bounds for dynamic matrix–vector product, dynamic matrix multiplication, and dynamic discriminant and an Ω( n ) lower bound for dynamic polynomial multiplication (convolution), providing a good match with Reif and Tate's O( n log n ) upper bound. We also show linear lower bounds for dynamic determinant, matrix adjoint, and matrix inverse and an Ω( n ) lower bound for the elementary symmetric functions. The second technique is the communication complexity technique of Miltersen, Nisan, Safra, and Wigderson which we apply to the setting of dynamic algebraic problems, obtaining similar lower bounds in the word RAM model. The third technique gives lower bounds in the weaker straight line program model. Using this technique, we show an Ω((log n)2/log log n) lower bound for dynamic discrete Fourier transform. Technical ingredients of our techniques are the incompressibility technique of Ben-Amram and Galil and the lower bound for depth-two superconcentrators of Radhakrishnan and Ta-Shma. The incompressibility technique is extended to arithmetic computation in arbitrary fields.

Details DOI

MFCS Conference 2001 Conference Paper

On Pseudorandom Generators in NC

  • 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 NC 0 circuits where each output bit depends on at most 3 input bits (i. e, DNC 0 3 circuits) and with stretch factor greater than 4 are not pseudorandom. • A large class of “non-problematic” NC 0 generators with superlinear stretch (including all NC 0 3 generators with superlinear stretch) are broken by a statistical test based on a linear dependency test combined with a pairwise independence test. • There is an NC 0 4 generator with a super-linear stretch that passes the linear dependency test as well as k -wise independence tests, for any constant k.

Details

FOCS Conference 1999 Conference Paper

Derandomizing Arthur-Merlin Games Using Hitting Sets

  • Peter Bro Miltersen
  • N. V. Vinodchandran

We prove that AM (and hence Graph Nonisomorphism) is in NP if for some /spl epsiv/>0, some language in NE/spl cap/ coNE requires nondeterministic circuits of size 2/sup en/. This improves results of Arvind and Kobler (1997) and of Klivans and Van Melkebeek (1999) who have proven the same conclusion, but under stronger hardness assumptions, namely, either the existence of a language in NE/spl cap/ coNE which cannot be approximated by nondeterministic circuits of size less than 2/sup en/ or the existence of a language in NE/spl cap/ coNE which requires oracle circuits of size 2/sup en/ with oracle gates for SAT (satisfiability). The previous results on derandomizing AM were based on pseudorandom generators. In contrast, our approach is based on a strengthening of Andreev, Clementi and Rolim's (1996) hitting set approach to derandomization. As a spin-off we show that this approach is strong enough to give an easy (if the existence of explicit dispersers can be assumed known) proof of the following implication: for some /spl epsiv/>0, if there is a language in E which requires nondeterministic circuits of size 2/sup en/, then P=BPP. This differs from Impagliazzo and Wigderson's (1995) theorem "only" by replacing deterministic circuits with nondeterministic ones.

Details

TCS Journal 1999 Journal Article

Fusion trees can be implemented with AC0 instructions only

  • Arne Andersson
  • Peter Bro Miltersen
  • Mikkel Thorup

Addressing a problem of Fredman and Willard, we implement fusion trees in deterministic linear space using AC0 instructions only. More precisely, we show that a subset of {0, …, 2 w - 1} of size n can be maintained using linear space under insertion, deletion, predecessor, and successor queries, with O( log n log log n ) amortized time per operation on a RAM with word size w, where the only computational instructions allowed on the RAM are functions in AC0. The AC0 instructions used are not all available on today's computers.

Details DOI

FOCS Conference 1996 Conference Paper

Static Dictionaries on AC 0 RAMs: Query Time Theta(sqrt(log n/log log n)) is Necessary and Sufficient

  • Arne Andersson
  • Peter Bro Miltersen
  • Søren Riis
  • Mikkel Thorup

In this paper we consider solutions to the static dictionary problem on AC/sup 0/ RAMs, i. e. random access machines where the only restriction on the finite instruction set is that all computational instructions are in AC/sup 0/. Our main result is a tight upper and lower bound of /spl theta/(/spl radic/log n/log log n) on the time for answering membership queries in a set of size n when reasonable space is used for the data structure storing the set; the upper bound can be obtained using O(n) space, and the lower bound holds even if we allow space 2/sup polylog n/. Several variations of this result are also obtained. Among others, we show a tradeoff between time and circuit depth under the unit-cost assumption: any RAM instruction set which permits a linear space, constant query time solution to the static dictionary problem must have an instruction of depth /spl Omega/(log w/log log to), where w is the word size of the machine (and log the size of the universe). This matches the depth of multiplication and integer division, used in the perfect hashing scheme by M. L. Fredman, J. Komlos and E. Szemeredi (1984).

Details

TCS Journal 1995 Journal Article

On the cell probe complexity of polynomial evaluation

  • Peter Bro Miltersen

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 probe algorithm for the problem is optimal if K is sufficiently large compared to n. As an application, we give a new proof of the fact that P ≠ incr-TIME(o(logn/log logn)).

Details DOI

TCS Journal 1994 Journal Article

Complexity models for incremental computation

  • 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 existing complexity classes. We show that problems that have small sequential space complexity also have small incremental time complexity. We show that all common LOGSPACE-complete problems for P are also incr-POLYLOGTIME-complete for P. We introduce a restricted notion of completeness called NRP-completeness and show that problems which are NRP-complete for P are also incr-POLYLOGTIME-complete for P. We also give incrementally complete problems for NLOGSPACE, LOGSPACE, and nonuniform NC1. We show that under certain restrictions problems which have efficient dynamic solutions also have efficient parallel solutions. We also consider a nonuniform model of incremental computation and show that in this model most problems have almost linear complexity. In addition, we present some techniques for lower bounding the complexity of explicitly defined problems. We also look at the time complexity of circuit-value and network-stability problems restricted to comparator gates. We show that the comparator-circuit value problem and the “lex-first maximal matching” problem are in incr-LOGSPACE while the comparator-network stability and the “man-optimal stable marriage problem” are in rincr-LOGSPACE(NLOGSPACE). This shows that the dynamic versions of these problems are solvable quickly in parallel even though there are no known NC algorithms to solve them from scratch.

Details DOI

FOCS Conference 1993 Conference Paper

Dynamic Word Problems

  • 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/sub 1/, x/sub 2/, .. ., x/sub n/)/spl isin/M/sup n/, initially (1, 1, .. ., 1) with two kinds of operations, for each i/spl isin/{1, .. ., n}, a/spl isin/M, an operation change/sub i, a/ which changes x/sub i/ to a and a single operation product returning /spl Pi//sub i=1//sup n/x/sub i/. This is the dynamic word problem. If we in addition for each j/spl isin/{1, .. ., n} have an operation prefix/sub j/ returning /spl Pi//sub i=1//sup j/x/sub i/, we talk about the dynamic prefix problem. We analyze the complexity of these problems in the cell probe or decision assignment tree model for two natural cell sizes, 1 bit and log n bits. We obtain a classification of the complexity based on algebraic properties of M. >

Details

MFCS Conference 1993 Conference Paper

The Complexity of Finding Replicas Using Equality Tests

  • Gudmund Skovbjerg Frandsen
  • Peter Bro Miltersen
  • Sven Skyum

Abstract We prove (for fixed k ) that at least \(\tfrac{1}{{k - 1}}(\begin{array}{*{20}c}n \\2 \\\end{array} ) - O(n)\) equality tests and no more than \(\tfrac{2}{k}(\begin{array}{*{20}c}n \\2 \\\end{array} ) + 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 improvement by a factor 2 compared to known results. We give tighter bounds for k =3.

Details

FOCS Conference 1992 Conference Paper

The Asymptotic Complexity of Merging Networks

  • Peter Bro Miltersen
  • Mike Paterson
  • Jun Tarui

Let M(m, n) be the minimum number of comparators needed in a comparator network that merges m elements x/sub 1/ or=m. Batcher's odd-even merge yields the following upper bound: M(m, n) or=m to infinity: M(m, n)>or=/sup 1///sub 2/(m+n)log/sub 2/(m+1)-O(m); in particular, M(n, n)>or=nlog/sub 2/n-O(n). The authors' proof technique extends to give similarly tight lower bounds for the size of monotone Boolean circuits for merging, and for the size of switching networks capable of realizing the set of permutations that arise from merging. >

Details
v2026.09.13