{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,3]],"date-time":"2025-05-03T10:10:03Z","timestamp":1746267003292,"version":"3.40.4"},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662439470"},{"type":"electronic","value":"9783662439487"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-43948-7_20","type":"book-chapter","created":{"date-parts":[[2014,6,11]],"date-time":"2014-06-11T16:10:36Z","timestamp":1402503036000},"page":"235-246","source":"Crossref","is-referenced-by-count":1,"title":["On DNF Approximators for Monotone Boolean Functions"],"prefix":"10.1007","author":[{"given":"Eric","family":"Blais","sequence":"first","affiliation":[]},{"given":"Johan","family":"H\u00e5stad","sequence":"additional","affiliation":[]},{"given":"Rocco A.","family":"Servedio","sequence":"additional","affiliation":[]},{"given":"Li-Yang","family":"Tan","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"20_CR1","first-page":"64","volume":"10","author":"W.V.O. Quine","year":"1954","unstructured":"Quine, W.V.O.: Two theorems about truth functions. Bol. Soc. Math. Mexicana\u00a010, 64\u201370 (1954)","journal-title":"Bol. Soc. Math. Mexicana"},{"key":"20_CR2","first-page":"354","volume":"31","author":"A.A. Razborov","year":"1985","unstructured":"Razborov, A.A.: Lower bounds for the monotone complexity of some boolean functions. Soviet Mathematics Doklady\u00a031, 354\u2013357 (1985)","journal-title":"Soviet Mathematics Doklady"},{"key":"20_CR3","unstructured":"Okol\u2019nishnikova, E.: On the influence of negations on the complexity of a realization of monotone Boolean functions by formulas of bounded depth. Metody Diskret. Analiz.\u00a038, 74\u201380 (1982) (in Russian)"},{"issue":"4","key":"20_CR4","doi-asserted-by":"publisher","first-page":"1004","DOI":"10.1145\/31846.31852","volume":"34","author":"M. Ajtai","year":"1987","unstructured":"Ajtai, M., Grevich, Y.: Monotone versus positive. Journal of the ACM\u00a034(4), 1004\u20131015 (1987)","journal-title":"Journal of the ACM"},{"issue":"5","key":"20_CR5","doi-asserted-by":"publisher","first-page":"929","DOI":"10.1070\/RM2003v058n05ABEH000667","volume":"58","author":"A.D. Korshunov","year":"2003","unstructured":"Korshunov, A.D.: Monotone Boolean functions. Russian Math. Surveys (Uspekhi Mat. Nauk)\u00a058(5), 929\u20131001 (2003)","journal-title":"Russian Math. Surveys (Uspekhi Mat. Nauk)"},{"key":"20_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF02579196","volume":"7","author":"N. Alon","year":"1987","unstructured":"Alon, N., Boppana, R.: The monotone circuit complexity of Boolean functions. Combinatorica\u00a07, 1\u201322 (1987)","journal-title":"Combinatorica"},{"key":"20_CR7","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1145\/62212.62265","volume-title":"STOC 1988: Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing","author":"M. Karchmer","year":"1988","unstructured":"Karchmer, M., Wigderson, A.: Monotone circuits for connectivity require super-logarithmic depth. In: STOC 1988: Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, pp. 539\u2013550. ACM, New York (1988)"},{"issue":"1","key":"20_CR8","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/BF02122563","volume":"8","author":"\u00c9. Tardos","year":"1988","unstructured":"Tardos, \u00c9.: The gap between monotone and non-monotone circuit complexity is exponential. Combinatorica\u00a08(1), 141\u2013142 (1988)","journal-title":"Combinatorica"},{"key":"20_CR9","doi-asserted-by":"crossref","unstructured":"Raz, R., Wigderson, A.: Monotone circuits for matching require linear depth. In: Proceedings of the 22nd ACM Symposium on Theory of Computing, pp. 287\u2013292 (1990)","DOI":"10.1145\/100216.100253"},{"key":"20_CR10","doi-asserted-by":"crossref","unstructured":"Karchmer, M., Raz, R., Wigderson, A.: Super-logarithmic depth lower bounds via direct sum in communication coplexity. In: Structure in Complexity Theory Conference, pp. 299\u2013304 (1991)","DOI":"10.1109\/SCT.1991.160273"},{"issue":"3","key":"20_CR11","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1006\/jcss.1995.1033","volume":"50","author":"M. Grigni","year":"1995","unstructured":"Grigni, M., Sipser, M.: Monotone separation of logarithmic space from logarithmic depth. J. Comput. Syst. Sci.\u00a050(3), 433\u2013437 (1995)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"20_CR12","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1006\/jcss.1997.1494","volume":"55","author":"A. Razborov","year":"1997","unstructured":"Razborov, A., Rudich, S.: Natural proofs. Journal of Computer and System Sciences\u00a055(1), 24\u201335 (1997)","journal-title":"Journal of Computer and System Sciences"},{"issue":"5","key":"20_CR13","doi-asserted-by":"publisher","first-page":"1283","DOI":"10.1137\/S0097539795285631","volume":"27","author":"M. Goldmann","year":"1998","unstructured":"Goldmann, M., H\u00e5stad, J.: Monotone circuits for connectivity have depth (log n)2\u2009\u2212\u2009o(1). SIAM J. Comput.\u00a027(5), 1283\u20131294 (1998)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"20_CR14","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1007\/s004930050062","volume":"19","author":"R. Raz","year":"1999","unstructured":"Raz, R., McKenzie, P.: Separation of the monotone NC hierarchy. Combinatorica\u00a019(3), 403\u2013435 (1999)","journal-title":"Combinatorica"},{"key":"20_CR15","doi-asserted-by":"crossref","unstructured":"Potechin, A.: Bounds on monotone switching networks for directed connectivity. In: Symposium on Foundations of Computer Science (FOCS), pp. 553\u2013562 (2010)","DOI":"10.1109\/FOCS.2010.58"},{"key":"20_CR16","doi-asserted-by":"crossref","unstructured":"Chan, S.M., Potechin, A.: Tight bounds for monotone switching networks via fourier analysis. In: Symposium on Theory of Computing (STOC), pp. 495\u2013504 (2012)","DOI":"10.1145\/2213977.2214024"},{"key":"20_CR17","doi-asserted-by":"crossref","unstructured":"Filmus, Y., Pitassi, T., Robere, R., Cook, S.A.: Average case lower bounds for monotone switching networks. In: Symposium on Foundations of Computer Science (FOCS) (2013)","DOI":"10.1109\/FOCS.2013.70"},{"key":"20_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/978-3-540-73420-8_19","volume-title":"Automata, Languages and Programming","author":"R.T. O\u2019Donnell","year":"2007","unstructured":"O\u2019Donnell, R.T., Wimmer, K.: Approximation by DNF: examples and counterexamples. In: Arge, L., Cachin, C., Jurdzi\u0144ski, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol.\u00a04596, pp. 195\u2013206. Springer, Heidelberg (2007)"},{"key":"20_CR19","doi-asserted-by":"crossref","unstructured":"Blais, E., Tan, L.Y.: Approximating Boolean functions with depth-2 circuits. In: Proceedings of the 28th Annual IEEE Conference on Computational Complexity, pp. 74\u201385 (2013)","DOI":"10.1109\/CCC.2013.17"},{"issue":"4","key":"20_CR20","doi-asserted-by":"publisher","first-page":"747","DOI":"10.1145\/234533.234564","volume":"43","author":"N. Bshouty","year":"1996","unstructured":"Bshouty, N., Tamon, C.: On the Fourier spectrum of monotone functions. Journal of the ACM\u00a043(4), 747\u2013770 (1996)","journal-title":"Journal of the ACM"},{"issue":"3","key":"20_CR21","doi-asserted-by":"publisher","first-page":"414","DOI":"10.1006\/jcss.1997.1533","volume":"55","author":"J. Jackson","year":"1997","unstructured":"Jackson, J.: An efficient membership-query algorithm for learning DNF with respect to the uniform distribution. Journal of Computer and System Sciences\u00a055(3), 414\u2013440 (1997)","journal-title":"Journal of Computer and System Sciences"},{"issue":"1\u20132","key":"20_CR22","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1016\/S0304-3975(96)00019-9","volume":"174","author":"M. Krause","year":"1997","unstructured":"Krause, M., Pudl\u00e1k, P.: On the computational power of depth-2 circuits with threshold and modulo gates. Theoretical Computer Science\u00a0174(1\u20132), 137\u2013156 (1997)","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"20_CR23","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1007\/PL00009809","volume":"18","author":"E. Friedgut","year":"1998","unstructured":"Friedgut, E.: Boolean functions with low average sensitivity depend on few coordinates. Combinatorica\u00a018(1), 27\u201336 (1998)","journal-title":"Combinatorica"},{"issue":"1","key":"20_CR24","doi-asserted-by":"publisher","first-page":"45","DOI":"10.4086\/toc.2011.v007a004","volume":"7","author":"K. Amano","year":"2011","unstructured":"Amano, K.: Tight bounds on the average sensitivity of k-CNF. Theory of Computing\u00a07(1), 45\u201348 (2011)","journal-title":"Theory of Computing"},{"issue":"2","key":"20_CR25","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/s00037-013-0068-6","volume":"22","author":"P. Gopalan","year":"2013","unstructured":"Gopalan, P., Meka, R., Reingold, O.: Dnf sparsification and a faster deterministic counting algorithm. Computational Complexity\u00a022(2), 275\u2013310 (2013)","journal-title":"Computational Complexity"},{"key":"20_CR26","unstructured":"Kalai, G.: Noise stability and threshold circuits. Gil Kalai\u2019s, Combinatorics and more, blog (2010), http:\/\/gilkalai.wordpress.com\/2010\/02\/10\/noise-stability-and-threshold-circuits\/"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-43948-7_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,3]],"date-time":"2025-05-03T09:31:08Z","timestamp":1746264668000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-43948-7_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662439470","9783662439487"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-43948-7_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}