<p>I am working on a problem and I am looking to solve the following subproblem : Given a &quot;restrictive&quot; blackbox access to boolean function <span class="math-container">$\phi$</span>, output a &quot;small-sized&quot; CNF that <em>reasonably</em> approximates <span class="math-container">$\phi$</span>.</p>
<p>More precisely, suppose <span class="math-container">$\phi:\{0,1\}^n\to \{0,1\}$</span> and we can somehow sample from the assignments that make <span class="math-container">$\phi$</span> true. Given a parameter <span class="math-container">$m$</span>, can we find a CNF formula <span class="math-container">$\hat\phi$</span> with at most <span class="math-container">$m$</span> clauses such that the distance (say the total variation distance or something similar) between <span class="math-container">$\phi$</span> and <span class="math-container">$\hat\phi$</span> is small (may depend on <span class="math-container">$m$</span>) and uses small amount of samples?</p>
<p>I was thinking of using some form of a decision tree learning model to do the job, but I can't really see how to do it exactly. Nor can I find any literature on the same.</p>
<p>Any help is appreciated!</p>

CC BY-SA 4.0
2024-08-04T16:05:24.523Z
This seems relevant (though may be an incomparable requirement wrt learning guarantee): https://www.cs.columbia.edu/~rocco/papers/soda15.html
Clement C.
CC BY-SA 4.0
2024-08-05T03:49:04.597Z
Related: https://cs.stackexchange.com/q/22122/755
D.W.
<machine-learning><boolean-functions><boolean-formulas><decision-trees>
Learning a boolean function using decision tree with small number of queries
AlternatingGroupoid
# Learning a boolean function using decision tree with small number of queries

(Asked by: username_0 on 2024-08-04)

I am working on a problem and I am looking to solve the following subproblem : Given a "restrictive" blackbox access to boolean function $\phi$, output a "small-sized" CNF that *reasonably* approximates $\phi$.

More precisely, suppose $\phi:\{0,1\}^n\to \{0,1\}$ and we can somehow sample from the assignments that make $\phi$ true. Given a parameter $m$, can we find a CNF formula $\hat\phi$ with at most $m$ clauses such that the distance (say the total variation distance or something similar) between $\phi$ and $\hat\phi$ is small (may depend on $m$) and uses small amount of samples?

I was thinking of using some form of a decision tree learning model to do the job, but I can't really see how to do it exactly. Nor can I find any literature on the same.

Any help is appreciated!

**Tags:** machine-learning, boolean-functions, boolean-formulas, decision-trees

> **Comments:**
> **username_1**: This seems relevant (though may be an incomparable requirement wrt learning guarantee): https://www.cs.columbia.edu/~rocco/papers/soda15.html  
> **username_2**: Related: https://cs.stackexchange.com/q/22122/755  

---

## 0 answers

