We consider the problem of estimating discrete distributions over $k$ elements under $eps$-local differential privacy from $n$ samples. The samples are distributed across multiple users who send privatized versions of their samples to the server. All the previously known sample optimal algorithms for this problem require a communication complexity that is linear in $k$ in the high privacy regime $(eps<1)$, and have a running time that grows as $ncdot k$, which can be prohibitive for large domain sizes. 

We study the problem under all the four resources, privacy, sample complexity, computational complexity, and communication complexity. We propose emph{Hadamard Response (HR)}, a local privatization mechanism that has the optimal sample complexity (for all values of privacy parameter $eps$), a communication complexity of $log k+2$ bits, and runs in time $tilde{O}(n)$. 

Our encoding and decoding mechanisms are based on Hadamard matrices, and are simple to implement. The gain in sample complexity comes from the large Hamming distance between rows of Hadamard matrices, and the gain in time complexity arises from Fast Hadamard Transformation. 
We compare our approach with Randomized Response (RR), RAPPOR, and subset-selection mechanisms (SS), theoretically, and experimentally.