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

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

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