Privacy-Enhancing First-Price Auctions Using Rational Cryptography (2009)
Peter Bro, Miltersen Jesper, Buus Nielsen, Nikos Triandopoulos
We consider enhancing a sealed-bid single-item auction with privacy concerns, our assumption being that bidders primarily care about monetary payoff and secondarily worry about exposing information...
Arne Andersson, Peter Bro, Miltersent Soren, Riis Mikkel Thorup
In this paper we consider solutions to the static dictionary problem on ACo RAMs, i.e. random access machines where the only restriction on theJinite instruction set is that all computationcil...
On Data Structures and Asymmetric Communication Complexity ∗ (2008)
Peter Bro, Miltersen Noam, Nisan Shmuel, Safra Avi Wigderson
In this paper we consider two party communication complexity when the input sizes of the two players differ significantly, the “asymmetric ” case. Most of previous work on communication...
Complexity Models for Incremental Computation \Lambda (2008)
Peter Bro, Milterseny Sairam Subramanianz, Jeffrey Scott, Vitter Roberto Tamassiax
Abstract 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...
Guillaume Escamocher, Peter Bro
In classical auction theory, the existence of pure strategy Nash equilibria (PSNE) of first-price auctions has been established under a variety of mild conditions. Nevertheless, known general...
is in NP if for some > 0, some language in NE \ coNE requires nondeterministic circuits of size 2
On converting CNF to DNF (2007)
Peter Bro, Miltersen Jaikumar, Radhakrishnan Ingo Wegener
The best-known representations of boolean functions f are those as disjunctions of terms (DNFs) and as conjunctions of clauses (CNFs). It is convenient to define the DNF size of f as the minimal...
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...
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...
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...
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...
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.:
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...
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...