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 has a consistent ... more >>>

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. We show ... more >>>

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

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

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 every ... more >>>

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 width grid ... more >>>