In this paper we study syntactic branching programs of bounded repetition
representing CNFs of bounded treewidth.
For this purpose we introduce two new structural graph
parameters $d$-pathwidth and clique preserving $d$-pathwidth denoted
by $pw_d(G)$ and $cpw_d(G)$ where $G$ is a graph.
We show that $cpw_2(G) \leq O(tw(G) \Delta(G))$ ... more >>>

We survey recent and classical results and techniques concerning binary codes in the large distance (or, high-noise) regime, and the closely related notion of $\varepsilon$-balanced codes. Our (hopefully small-biased) column will mainly discuss encoding, and decoding from adversarial errors.

A previous version of this text originally appeared as an ACM ... more >>>

We study uniquely decodable codes and list decodable codes in the high-noise regime, specifically codes that are uniquely decodable from $\frac{1-\varepsilon}{2}$ fraction of errors and list decodable from $1-\varepsilon$ fraction of errors. We present several improved explicit constructions that achieve near-optimal rates, as well as efficient or even linear-time decoding ... more >>>