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

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, ..., x_t}, we want to ... more >>>