All reports by Author Peter Bro Miltersen:

__
TR13-107
| 7th August 2013
__

Gil Cohen, Ivan Bjerre Damgard, Yuval Ishai, Jonas Kolker, Peter Bro Miltersen, Ran Raz, Ron Rothblum#### Efficient Multiparty Protocols via Log-Depth Threshold Formulae

__
TR06-004
| 6th January 2006
__

Jesper Torp Kristensen, Peter Bro Miltersen#### Finding small OBDDs for incompletely specified truth tables is hard

__
TR05-037
| 8th April 2005
__

Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, Peter Bro Miltersen#### On the Complexity of Numerical Analysis

Revisions: 1
,
Comments: 1

__
TR05-032
| 16th March 2005
__

Gudmund Skovbjerg Frandsen, Peter Bro Miltersen#### Reviewing Bounds on the Circuit Size of the Hardest Functions

__
TR03-017
| 27th March 2003
__

Peter Bro Miltersen, Jaikumar Radhakrishnan, Ingo Wegener#### On Converting CNF to DNF

__
TR02-066
| 24th October 2002
__

Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, V Vinay#### Circuits on Cylinders

__
TR97-044
| 26th September 1997
__

David Mix Barrington, Chi-Jen Lu, Peter Bro Miltersen, Sven Skyum#### Searching constant width mazes captures the AC^0 hierarchy

Gil Cohen, Ivan Bjerre Damgard, Yuval Ishai, Jonas Kolker, Peter Bro Miltersen, Ran Raz, Ron Rothblum

We put forward a new approach for the design of efficient multiparty protocols:

1. Design a protocol for a small number of parties (say, 3 or 4) which achieves

security against a single corrupted party. Such protocols are typically easy

to construct as they may employ techniques that do not ...
more >>>

Jesper Torp Kristensen, Peter Bro Miltersen

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 for any integer m,

G has a vertex colouring using m colours if and only if g ...
more >>>

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 following problem,

which we call PosSLP:

Given a division-free straight-line program

producing an integer N, decide whether N>0.

more >>>

Gudmund Skovbjerg Frandsen, Peter Bro Miltersen

In this paper we review the known bounds for $L(n)$, the circuit size

complexity of the hardest Boolean function on $n$ input bits. The

best known bounds appear to be $$\frac{2^n}{n}(1+\frac{\log

n}{n}-O(\frac{1}{n})) \leq L(n) \leq\frac{2^n}{n}(1+3\frac{\log

n}{n}+O(\frac{1}{n}))$$ However, the bounds do not seem to be

explicitly stated in the literature. We ...
more >>>

Peter Bro Miltersen, Jaikumar Radhakrishnan, Ingo Wegener

The best-known representations of boolean functions f are those of disjunctions of terms (DNFs) and as conjuctions of clauses (CNFs). It is convenient to define the DNF size of f as the minimal number of terms in a DNF representing f and the CNF size as the minimal number of ... more >>>

Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, V Vinay

We consider the computational power of constant width polynomial

size cylindrical circuits and nondeterministic branching programs.

We show that every function computed by a Pi2 o MOD o AC0 circuit

can also be computed by a constant width polynomial size cylindrical

nondeterministic branching program (or cylindrical circuit) and

that ...
more >>>

David Mix Barrington, 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 application,

we show that there is a data structure solving dynamic st-connectivity

for constant ...
more >>>