People who code: we want your input. Take the Survey

Tag Info

Let $\land_p$ be a gate with error $p$ only when the inputs are $1$ and $0$. What can we say about $$(x \land_p y) \land_p (x \land_p y)?$$ If $x=y=1$ then we always get $1$. If $x = 0$ then we always get $0$. When $x = 1$ and $y = 0$, we get the wrong answer $1$ with probability $$p \cdot p + p \cdot (1-p) \cdot p = p^2(2-p).$$ Call that function $f(p)$....
A comparator circuit is a circuit computing a function on $x_1,\ldots,x_n \in \{0,1\}^n$. The inputs to the circuit are labeled with either constants ($0$ or $1$), inputs ($x_1,\ldots,x_n$) or negated inputs ($\lnot x_1,\ldots,\lnot x_n$). The only allowed gate is a comparator gate, which has two inputs $a,b$ and two outputs $a\land b,a\lor b$. The circuit ...