We observe that if we allow for the use of
division and the floor function
besides multiplication, addition and
subtraction then we can
compute the arithmetic convolution
of two n-dimensional integer vectors in O(n) steps and
perform the arithmetic matrix multiplication
of two integer n times n matrices ... more >>>

We show $\Omega(n^2)$ lower bounds on the total space used in resolution refutations of random $k$-CNFs over $n$ variables, and of the graph pigeonhole principle and the bit pigeonhole principle for $n$ holes. This answers the long-standing open problem of whether there are families of $k$-CNF formulas of size $O(n)$ ... more >>>

We study which functions can be computed by efficient circuits whose gate connections are very easy to compute. We give quasilinear-size circuits for sorting whose connections can be computed by decision trees with depth logarithmic in the length of the gate description. We also show that NL has NC$^2$ circuits ... more >>>