Can someone explain the "three-for-two" trick used by the DGHV scheme authors to squash the decryption circuit? Can someone please explain the "three-for-two" trick used by the authors of the DGHV scheme (page 17) to squash the decryption circuit? I looked for resources on the same, but it looks like the authors coined this term.

A brief description of the "three-for-two" trick:

It is a technique that uses a constant depth circuit to transform three numbers of arbitrary bit lengths into two numbers that are almost 1 bit longer, such that the sum of the two output numbers is equal to the sum of the three input numbers.

Furthermore, the paper says that the total depth that it takes to reduce $k$ numbers to two numbers is $d \leq 2^{\lceil log_{3/2}k \rceil + 2}$. I don't get how we landed on this expression.
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}$.