Views and normal forms

Views

The truth table. Subset of the hypercube. The concept.

A set system: Can consider c as a set: set of ‘selected’ points, induces dichotomies on X.

Social (binary) choice or voting scheme of n people.

Normal forms

Write as sign of multinomial of n variables

$x\in {\{0,1\}}^n$. Take DNF, change $\overline{x_i}\to (1-x_i)$.

k-DNF and k-CNF

$k\le n$. DNF is a disjunction of conjunctions. CNF is a conjunction of disjunctions.

Derivation from truth tables.

DNF $c$ for boolean function $f$ is obtainable from truth table of $f$: $\{x:f(x)=0\}$.

CNF $d$ for boolean function $f$ is obtainable from truth table of f: get the CNF of $\overline{f}(x)$, negate it to get a $d$.

Connection between DNF and CNF.

Any term in $d$ and any clause in $c$ cannot be disjoint \why.

$t$ term CNF can be reduced to $t$-DNF using distributive laws.

t-DNF to t-term CNF is also possible, but this may take exponential time as $RP\ne NP$: See colt ref about hardness of proper learning k-DNF.

Minimization of number of terms

Drawing rectangles in Karnaugh / Veitch tables.

\paragraph*{Minterms and maxterms} Minterms of a DNF are terms such that: Each var appears $\le 1$ times. Maxterms of a CNF are similarly define. So, a minimal DNF is a sum of minterms, while the minimal CNF is a product of maxterms.

A minterm as ${\{\pm 1\}}^n$ fn: $\prod (\frac{1+x_i}{2})$. Constant term is coefficient of $p_{\varphi }:=1$.

DNF norm

In the uniform distr fn space, Mansour’s conjecture: \ $\mathrm{\exists }$ polynomial p: ${\parallel DNF\parallel }_1\le O(n^{\frac{1}{ϵ}});{\parallel f-p\parallel }^2\le ϵ$.

Size s DNF f

Aka s-term DNF. Some notation: Term-length t, terms $T_i$, s = size(f) = num of terms: maybe poly(n), n variables.

Actual representation size $\le ns\log n$.

$|k-DNF|\le (2n{)}^k$: count the number of possible ways to make a k-DNF.

Number of functions: $O((\genfrac{}{}{0ex}{}{3^n}{s}))=O(3^{ns})$. So, number of polysize DNF: $‘3^{n^{O(\log n)}}$.

t-DNF reducible to disjunction upon feature expansion. With distributive laws, size s DNF reducible to s-CNF and thence to negation of s-DNF. Negation of size s DNF is size s CNF.

Strictly more expressive than decision lists: \why: so more powerful.

DNF f to l-augmented Decision tree of rank \htext{\(\leq \frac{2n{l}\log s + 1\)}{}}

Let p = terms of length $>l$, make most commonly occuring literal $x_i$ in the p terms (occurs atleast in $\frac{pl}{2n}$ by pigeon hole), make kids DNF’s with $x_i$ set to 0 (make many terms disappear) and 1; repeat till all terms have lower term length: rank r(n, p) increases when r(kids): $r(n-1,p-\frac{pl}{2n})$ and r(n-1,p) are same; r(n,0) = r(0, p) = 0; solving recurrance, rank $\le \frac{2n}{l}\log s+1$.

DNF f to PTF

$sign(T_1\cdots +T_s-2^{-1})$. So, Any f needs $\le n$ PTF: Any f is at most n-DNF.

Has PTF of degree $O(\sqrt{t}\log s)$: Let $T_i=x_1\dots x_t,a_i(\overline{x})=\frac{x_1+\dots x_t}{t}$, Chebyshev pol (see Approx theory sheet) $C_{\sqrt{t}}((1+t^{-1})a_i(\overline{x}))=Q_i,deg(Q_i)=\sqrt{t}$; for $T_i(x)=1,|Q_i|\ge 2$, else $|Q_i|\le 1$; PTF is $\sum Q_i^{\log s}-s-2^{-1}$.

