Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR15-205 | 15th December 2015 18:17

Quadratic maps are hard to sample

RSS-Feed




TR15-205
Authors: Emanuele Viola
Publication: 15th December 2015 18:18
Downloads: 1470
Keywords: 


Abstract:

This note proves the existence of a quadratic GF(2) map
$p : \{0,1\}^n \to \{0,1\}$ such that no constant-depth circuit
of size $\poly(n)$ can sample the distribution $(u,p(u))$
for uniform $u$.



ISSN 1433-8092 | Imprint