We give a simpler proof, via query elimination, of a result due to O'Donnell, Saks, Schramm and Servedio, which shows a lower bound on the zero-error randomized query complexity of a function $f$ in terms of the maximum influence of any variable of $f$. Our lower bound also applies to ... more >>>

In recent results the complexity of isomorphism testing on
graphs of bounded treewidth is improved to TC$^1$ [GV06] and further to LogCFL [DTW10].
The computation of canonical forms or a canonical labeling provides more information than
isomorphism testing.
Whether canonization is in NC or even TC$^1$ was stated ... more >>>

This paper characterizes alternation trading based proofs that satisfiability is not in the time and space bounded class $\DTISP(n^c, n^\epsilon)$, for various values $c<2$ and $\epsilon<1$. We characterize exactly what can be proved in the $\epsilon=0$ case with currently known methods, and prove the conjecture of Williams that $c=2\cos(\pi/7)$ is ... more >>>