6
$\begingroup$

Let $B=\{0,1\}$. A read-once branching program of width $n$ and size $w$ is given by a graph with layers $0,\ldots, n$, where the first layer has just the starting node, the last layer has nodes labeled 0 and 1, each layer has $\le w$ nodes, and each node has 2 edges labeled 0 and 1 pointing to nodes in the next layer. To evaluate the program on $x_1\ldots x_n$, simply start at the start node and follow the edges labeled $x_1,x_2,\ldots$, and read the label on the last node. Fix $n$, and let $w$-ROBP be the class of width $w$ read-once branching programs (and by abuse of notation, the functions computed by them).

Question:

Find an $\text{poly}(n,\epsilon)$ algorithm (or else show it would break some hardness assumption) such that given $f:B^n\to B$ as a black box, it computes $g\in w$-ROBP with high probability such that

$$ \mathbb{P}_{x\sim B^n}(g(x)\ne f(x))\le \min_{h\in w\text{-ROBP}} \mathbb{P}_{x\sim B^n}(h(x)\ne f(x)) + \epsilon. $$

In other words, find an agnostic PAC-learning algorithm for $w$-ROBP. Even a weaker bound depending on $\min_{h\in w\text{-ROBP}} \mathbb{P}_x(h(x)\ne f(x))$ would be interesting. I'm convinced that I have an algorithm for when $f\in w$-ROBP (so that the max is 0) but it doesn't generalize to this setting.

A quick literature search shows intractability results for more powerful classes such as width 3 (read-many) branching programs, and learning algorithms for finite automata (which are ROBP's with each layer the same), and not much on ROBP's. I would also appreciate any other results/references on learning for ROBP's.

$\endgroup$
  • 2
    $\begingroup$ It might help you to know that read once branching programs are also called "OBDD" in some of the literature. A google search for OBDD learning comes up with some results that seem relevant. $\endgroup$ – mobius dumpling Mar 29 '15 at 20:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.