Appendices Appendices 1 A Basic Facts about Gaussian Distributions 2 B An Improved Analysis of NA-Hutch+ + 3 C Lower Bounds 8 C.1 Case 1: Lower Bound for Small ɛ