Abstract
A Boolean function \(f \colon \mathbb{F}^n_2 \rightarrow \mathbb{F}_2\) is called an affine disperser of dimension d, if f is not constant on any affine subspace of \(\mathbb{F}^n_2\) 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 \(\mathbb{F}^n_2\). 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.
Research is partially supported by Federal Target Program “Scientific and scientific-pedagogical personnel of the innovative Russia” 2009–2013, Russian Foundation for Basic Research, RAS Program for Fundamental Research, Grant of the President of Russian Federation (NSh-5282.2010.1), and PDMI Computer Science Club scholarship.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Shannon, C.E.: The synthesis of two-terminal switching circuits. Bell System Technical Journal 28, 59–98 (1949)
Blum, N.: A Boolean function requiring 3n network size. Theoretical Computer Science 28, 337–345 (1984)
Iwama, K., Lachish, O., Morizumi, H., Raz, R.: An explicit lower bound of 5n − o(n) for boolean circuits (2005) (unpublished manuscript), http://www.wisdom.weizmann.ac.il/~ranraz/publications/Podedl.ps
Ben-Sasson, E., Kopparty, S.: Affine dispersers from subspace polynomials. In: Proceedings of the Annual Symposium on Theory of Computing (STOC), vol. 679, pp. 65–74. ACM Press, New York (2009)
Boyar, J., Peralta, R.: Tight bounds for the multiplicative complexity of symmetric functions. Theoretical Computer Science 396, 223–246 (2008)
Boyar, J., Peralta, R., Pochuev, D.: On The Multiplicative Complexity of Boolean Functions over the Basis \((\land,\oplus,1)\). Theoretical Computer Science 235(1), 1–16 (2000)
Schnorr, C.P.: Zwei lineare untere Schranken für die Komplexität Boolescher Funktionen. Computing 13, 155–171 (1974)
Paul, W.J.: A 2.5n-lower bound on the combinational complexity of Boolean functions. SIAM Journal of Computing 6(3), 427–433 (1977)
Stockmeyer, L.J.: On the combinational complexity of certain symmetric Boolean functions. Mathematical Systems Theory 10, 323–336 (1977)
Kojevnikov, A., Kulikov, A.S.: Circuit Complexity and Multiplicative Complexity of Boolean Functions. In: Ferreira, F., Löwe, B., Mayordomo, E., Mendes Gomes, L. (eds.) CiE 2010. LNCS, vol. 6158, pp. 239–245. Springer, Heidelberg (2010)
Zwick, U.: A 4n lower bound on the combinational complexity of certain symmetric boolean functions over the basis of unate dyadic Boolean functions. SIAM Journal on Computing 20, 499–505 (1991)
Savicky, P., Zak, S.: A large lower bound for 1-branching programs. Technical Report TR96-036, ECCC (1996)
Amano, K., Tarui, J.: A well-mixed function with circuit complexity 5n ±o(n): Tightness of the lachish-raz-type bounds. In: Agrawal, M., Du, D.-Z., Duan, Z., Li, A. (eds.) TAMC 2008. LNCS, vol. 4978, pp. 342–350. Springer, Heidelberg (2008)
Demenkov, E., Kojevnikov, A., Kulikov, A.S., Yaroslavtsev, G.: New upper bounds on the Boolean circuit complexity of symmetric functions. Information Processing Letters 110(7), 264–267 (2010)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag GmbH Berlin Heidelberg
About this paper
Cite this paper
Demenkov, E., Kulikov, A.S. (2011). An Elementary Proof of a 3n − o(n) Lower Bound on the Circuit Complexity of Affine Dispersers. In: Murlak, F., Sankowski, P. (eds) Mathematical Foundations of Computer Science 2011. MFCS 2011. Lecture Notes in Computer Science, vol 6907. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-22993-0_25
Download citation
DOI: https://doi.org/10.1007/978-3-642-22993-0_25
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-22992-3
Online ISBN: 978-3-642-22993-0
eBook Packages: Computer ScienceComputer Science (R0)