×

Approximating Boolean functions with depth-2 circuits. (English) Zbl 1330.68100

Summary: We study the complexity of approximating Boolean functions with disjunctive normal forms (DNFs) and other depth-2 circuits, exploring two main directions: universal bounds on the approximability of all Boolean functions, and the approximability of the parity function. In the first direction, our main positive results are the first nontrivial universal upper bounds on approximability by DNFs: (a) every Boolean function can be \(\epsilon\)-approximated by a DNF of size \(O_\epsilon(2^n/\log n)\), and (b) every Boolean function can be \(\epsilon\)-approximated by a DNF of width \(c_\epsilon n\), where \(c_\epsilon < 1\). Our techniques extend broadly to give strong universal upper bounds on approximability by various depth-2 circuits that generalize DNFs, including the intersection of halfspaces, low-degree Polynomial threshold functions, and unate functions. We show that the parameters of our constructions almost match the information-theoretic inapproximability of a random function. In the second direction our main positive result is the construction of an explicit DNF that approximates the following parity function: \(\mathsf{PAR}_n\) can be \(\epsilon\)-approximated by a DNF of size \(2^{(1-2\epsilon)n}\) and width \((1-2\epsilon)n\). Using Fourier analytic tools we show that our construction is essentially optimal not just within the class of DNFs but also within the far more expressive classes of the intersection of halfspaces and intersection of unate functions.

MSC:

68Q25 Analysis of algorithms and problem complexity
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)

Software:

