In 1979 Valiant showed that the complexity class VP_e of families with polynomially bounded formula size is contained in the class VP_s of families that have algebraic branching programs (ABPs) of polynomially bounded size. Motivated by the problem of separating these classes we study the topological closure VP_e-bar, i.e. the ... more >>>

Assume that the edges of the complete bipartite graph $K_{n,n}$ are labeled with elements of $\mathbb{F}_2^d$, such that the sum over
any simple cycle is nonzero. What is the smallest possible value of $d$? This problem was raised by Gopalan et al. [SODA 2017] as it characterizes the alphabet size ... more >>>

We devise a new technique to prove lower bounds for the proof size in resolution-type calculi for quantified Boolean formulas (QBF). The new technique applies to the strong expansion system IR-calc and thereby also to the most studied QBF system Q-Resolution.

Our technique exploits a clear semantic paradigm, showing the ... more >>>