Has $O(n^{1/3}\log s)$ PTF: \ Make $n^{2/3}$ augmented Decision tree of rank $2n^{1/3}\log s+1$; change each $n^{2/3}$ DNF at leaf to $n^{1/3}\log s$ PTF; change Decision tree to $2n^{1/3}\log s+2$ Decision list (k long, terms: \({T’{i}}\)) which output PTF’s \({P{i}}\); $\mathrm{\exists }$ PTF with polynomial \(2^{k}T’{1}P{1} + 2^{k-1}T’{2}P{2} \dots\) of degree $O(2n^{1/3}\log s+n^{1/3}\log s)$.

Lower bounds on PTF degree

f = parity fn: ${0,1}^n\to \pm 1$, an $O(2^n)$ size DNF needs n PTF: Let sign(Q(x)) be parity PTF: $x_i^2=x^i$, so all polynomials (even Q(x)) multilinear; $Q(x)=Q(\pi (x))$; let $Q^{\prime }(x)=\sum _{\pi }Q(\pi (x_1\dots x_i))$; Q’ symmetric, sign(Q’) computes parity, degree(Q’) = degree(Q); $Q^{\prime }(x)=Q^{}{\prime }^{\prime }(\sum x_i)$; $Q^{}{\prime }^{\prime }(0)<0,Q^{}{\prime }^{\prime }(1)>0,Q^{}{\prime }^{\prime }(2)<0\dots$; so Q’’ has n roots; so Q’, Q has degree n.

Some polysize DNF in n variables needs PTF of degree $n^{1/3}$: DNF f = ‘1 in a box’ fn (Minsky, Papert): $s=m;T_i=\underset{j=1}{\overset{4m^2}{\bigwedge }}{x}_{i,j}$; let $x_i$ be variables in box $T_i$; let sign(Q(x)) be PTF for f; $Q^{\prime }(x)=\sum _{{\pi }_{1,i}\dots {\pi }_{m,i^{\prime }}}Q({\pi }_{1,i}(x_1),\dots {\pi }_{m,i^{\prime }}(x_m))$; sign(Q’) also is f, degree(Q’) same; $Q^{}{\prime }^{\prime }(\sum x_{1,i},\dots \sum x_{m,i})$ with same degree $Q^{}{\prime }^{\prime }(x)>0$ iff $\sum x_{1,i}\ge 4m^2$; let $p(t)=Q^{}{\prime }^{\prime }(4m^2-(t-1{)}^2,4m^2-(t-3{)}^2\dots 4m^2-(t-(2m-1){)}^2)$; $deg(p)=2\ast deg(Q^{}{\prime }^{\prime })$; $p(1)>0,p(2)<0,p(3)>0\dots$; $degree(p)\ge 2m$, so $deg(Q)\ge m$.

Boolean circuits (ckt)

A DAG with $n$ inputs: $C_n$; internal nodes represent logic gates/ operations; directed edges represent inputs and outputs to these nodes. Circuit basis: the gates: usually AND, OR. Bounded vs unbounded fanin. Size and depth of ckt.

Using De Morgan’s laws, any ckt can be changed to have all NOT gates at input. Ckt with bounded fan in $k$ can be changed to have bounded fan in 2 with constant blowup in depth. Unbounded fanin ckt convertible to bounded fanin ckt with $\log (size(ckt))$ blowup in depth.

Turing machine halting in time $T(n)$ convertible to ckt of depth $T(n)$ and size $(T(n){)}^2$.

Boolean formula f

Aka Boolean expressions, tree like circuits. Subset of Boolean circuits: Only 1 output per gate. Can be rewritten as a 3 CNF.

Balance tree-like circuits, reduce depth

(Spira): Take tree O with n nodes, find subtree A with (2/3)n nodes; A could be T or F: create 2 trees BT, BF out of the other n/3 nodes with either A=T or A=F; Now, $O=(A\wedge BT)\vee (\sim A\wedge BF)$; keep repeating this for A, BF, BT to get tree of depth $lo{g}_{\frac{3}{2}}n$.

Turing machines

See Computational Complexity ref.