Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > MOHAMMAD MAHDI KHODABANDEH:
All reports by Author Mohammad Mahdi Khodabandeh:

TR26-066 | 1st May 2026
Mohammad Mahdi Khodabandeh, Igor Shinkar

On Sampling Lower Bounds for Polynomials

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$-tuple $\mathcal{P} = (P_1,\dots, P_n)$ of functions $P_i \colon \mathbb{F}_2^m \to \mathbb{F}_2$ defines a distribution over $\{0,1\}^n$ in the natural way: ... more >>>




ISSN 1433-8092 | Imprint