The tag has no wiki summary.

learn more… | top users | synonyms

4
votes
0answers
366 views

k-CNF ←→ k-DNF conversion to minimize errors

the following problem/question seems fundamental/hard. it appears in some circuit theory proofs, graph theory, and maybe elsewhere. looking for any nontrivial insight. will add various known/nearby ...
2
votes
2answers
190 views

Size of decision tree for f is polynomial in the DNF size of f and CNF size of f

I've been having hard time with proving the following claim: Let $f:\{T,F\}^n\rightarrow \{T,F\}$ be a boolean function. Let $size_{DT}(f)$ denote the number of leaves in the smallest (w.r.t the ...
9
votes
1answer
202 views

Boolean formula balancing in $\mathsf{AC^0}$

I am looking for references about the complexity of Boolean formula balancing problem. In particular, Was it known that Boolean formulas can be balanced in $\mathsf{AC^0}$? Is there a simple proof ...