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), it seems that there is this inequality which 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?