An Elementary Proof of a 3n − o(n) Lower Bound on the Circuit Complexity of Affine Dispersers
作者： Evgeny Demenkov , Alexander S. Kulikov
DOI: 10.1007/978-3-642-22993-0_25
关键词:
摘要: A Boolean function f: F2n → F2 is called an affine disperser of dimension d, if f not constant on any subspace at least d. Recently Ben-Sasson and Kopparty gave explicit construction for sublinear The main motivation studying such functions comes from extracting randomness structured sources imperfect randomness. In this paper, we show another application: give a very simple proof 3n-o(n) lower bound the circuit complexity (over full binary basis) dispersers dimension. same (but completely different function) was given by Blum in 1984 still best known. The technique to substitute variables linear functions. This way restricted F2n. An then guarantees that one can make n - o(n) substitutions before degenerates. It remains each substitution eliminates 3 gates circuit.
springer.com
spbu.ru
springerlink.com参考文章(16)
Petr Savický, Stanislav Zák, A large lower bound for 1-branching programs Electronic Colloquium on Computational Complexity. ,vol. 3, ,(1996)
Arist Kojevnikov, Alexander S. Kulikov, Circuit complexity and multiplicative complexity of Boolean functions conference on computability in europe. ,vol. 6158, pp. 239- 245 ,(2010) , 10.1007/978-3-642-13962-8_27
Kazuo Iwama, Hiroki Morizumi, An Explicit Lower Bound of 5n - o(n) for Boolean Circuits mathematical foundations of computer science. pp. 353- 364 ,(2002) , 10.1007/3-540-45687-2_29
Kazuyuki Amano, Jun Tarui, A well-mixed function with circuit complexity 5n: Tightness of the Lachish–Raz-type bounds Theoretical Computer Science. ,vol. 412, pp. 1646- 1651 ,(2011) , 10.1016/J.TCS.2010.12.040
Larry J. Stockmeyer, On the combinational complexity of certain symmetric Boolean functions Theory of Computing Systems \/ Mathematical Systems Theory. ,vol. 10, pp. 323- 336 ,(1976) , 10.1007/BF01683282
Joan Boyar, René Peralta, Tight bounds for the multiplicative complexity of symmetric functions Theoretical Computer Science. ,vol. 396, pp. 223- 246 ,(2008) , 10.1016/J.TCS.2008.01.030
E. Demenkov, A. Kojevnikov, A. Kulikov, G. Yaroslavtsev, New upper bounds on the Boolean circuit complexity of symmetric functions Information Processing Letters. ,vol. 110, pp. 264- 267 ,(2010) , 10.1016/J.IPL.2010.01.007
Norbert Blum, A Boolean function requiring 3n network size Theoretical Computer Science. ,vol. 28, pp. 337- 345 ,(1983) , 10.1016/0304-3975(83)90029-4
Wolfgang J. Paul, A $2.5n$-Lower Bound on the Combinational Complexity of Boolean Functions SIAM Journal on Computing. ,vol. 6, pp. 427- 443 ,(1977) , 10.1137/0206030
Eli Ben-Sasson, Swastik Kopparty, Affine dispersers from subspace polynomials Proceedings of the 41st annual ACM symposium on Symposium on theory of computing - STOC '09. pp. 65- 74 ,(2009) , 10.1145/1536414.1536426