<p>A well-known fact is that if a function f is computable by a k-CNF and an l-DNF then it can be computed by a tree of depth at most kl. Long time ago I heard the problem what happens if the CNF and DNF only compute f with some small error $\epsilon&gt;0$. Is there a shallow tree computing f with a small error? (I am not sure that the problem was posed in this way, but this is the question I am interested in.)</p>

CC BY-SA 3.0
2015-11-18T02:23:33.630Z
What is the notion of error? I.e., what does it mean for a k-CNF to compute a function f with error $\epsilon$?
Robin Kothari
CC BY-SA 3.0
2015-11-18T08:52:11.270Z
I think it means that the output has to be correct for at least $(1-\epsilon)\cdot 2^n$ of the inputs.
Jan Johannsen
CC BY-SA 3.0
2015-11-19T11:12:00.457Z
You can use the fact that k-CNF can be approximated by an exp(k)-junta, and same for l-DNF, but I suppose you want a better something better than exponential depth.
Igor Shinkar
CC BY-SA 3.0
2015-12-08T09:42:14.173Z
Smyth has shown a result like this: http://dl.acm.org/citation.cfm?doid=509907.509942
Robin Kothari
<circuit-complexity>
Boolean functions computed approximately by k-CNFs and l-DNFs and the depth of trees
Pavel Pudlak
# Boolean functions computed approximately by k-CNFs and l-DNFs and the depth of trees

(Asked by: username_0 on 2015-11-18)

A well-known fact is that if a function f is computable by a k-CNF and an l-DNF then it can be computed by a tree of depth at most kl. Long time ago I heard the problem what happens if the CNF and DNF only compute f with some small error $\epsilon>0$. Is there a shallow tree computing f with a small error? (I am not sure that the problem was posed in this way, but this is the question I am interested in.)

**Tags:** circuit-complexity
> **Comments:**
> **username_1**: What is the notion of error? I.e., what does it mean for a k-CNF to compute a function f with error $\epsilon$?  
> **username_2**: I think it means that the output has to be correct for at least $(1-\epsilon)\cdot 2^n$ of the inputs.  
> **username_3**: You can use the fact that k-CNF can be approximated by an exp(k)-junta, and same for l-DNF, but I suppose you want a better something better than exponential depth.  
> **username_1**: Smyth has shown a result like this: http://dl.acm.org/citation.cfm?doid=509907.509942  

---

## 0 answers

