Cone Rewriting

概要

Faster homomorphic encryption is not enough: improved heuristic for multiplicative depth minimization of Boolean circuits
で定義

Multiplicative depth-2 cone rewriting
の一般化

Cone selection method

cone 選択手法は書き換えるべき最小の coneの集合を見つけること
書き換えはnodeの数を増やすのでそれを抑えることにもなる
そのためには
$C$
の各クリティカルパスは
${\Delta }^{\min }$
から最低一つのconeの終端ノードを含む
ので
${\Delta }^{\min }$
のconeを書き換えたあと全体の
mult-depth
が

必ず減少することが保証される

.

この問題は組合せ最適化の分野で DVD問題(
Dag vertex deletion problem
)
19
として知られている.

cone 選択ヒューリスティックは
まず
CONEREC
を使ってすべての削減可能な cone の集合
$\Delta$
をみつける

グラフ
$C^{\mathrm{AND}}$
(
critical
な ANDを含む) を作る

その間に深さ2の
critical path
が存在する場合2つのANDノードがCANDで接続されています

もし, ANDノードが削減可能な
critical path
なら

ネットワークから着想を得た
$C^{\mathrm{AND}}$
のすべてのノード
$v$
はトポロジカル順に訪れる.
ノードとエッジのフローを頂点ごとに計算する
ノードのフロー
$f^{+}(v)$
: 入力辺のフローの合計 or 1
出力エッジのフロー

$$g^{+}(v,u),u\in \mathrm{succ}(v)$$

, 入力のフローが等分される

todo : あとで理解し実装する