Affine extractors and AC0-Parity
Affine extractors and AC0-Parity
复制标题
仿射提取器和 AC0 奇偶校验
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Emanuele Viola
中科院分区：
文献类型：
--
作者：
Xuangui Huang;P. Ivanov;Emanuele Viola
我们研究了一个简单而通用的模板，用于构造仿射提取器，通过组成一个线性变换与弹性函数。使用这一点，我们表明，良好的仿射提取器可以计算的各种类型的非显式电路，包括AC 0-XOR电路：AC 0电路的奇偶校验门层的输入。我们还表明，单边提取器可以计算小DNF-XOR电路，并将这些电路从其他研究良好的类。作为研究DNF-XOR电路的进一步动机，我们表明，如果它们可以近似内积，那么小的AC 0-XOR电路可以精确地计算它-这是一个长期存在的开放问题。
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 extractors 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.
影响因子：
4.9
作者：
Chattopadhyay, Eshan;Zuckerman, David
通讯作者：
Zuckerman, David
几乎对数熵的仿射提取器
DOI：
10.1109/focs52979.2021.00067
发表时间：
2022
期刊：
IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS
影响因子：
--
作者：
Chattopadhyay, E;Goodman, J;Liao, J
通讯作者：
Liao, J