On Sampling Lower Bounds for Polynomials

Mohammad Mahdi Khodabandeh, Igor Shinkar

In this work, we continue the line of research on the complexity of distributions (Viola, Journal of Computing 2012), and study samplers defined by low degree polynomials. An $n$-t…