摘要: We give an explicit function h:{0,1}n->{0,1} such that any deMorgan formula of size O(n2.499) agrees with h on at most 1/2 + e fraction the inputs, where is exponentially small (i.e. = 2-nΩ(1)). also show, using same technique, boolean O(n1.999) over complete basis, Our construction based Andreev's Ω(n2.5-o(1)) lower bound was proved for case exact computation.
acm.org
princeton.edu
weizmann.ac.il 
sci-hub.se 参考文章(18)
Stasys Jukna, Boolean Function Complexity: Advances and Frontiers ,(2012)
Rahul Santhanam, Fighting Perebor: New and Improved Algorithms for Formula and QBF Satisfiability 2010 IEEE 51st Annual Symposium on Foundations of Computer Science. pp. 183- 192 ,(2010) , 10.1109/FOCS.2010.25
Russell Impagliazzo, Raghu Meka, David Zuckerman, Pseudorandomness from Shrinkage 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science. pp. 111- 119 ,(2012) , 10.1109/FOCS.2012.78
Devdatt P. Dubhashi, Alessandro Panconesi, Concentration of Measure for the Analysis of Randomized Algorithms ,(2012)
Russell Impagliazzo, Noam Nisan, The effect of random restrictions on formula size Random Structures and Algorithms. ,vol. 4, pp. 121- 133 ,(1993) , 10.1002/RSA.3240040202
Noam Nisan, Avi Wigderson, Hardness vs randomness Journal of Computer and System Sciences. ,vol. 49, pp. 149- 167 ,(1994) , 10.1016/S0022-0000(05)80043-1
Johan HÅ stad, The Shrinkage Exponent of de Morgan Formulas is 2 SIAM Journal on Computing. ,vol. 27, pp. 48- 64 ,(1998) , 10.1137/S0097539794261556
Ben W. Reichardt, Reflections for quantum query algorithms symposium on discrete algorithms. pp. 560- 569 ,(2011) , 10.5555/2133036.2133080
Noam Nisan, Pseudorandom bits for constant depth circuits Combinatorica. ,vol. 11, pp. 63- 70 ,(1991) , 10.1007/BF01375474
Esther Ezra, Micha Sharir, Any AND-OR Formula of Size N can be Evaluated in time N^{1/2 + o(1)} on a Quantum Computer foundations of computer science. pp. 363- 372 ,(2007) , 10.1109/FOCS.2007.10