Electronic Colloquium on Computational Complexity
Login | Register | Classic Style

RSS-FeedNext next

TR17-034 | 21st February 2017
Karl Bringmann, Christian Ikenmeyer, Jeroen Zuiddam

On algebraic branching programs of small width

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

TR17-033 | 19th February 2017
Daniel Kane, Shachar Lovett, Sankeerth Rao

Labeling the complete bipartite graph with no zero cycles

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

TR17-032 | 17th February 2017
Olaf Beyersdorff, Joshua Blinkhorn

Formulas with Large Weight: a New Technique for Genuine QBF Lower Bounds

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

Next next

ISSN 1433-8092 | Imprint