# Tag Info

4

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)$....

3

$\def\co{\mathrm{co}}\def\poly{\mathrm{poly}}\def\N{\mathbb N}$A language $L$ is in $(C/\poly)\cap(\co C/\poly)$ iff there are languages $$L_0\in C,\qquad L_1\in\co C,$$ and sequences of advice strings $\{a_{0,n}:n\in\N\}$, $\{a_{1,n}:n\in\N\}$ such that $$|a_{0,n}|,|a_{1,n}|=n^{O(1)},$$ and for any $n\in\N$ and $w\in\{0,1\}^n$, w\in L\iff(w,a_{0,n})\in ...

2

The idea is to "move backwards" all the not gate. Assume you have some circuit, for example $(\cdot,\cdot)\rightarrow AND\rightarrow NOT\rightarrow OUTPUT$ Can be converted to: $(\cdot \rightarrow NOT,\cdot \rightarrow NOT)\rightarrow OR\rightarrow OUTPUT$ Doing this without thought can increase the circuit size exponentially. So, when you see two $... 1 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 ...

Only top voted, non community-wiki answers of a minimum length are eligible