JBool
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] M. Ajtai, {\it \(Σ^1_1\)-formulae on finite structures}, Annal. Pure Appl. Logic, 24 (1983), pp. 1-48. · Zbl 0519.03021
[2] K. Amano, {\it Tight bounds on the average sensitivity of \(k\)-CNF}, Theory Comput., 7 (2011), pp. 45-48. · Zbl 1213.68416
[3] A. Bernasconi, B. Codenotti, and J. Simon, {\it On the Fourier Analysis of Boolean Functions}, Technical report. Istituto di Matematica Computazionale, 1997.
[4] P. Beame, R. Impagliazzo, and S. Srinivasan, {\it Approximating \(\mathsf{AC}^0\) by small height decision trees and a deterministic algorithm for} #\( \mathsf{AC}^0\mathsf{SAT} \), in Proceedings of the IEEE Conference on Computational Complexity, 2012, pp. 117-125.
[5] R. Boppana, {\it The average sensitivity of bounded-depth circuits}, Inform. Process. Lett., 63 (1997), pp. 257-261. · Zbl 1337.68124
[6] E. Blais, L.-Y. Tan, and A. Wan, {\it An inequality for the Fourier spectrum of parity decision trees}, arXiv:1506.01055 [cs.DM], 2015.
[7] J.-Y. Cai, {\it With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy}, J. Comput. System Sci., 38 (1989), pp. 68-85. · Zbl 0668.68052
[8] Y. Crama and P. L. Hammer, {\it Boolean Functions: Theory, Algorithms, and Applications}, Encyclopedia Math. Appl. 142, Cambridge University Press, New York, 2011. · Zbl 1237.06001
[9] G. Cohen, I. Honkala, S. Litsyn, and A. Lobstein, {\it Covering Codes}, North-Holland Mathematical Library, Elsevier Science, New York, 2005. · Zbl 0874.94001
[10] C.-K. Chow, {\it On the characterization of threshold functions}, in Proceedings of the 2nd Annual Symposium on Switching Circuit Theory and Logical Design (FOCS), 1961, pp. 34-38.
[11] M. Furst, J. Saxe, and M. Sipser, {\it Parity, circuits, and the polynomial-time hierarchy}, Math. Systems Theory, 17 (1984), pp. 13-27. · Zbl 0534.94008
[12] V. V. Glagolev, {\it Nekotorye otsenki dizyunktivnykh normalnykh form funktsi\v\i algebry logiki}, Problemy Kibernetiki, 19 (1967), pp. 75-95.
[13] J. H\aastad, {\it Almost optimal lower bounds for small depth circuits}, in Proceedings of STOC, 1986, pp. 6-20.
[14] J. H\aastad, {\it On the Correlation of Parity and Small-Depth Circuits}, Technical report TR12-137, Electronic Colloquium on Computational Complexity, 2012. · Zbl 1320.68092
[15] R. Impagliazzo, W. Matthews, and R. Paturi, {\it A satisfiability algorithm for \(\mathsf{AC}^0\)}, In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, 2012, pp. 961-972. · Zbl 1423.68583
[16] D. Kane, {\it The average sensitivity of an intersection of half spaces}, Res. Math. Sci., 1 (2014), pp. 1-8. · Zbl 1349.68150
[17] A. D. Korshunov, {\it Verkhnyaya otsenka slozhnosti kratcha\v\ishikh dnf pochti vsekh bulevykh funktsi\v\i}, {\it Kibernetika}, 6 (1969), pp. 1-8.
[18] A. D. Korshunov, {\it O slozhnosti kratcha\v\ishikh dizyunktivnykh normalnykh form bulevykh funktsi\v\i}, Metody Diskretnogo Anal., 37 (1981), pp. 9-41.
[19] A. D. Korshunov, {\it O slozhnosti kratcha\v\ishikh dizyunktivnykh normalnykh form sluchaǐnykh bulevykh funktsi\v\i}, Metody Diskretnogo Anal., 40 (1983), pp. 25-53.
[20] A. Klivans, R. O’Donnell, and R. Servedio, {\it Learning intersections and thresholds of halfspaces}, J. Comput. System Sci., 68 (2004), pp. 808-840. · Zbl 1074.68026
[21] G. A. Kabatyanski and V. I. Panchenko, {\it Packings and coverings of the Hamming space by unit balls}, Dokl. Akad. Nauk SSSR, 303 (1988), pp. 550-552.
[22] M. Krivelevich, B. Sudakov, and V. H. Vu, {\it Covering codes with improved density}, IEEE Trans. Inform. Theory, 49 (2003), pp. 1812-1815. · Zbl 1247.94070
[23] S. E. Kuznetsov, {\it O nizhne\v\i otsenke dliny kratcha\v\ishe\v\i dnf pochti vsekh bulevykh funktsi\v\i,} Veroyatnoste Metody Kibernetiki, 19 (1983), pp. 44-47.
[24] N. Linial, Y. Mansour, and N. Nisan, {\it Constant depth circuits, Fourier transform and Learnability}, in Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, 1989, pp. 574-579. · Zbl 0781.94006
[25] O. Lupanov, {\it Implementing the algebra of logic functions in terms of constant depth formulas in the basis \(\&, ∨, ¬\)}, Dokl. Akad. Nauk. SSSR, 136 (1961), pp. 1041-1042. · Zbl 0104.24102
[26] R. O’Donnell and K. Wimmer, {\it Approximation by DNF: Examples and counterexamples}, in Proceedings of the 34th Annual International Colloquium on Automata, Languages and Programming, 2007, pp. 195-206. · Zbl 1171.94382
[27] N. Pippenger, {\it The shortest disjunctive normal form of a random boolean function}, Random Structures Algorithms, 22 (2003), pp. 161-186. · Zbl 1023.94023
[28] W. V. O. Quine, {\it Two theorems about truth functions}, Bol. Soc. Mat. Mexicana, 10 (1954), pp. 64-70.
[29] A. A. Sapozhenko, {\it O slozhnosti dizyunktivnykh normalnykh form, poluchaemykh s pomoshchyu gradientnogo algoritma}, Diskretn. Anal., 21 (1972), pp. 62-71.
[30] P. Traxler, {\it Variable influences in conjunctive normal forms}, in Proceedings of SAT, 2009, pp. 101-113. · Zbl 1247.94075
[31] A. Yao, {\it Separating the polynomial time hierarchy by oracles}, in Proceedings of the 26th Annual IEEE Symposium on Foundations of Computer Science, 1985, pp. 1-10.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.