Small Pseudo-Random Sets Yield Hard Functions: New Tight Explict Lower Bounds for Branching Programs
Small Pseudo-Random Sets Yield Hard Functions: New Tight Explict Lower Bounds for Branching Programs
复制标题
小伪随机集产生硬函数：分支程序的新严格显式下界
DOI：
--
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
J. Rolim
中科院分区：
文献类型：
--
作者：
A. E. Andreev;Juri L. Baskakov;A. Clementi;J. Rolim
在以前的几部作品中，相对于某种类别的算法或布尔电路的构造已被用来得出小型伪随机空间。伪随机的构建（两侧和单面）集，用于布尔仿期空间，以及具有硬支支化程序复杂性的布尔功能的明确构造。
如果是1次阅读的分支程序（1-Br.pr。），我们表明，非琐碎的（即基数2O（n））差异集（即双面伪随机集）的boolean仿率差异（即双面伪随机集）尺寸大于N/2的空间通过结合了最著名的bibles blip.pr的显式布尔。得出所需的差异集，并在1-BR.PR的p中获得一个布尔函数，并在dtime（2o（log2 n））中具有1- br.pr的尺寸。尺寸不小于2N-O（log n）。读取分支程序（k-br.pr。），我们引入了一种新方法，以推导明显的指数下限，涉及构建击球集（单方面伪随机集），以构建尺寸O的仿射空间（N/2） ）使用适当的“正交”表示，我们有效地构造了这些命中术，从而在P BR.PR的P中获得了显式的布尔函数。 o（log n/log log n。这比[8,11，17]中给出的以前最著名的下限有所改善。
In several previous works the construction of a computationally hard function with respect to a certain class of algorithms or Boolean circuits has been used to derive small pseudo-random spaces. In this paper, we revert this connection by presenting two new direct relations between the efficient construction of pseudo-random (both two-sided and one-sided) sets for Boolean affine spaces and the explicit construction of Boolean functions having hard branching program complexity.
In the case of 1-read branching programs (1-Br.Pr.), we show that the construction of non trivial (i.e. of cardinality 2o(n)) discrepancy sets (i.e. two-sided pseudo-random sets) for Boolean affine spaces of dimension greater than n/2 yield a set of explicit Boolean functions having very hard 1-Br.Pr. size. By combining the best known construction of Ɛ-biased sample spaces for linear tests and a simple "Reduction" Lemma, we derive the required discrepancy set and obtain a Boolean function in P having 1-Br.Pr. size not smaller than 2n-O(log2 n) and a Boolean function in DTIME(2O(log2 n)) having 1-Br.Pr. size not smaller than 2n-O(log n). The latter bound is optimal and both of them are exponential improvements over the best previously known lower bound that was 2n-3n1=2 [21]. As for non deterministic syntactic k-read branching programs (k-Br.Pr.), we introduce a new method to derive explicit, exponential lower bounds that involves the construction of hitting sets (one-sided pseudo-random sets) for affine spaces of dimension o(n/2). Using an appropriate "orthogonal" representation of small Boolean affine spaces, we efficiently construct these hitting sets thus obtaining an explicit Boolean function in P that has k-Br.Pr. size not smaller than 2n1-o(1) for any k = o(log n/log log n. This improves over the previous best known lower bounds given in [8,11, 17] for some range of k.