Can someone explain the "three-for-two" trick used by the DGHV scheme authors to squash the decryption circuit?
As far as I understand, the "three-for-two" tricks rely on the fact that one does not need to immediately propagate the carries along the whole adder circuit. You may have heard of the "carry-save-adder" method which consists in postponing the carry propagation to reduce circuit latency. For instance, when adding $a=0, b=1$ and $c=1$ (1 bit-integers), one will split the result into two new integers x and y : carry and output. Thus, one can compute $a+b+c$ as $(x &lt;&lt; 1)+y = 2 \times x+y$. In this case, $x = 1$ and $y = 0$. While this example is given with 1-bit integers, we can extend the method to n-bit integers. 

Given $a=(1001)_2$, $b=(0101)_2$ and $c=(1010)_2$ (where $(.)_2$ stands for binary notation), one can find that $x=(1001)_2$ and $y=(0110)_2$. Computing both $x,y$ requires $\mathcal{O}(1)$ circuit depth as it does not depend on $(a,b,c)$ bit-length. However, notice that computing $(x \times 2+y)=(10010)_2+(00110)_2=(11000)_2$ will require $n$ depth circuits if based on a basic "carry-ripple adder" (where $n$ is the bit length of given integers). Note there exists logarithmic adder. 

About the $d&lt;2^{\lceil\log_{3/2}(k)\rceil+2}$ property, it is related to the fact that one can apply the "three-for-two" trick as many times as necessary. For instance, given integers $(a_0, a_1, a_2, a_3)$, one will apply the trick to the first triple $(a_0,a_1,a_2)$ to obtain $(b_0, b_1)$. Thus it remains to compute the sum $(b_0, b_1, a_3)$ (first step). Using the trick one last time, one will obtain $(b_2, b_3)$. 

Every single time one sees a "triplet", one can transform it into a couple. At every step, one can reduce the total amount of elements from $k$ to $k \times \frac{2}{3}$. Since then, it requires at most $\lceil \log_{3/2}(K) \rceil+2$ steps to reduce a list of $K$ integers to 2 integers. To illustrate this point, if $K=9$ and if one applies the trick once, one will obtain a 6-item list. If one apply it one more time, one obtains a 4-item list. It requires a last "trick" to obtain 2 elements that one can finally sum up using a regular adder. 

Let $x_i$ be the i-th bit of $x = x_0+x_1 \times 2 + x_2 \times 2^2 +... x_{n-1} \times 2^{n-1}$. The $x_i$ computing part of the "three-for-two" circuit requires at least one multiplication (at least one AND gate / Multiplication gate). As the "trick" is chained, multiplications involved in $x_i$ will stack, doubling (that explains the power of two in the  $d&lt;2^{\lceil\log_{3/2}(k)\rceil+2}$ inequality) the "noise" of the homomorphic encrypted text for every layer of the "chain". That is why the multiplicative depth is at most $d&lt;2^{\lceil\log_{3/2}(k)\rceil+2}$.