Polylogarithmic Independence Can Fool DNF Formulas
作者： Vladimir Braverman , Rafail Ostrovsky
DOI: 10.1109/FOCS.2007.55
关键词:
摘要: We show that any k-wise independent probability measure on {0, 1}n can O(m2ldr2ldr2-radick/10)-fool boolean function computable by an rn-clauses DNF (or CNF) formula n variables. Thus, for each constant c > 0. there is a e 0 such m-clauses be in m-e-fooled clog in-wise measure. This resolves, asymptotically and up to logm factor, the depth-2 circuits case of conjecture due Linial Nisan (1990). The result equivalent new characterization formulas low degree polynomials. It implies similar statement measures with small bias property. Using known explicit constructions spaces having limited independence property or property, we. directly obtain large class PRG's ofO(log2 m log n)-seed length variables, improving previously seed lengths.
ieeecomputersociety.org
computer.org参考文章(41)
Luca Trevisan, A Note on Deterministic Approximate Counting for k-DNF Electronic Colloquium on Computational Complexity. ,(2002)
ROBERT J. LECHNER, HARMONIC ANALYSIS OF SWITCHING FUNCTIONS Recent Developments in Switching Theory. pp. 121- 228 ,(1971) , 10.1016/B978-0-12-509850-2.50010-5
Alexander A. Razborov, A simple proof of Bazzi's theorem. Electronic Colloquium on Computational Complexity. ,vol. 15, ,(2008)
Dan Gusfield, Algorithms on Strings, Trees, and Sequences: Suffix Trees and Their Uses ,(1997) , 10.1017/CBO9780511574931
R. Beigel, N. Reingold, D. Spielman, The perceptron strikes back structure in complexity theory annual conference. pp. 286- 291 ,(1991) , 10.1109/SCT.1991.160270
Erdong Chen, Hao Yuan, Linji Yang, Longest Increasing Subsequences in Windows Based on Canonical Antichain Partition Algorithms and Computation. pp. 1153- 1162 ,(2005) , 10.1007/11602613_114
David Liben-Nowell, Erik Vee, An Zhu, None, Finding longest increasing and common subsequences in streaming data computing and combinatorics conference. pp. 263- 272 ,(2005) , 10.1007/11533719_28
Timothy M. Chan, Bashir S. Sadjad, Geometric optimization problems over sliding windows international symposium on algorithms and computation. pp. 246- 258 ,(2004) , 10.1007/978-3-540-30551-4_23
Yun Chi, Haixun Wang, P.S. Yu, R.R. Muntz, Moment: maintaining closed frequent itemsets over a stream sliding window international conference on data mining. pp. 59- 66 ,(2004) , 10.1109/ICDM.2004.10084
Richard P. Stanley, Enumerative Combinatorics: Volume 1 ,(1997)