A multi-start heuristic for multiplicative depth minimization of boolean circuits

@inproceedings{carpov2017multi,
  title={A multi-start heuristic for multiplicative depth minimization of boolean circuits},
  author={Carpov, Sergiu and Aubry, Pascal and Sirdey, Renaud},
  booktitle={International Workshop on Combinatorial Algorithms},
  pages={275--286},
  year={2017},
  organization={Springer},
  url={https://eprint.iacr.org/2017/483.pdf}
}

multiplicative depth
最小化のアルゴリズム,
multi-start heuristicの提案論文

Multiplicative depth-2 path rewriting

(
Faster homomorphic encryption is not enough: improved heuristic for multiplicative depth minimization of Boolean circuits
より)
$p=(v_1,U_y,v_t)$
はANDゲート
$v_1$
から ANDゲート
$v_t$
までのパス
その中には multi-input XORゲート
$U_y$
が入力
$v_1,y_1,\cdots y_m$
を持っている.
(一般性を損なわないように，最初の回路の中間的な2入力XORゲートを，1つの多入力XORゲートにまとめました)
$v_1$
の入力
$a_1,a_2(l(a_1)\ge l(a_2))$
,
$a_3$
は
$v_t$
の入力, その他は
$U_t$
の入力(図1右, 太線は
critical path
)
$p$
を論理式にすると

$$((a_1\cdot a_2)\oplus \underset{i}{⨁}{y}_i)\cdot a_3$$

これを

$$((a_2\cdot a_3)\cdot a_1)\oplus (a_3\cdot \underset{i}{⨁}{y}_i)$$

にしたい.
$a_1$
から
$r$
までの局所的な
mult-depth
は1減っている(まあそう)
→ critical path変わらないのか？

$$mi{n}_{u\in pred(v)}l(u)<l(v_1)-1,v\in \{v_1,v_t\}$$

が成り立っているなら
mean:
$v_1,v_t$
は子孫がANDが1個より少ない=
$v_1,v_t$
がANDノードであればいい
multi-input XORゲートは書き換えた後ツリー状に並び替えることで２入力ゲートを得られる(順不同).
特殊な例について説明する.
もし, パス
$p$
が一つもXORノードを持っていないとき変形結果は
$(a_2\cdot a_3)\cdot a_1$
になる.
もし,
$U_y$
が2入力XORゲートなら消え, ANDゲート
$u_y$
は
$y_1$
と
$a_3$
を入力とする.

変形後のmult-depth

$l(r)=l(a_1)+2$
, (2)が成り立つなら

$$r=\max (l(a_1),l(y_1),\cdots l(y_m))+1$$

になる.
ノード
$y_i(i=1\cdots m)$
が変換前に
critical path
の上にあるなら
mult-depth
は保たれる

→減らせない
$r$
を
$l(a_1)+2$
から
$l(a_1)+1$
に減らすために 少なくとも1回別の
$u_y$
で終わる別の
Multiplicative depth-2 path rewriting
が必要(例えば図左側)

$y_1$
が
critical-path
上にあったらdepthは変わらず

->
critical-path
に属している
$U_y$
の各入力に対してpath-rewritingが必要になるから

A multi-start heuristic for multiplicative depth minimization of boolean circuits
の著者は，中間ノード
$y_1\cdots y_m$
の
mult-depth
2のパスの特殊なケースのみを研究した.

このため，この演算子の適用範囲は狭く，また，パスの書き換え回数を減らすために必要な演算子の適用範囲が限定され，乗算深さを減らすために必要なパスの書き換え回数も限定される．