Given two integers $n$ and $k$, I want to compute the exact value of the binomial coefficient ${n \choose k}$.
Here $n$ and $k$ are given in their binary representation, meaning that the size of the input is about $\log n + \log k$.
How fast, in big-O notation, can we compute ${n \choose k}$?
One can compute this in time $O(k)$ using, say, the multiplicative formula (see here). But in the worst case, this is exponential in the size of the input.
Can ${n \choose k}$ be computed faster?