We propose a new definition of the class of search problems that correspond to BPP.
Specifically, a problem in this class is specified by a polynomial-time approximable function $q:\{0,1\}^*\times\{0,1\}^*\to[0,1]$ that associates, with each possible solution $y$ to an instance $x$, a quality $q(x,y)$.
Intuitively, quality 1 corresponds to perfectly ... more >>>

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