Before revision:  Under local privacy constraints , we present a sample-optimal private-coin scheme that only sends a one-bit message per user.
After revision:  We characterize the sample complexity for sparse estimation under LDP constraints up to a constant factor and the sample complexity under communication constraints up to a logarithmic factor. Our upper bounds under LDP are based on the Hadamard Response, a private coin scheme that requires only one bit of communication per user.