All reports by Author Gudmund Skovbjerg Frandsen:

__
TR05-032
| 16th March 2005
__

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

__
TR97-009
| 12th March 1997
__

Jonathan F. Buss, Gudmund Skovbjerg Frandsen, Jeffrey O. Shallit#### The Computational Complexity of Some Problems of Linear Algebra

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 >>>

Jonathan F. Buss, Gudmund Skovbjerg Frandsen, Jeffrey O. Shallit

We consider the computational complexity of some problems

dealing with matrix rank. Let E,S be subsets of a

commutative ring R. Let x_1, x_2, ..., x_t be variables.

Given a matrix M = M(x_1, x_2, ..., x_t) with entries

chosen from E union {x_1, x_2, ..., ...
more >>>