Certification for Quantified Boolean Formulas (QBF) and Dependency Quantified Boolean Formulas is an ongoing challenge (DQBF). Recent proof complexity work has shown that the majority of QBF and DQBF techniques can be p-simulated by using the independent extension rule. In propositional logic, extension rules are supported by proof checkers using ... more >>>

In this column, we overview recent progress by many authors on understanding the approximability of constraint satisfaction problems (CSPs) in low-space streaming models. Inspired by this recent progress, we collate nine conjectural lower bounds against streaming algorithms for CSPs, some of which appear here for the first time.

more >>>

Prange's information set algorithm is a decoding algorithm for arbitrary linear codes. It decodes corrupted codewords of any $\mathbb{F}_2$-linear code $C$ of message length $n$ up to relative error rate $O(\log n / n)$ in $\poly(n)$ time. We show that the error rate can be improved to $O((\log n)^2 / ... more >>>