We consider the reachability problem for a certain class of directed acyclic graphs embedded on surfaces. Let ${\cal G}(m,g)$ be the class of directed acyclic graphs with $m = m(n)$ source vertices embedded on a surface (orientable or non-orientable) of genus $g = g(n)$. We give a log-space reduction that ... more >>>

We initiate the study of the proof complexity of propositional encoding of (weak cases of) concrete independence results. In particular we study the proof complexity of Paris-Harrington's Large Ramsey Theorem. We prove a conditional lower bound in Resolution and a quasipolynomial upper bound in bounded-depth Frege.

more >>>

We study the complexity of polynomial multiplication over arbitrary fields. We present a unified approach that generalizes all known asymptotically fastest algorithms for this problem. In particular, the well-known algorithm for multiplication of polynomials over fields supporting DFTs of large smooth orders, Schönhage-Strassen's algorithm over arbitrary fields of characteristic different ... more >>>