An Elementary Proof of a 3n - o(n) Lower Bound on the Circuit Complexity of Affine Dispersers
An Elementary Proof of a 3n - o(n) Lower Bound on the Circuit Complexity of Affine Dispersers
复制标题
仿射分散器电路复杂度的 3n - o(n) 下界的基本证明
DOI：
10.1007/978-3-642-22993-0_25
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
A. Kulikov
中科院分区：
文献类型：
--
作者：
Evgeny Demenkov;A. Kulikov
布尔函数f：称F2 n → F2为d维仿射扩散子，如果f在F2 n的任意d维仿射子空间上都不是常数。最近Ben-Sasson和Kopparty给出了次线性d的仿射扩散子的显式构造。研究这些函数的主要动机来自于从结构化的不完美随机性来源中提取随机性。在本文中，我们展示了另一个应用：我们给出了一个非常简单的证明的3 n-o（n）下界的电路复杂性（在全二进制基）的仿射扩散的次线性维数。同样的下界3 n-o（n）（但对于一个完全不同的函数）是由Blum在1984年给出的，至今仍是最著名的。
主要技术是用线性函数代替变量。这样，函数被限制到F2 n的仿射子空间。次线性维数的仿射扩散器则保证在函数退化之前可以进行n-o（n）这样的替换。它仍然表明，每一个这样的替代消除至少3门电路。
A Boolean function f: F2n → F2 is called an affine disperser of dimension d, if f is not constant on any affine subspace of F2n of dimension at least d. Recently Ben-Sasson and Kopparty gave an explicit construction of an affine disperser for sublinear d. The main motivation for studying such functions comes from extracting randomness from structured sources of imperfect randomness. In this paper, we show another application: we give a very simple proof of a 3n-o(n) lower bound on the circuit complexity (over the full binary basis) of affine dispersers for sublinear dimension. The same lower bound 3n-o(n) (but for a completely different function) was given by Blum in 1984 and is still the best known.
The main technique is to substitute variables by linear functions. This way the function is restricted to an affine subspace of F2n. An affine disperser for sublinear dimension then guarantees that one can make n - o(n) such substitutions before the function degenerates. It remains to show that each such substitution eliminates at least 3 gates from a circuit.
电路复杂度良好的混合函数 5n -o(n)
DOI：
--
发表时间：
2007
期刊：
影响因子：
--
作者：
天野一幸;垂井淳;トンプラチュム・アクサラ;垂井 淳
通讯作者：
垂井 淳