I was going through this recent paper, and I had a couple of doubts in the final analysis of complexity of the scheme (you don’t need to go through the whole paper). I included three questions here, as I thought they seem to simple questions.

- In Pg 17 (last four lines, see after equation 7), there is this inequality that is used (here, $ k(n) = \sqrt{\frac{n\delta(n)}{\log n}}$ and $ \delta(n) = o(n / \log n)$ ):

$ \frac{\binom{n}{a}}{\binom{^n/_k}{^a/_k}^k} \leq (^n/_k)^k$

Can I know a proof for it?

- Similarly, in the beginning of Pg 18, how is this possible? (the above inequality is used to get here though, $ (n / k)^{k / 2}$ thing, and don’t worry about the meaning of $ \mathtt{ss}$ )

$ \mathtt{ss} \leq \sqrt{\binom{n}{\frac{n}{2}-\delta(n)}}\cdot (n / k)^{k / 2} \cdot \binom{k}{2\delta(n)} \cdot 2^{(2\delta(n)+1)n / k} \leq 2^{n / 2 + o(n)}$

- Also, this one might be a bit trivial, in Pg 17, one inequality above equation 7, the $ O(n)$ term is dropped, isn’t that relevant?