Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR21-137 | 14th September 2021 19:42

Affine extractors and AC0-Parity

RSS-Feed




TR21-137
Authors: Xuangui Huang, Peter Ivanov, Emanuele Viola
Publication: 14th September 2021 19:42
Downloads: 228
Keywords: 


Abstract:

We study a simple and general template for constructing affine extractors by composing a linear transformation with resilient functions. Using this we show that good affine extractors can be computed by non-explicit circuits of various types, including AC0-Xor circuits: AC0 circuits with a layer of parity gates at the input. We also show that one-sided extractor can be computed by small DNF-Xor circuits, and separate these circuits from other well-studied classes. As a further motivation for studying DNF-Xor circuits we show that if they can approximate inner product then small AC0-Xor circuits can compute it exactly – a long-standing open problem.



ISSN 1433-8092 | Imprint