如何確定電路的層數？
在多方計算 (MPC) 或全同態加密 (FHE) 等許多加密應用程序中，您會考慮一個函式 $ f $ 由某個代數結構（通常是域）上的電路描述。
現在，算法的複雜性在很大程度上取決於電路的深度，而不一定取決於電路的大小，這是非常典型的。例如，在基於 Lattice 的 FHE 中就是這種情況，其中需要低深度才能執行自舉，或者在某些輪數取決於電路深度的非恆定輪 MPC 協議中。
鑑於上述情況，我有兩個問題。
- 給定一個電路 $ f $ ，我們如何優化以獲得相同的“更淺”電路 $ f $ ? 是否有任何工具/算法可用於此目的？
- 假設電路為 $ f $ 如果作為門列表給出，其中每個門都指向與其輸入對應的一個或多個門。我們如何從這種表示中確定電路的層？是否也有任何工具/算法？
第二點與 MPC 尤其相關，其中同一層中門的通信可以並行化，提供了很大的改進。
謝謝！
給定 f 的電路，我們如何優化以獲得相同 f 的“更淺”電路？是否有任何工具/算法可用於此目的？
研究人員已經確定這是 MPC 和 FHE 的一個相關問題，其中低深度電路會產生很大的性能差異。這個方向的一些作品包括
$$ BDKK+18 $$和$$ BHWK16 $$, 並探勘他們的參考資料將揭示朝這個方向的更多工作。 該領域的一些技術包括從電氣工程領域的電路綜合中調整一些優化工具，還有一些其他的手工優化。
假設 f 的電路作為門列表給出，其中每個門指向與其輸入對應的一個或多個門。我們如何從這種表示中確定電路的層？是否也有任何工具/算法？
我知道實現這一目標的兩種方法。
貪心算法
一個非常直覺的工作如下，在高層次上。獲取輸入節點併計算您可以從這些節點計算的所有加法門，而不會絆倒乘法門。然後計算僅依賴於上面找到的任何門（包括輸入門）的乘法門。這些門的深度為 1。
然後計算依賴於所有先前門的所有加法門，然後計算僅依賴於到目前為止找到的門的乘法門。它們的深度為 2。此迭代一直持續到處理完所有門為止。
使用動態規劃
這種方法被認為是
$$ KSS13 $$. 到每條邊 $ v_{ij} $ 從大門走 $ g_i $ 到門 $ g_j $ , 賦予權重 $ 0 $ 如果 $ g_j $ 是一個加法門，並分配權重 $ -1 $ 如果 $ g_j $ 是一個乘法門。然後，很容易看出門的深度變成了從門到任何輸入節點的最短距離（負數）。這可以通過動態程式算法（如Dijkstra 算法）來計算。