Title: Filling the Soap Bubbles: Efficient Black-Box Adversarial Certification with Non-Gaussian Smoothing. Abstract: Randomized classifiers have been shown to provide a promising approach for achieving certified robustness against adversarial attacks in deep learning. However, most existing methods only leverage Gaussian smoothing noise and only work for $\ell_2$ perturbation. We propose a general framework of adversarial certification with non-Gaussian noise and for more general types of attacks, from a unified functional optimization perspective. Our new framework allows us to identify a key trade-off between accuracy and robustness via designing smoothing distributions, helping to design two new families of non-Gaussian smoothing distributions that work more efficiently for $\ell_2$ and $\ell_\infty$ attacks, respectively. Our proposed methods achieve better results than previous works and provide a new perspective on randomized smoothing certification.