Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR21-137 | 21st November 2021 12:22

Affine extractors and AC0-Parity

RSS-Feed




Revision #1
Authors: Xuangui Huang, Peter Ivanov, Emanuele Viola
Accepted on: 21st November 2021 12:22
Downloads: 0
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.



Changes to previous version:

Minor editing


Paper:

TR21-137 | 14th September 2021 19:42

Affine extractors and AC0-Parity





TR21-137
Authors: Xuangui Huang, Peter Ivanov, Emanuele Viola
Publication: 14th September 2021 19:42
Downloads: 269
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