{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,31]],"date-time":"2025-10-31T21:44:11Z","timestamp":1761947051106,"version":"build-2065373602"},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540734192"},{"type":"electronic","value":"9783540734208"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-73420-8_19","type":"book-chapter","created":{"date-parts":[[2007,8,25]],"date-time":"2007-08-25T14:58:43Z","timestamp":1188053923000},"page":"195-206","source":"Crossref","is-referenced-by-count":14,"title":["Approximation by DNF: Examples and Counterexamples"],"prefix":"10.1007","author":[{"given":"Ryan","family":"O\u2019Donnell","sequence":"first","affiliation":[]},{"given":"Karl","family":"Wimmer","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"19_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0168-0072(83)90038-6","volume":"24","author":"M. Ajtai","year":"1983","unstructured":"Ajtai, M.: $\\Sigma^1_1$ -formulae on finite structures. Annals of Pure and Applied Logic\u00a024, 1\u201348 (1983)","journal-title":"Annals of Pure and Applied Logic"},{"key":"19_CR2","doi-asserted-by":"crossref","unstructured":"Ajtai, M.: Approximate counting with uniform constant-depth circuits. In: Advances in Computational Complexity Theory, pp. 1\u201320. Amer. Math. Soc., Providence, RI (1993)","DOI":"10.1090\/dimacs\/013\/01"},{"key":"19_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF02579338","volume":"3","author":"M. Ajtai","year":"1983","unstructured":"Ajtai, M., Koml\u00f3s, J., Szemer\u00e9di, E.: Sorting in c logn parallel steps. Combinatorica\u00a03, 1\u201319 (1983)","journal-title":"Combinatorica"},{"key":"19_CR4","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1007\/BF02698830","volume":"90","author":"I. Benjamini","year":"1999","unstructured":"Benjamini, I., Kalai, G., Schramm, O.: Noise sensitivity of boolean functions and applications to percolation. Inst. Hautes \u00c9tudes Sci. Publ. Math.\u00a090, 5\u201343 (1999)","journal-title":"Inst. Hautes \u00c9tudes Sci. Publ. Math."},{"key":"19_CR5","volume-title":"Randomness and Computation","author":"M. Ben-Or","year":"1990","unstructured":"Ben-Or, M., Linial, N.: Collective coin flipping. In: Micali, S. (ed.) Randomness and Computation, Academic Press, New York (1990)"},{"issue":"2","key":"19_CR6","doi-asserted-by":"publisher","first-page":"222","DOI":"10.1016\/0022-0000(86)90027-9","volume":"32","author":"R. Boppana","year":"1986","unstructured":"Boppana, R.: Threshold functions and bounded depth monotone circuits. J. Comp. Sys. Sci.\u00a032(2), 222\u2013229 (1986)","journal-title":"J. Comp. Sys. Sci."},{"issue":"5","key":"19_CR7","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1016\/S0020-0190(97)00131-2","volume":"63","author":"R. Boppana","year":"1997","unstructured":"Boppana, R.: The average sensitivity of bounded-depth circuits. Inf. Process. Lett.\u00a063(5), 257\u2013261 (1997)","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"19_CR8","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"},{"key":"19_CR9","unstructured":"Dinur, I., Friedgut, E.: Lecture notes (2006), available at http:\/\/www.cs.huji.ac.il\/~analyt\/scribes\/L11.pdf"},{"issue":"1","key":"19_CR10","doi-asserted-by":"publisher","first-page":"474","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), 474\u2013483 (1998)","journal-title":"Combinatorica"},{"issue":"4","key":"19_CR11","doi-asserted-by":"publisher","first-page":"1017","DOI":"10.1090\/S0894-0347-99-00305-7","volume":"12","author":"E. Friedgut","year":"1999","unstructured":"Friedgut, E.: Sharp thresholds of graph properties, and the k-SAT problem. J. American Math. Soc.\u00a012(4), 1017\u20131054 (1999)","journal-title":"J. American Math. Soc."},{"issue":"1-2","key":"19_CR12","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1002\/rsa.20042","volume":"26","author":"E. Friedgut","year":"2005","unstructured":"Friedgut, E.: Hunting for sharp thresholds. Random Struct. & Algorithms\u00a026(1-2), 37\u201351 (2005)","journal-title":"Random Struct. & Algorithms"},{"key":"19_CR13","volume-title":"Computational Limitations for Small Depth Circuits","author":"J. H\u00e5stad","year":"1986","unstructured":"H\u00e5stad, J.: Computational Limitations for Small Depth Circuits. MIT Press, Cambridge, MA (1986)"},{"key":"19_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/11830924_38","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"S. Hoory","year":"2006","unstructured":"Hoory, S., Magen, A., Pitassi, T.: Monotone circuits for the majority function. In: D\u00edaz, J., Jansen, K., Rolim, J.D.P., Zwick, U. (eds.) APPROX 2006 and RANDOM 2006. LNCS, vol.\u00a04110, Springer, Heidelberg (2006)"},{"key":"19_CR15","unstructured":"Jackson, J.: The Harmonic sieve: a novel application of Fourier analysis to machine learning theory and practice. PhD thesis, Carnegie Mellon University, (August 1995)"},{"key":"19_CR16","doi-asserted-by":"crossref","unstructured":"Kalai, G.: Combinatorics with a geometric flavor: some examples, 2000. GAFA Special Volume 10, Birkhauser Verlag, Basel (2000)","DOI":"10.1007\/978-3-0346-0425-3_7"},{"key":"19_CR17","doi-asserted-by":"crossref","unstructured":"Kahn, J., Kalai, G., Linial, N.: The influence of variables on boolean functions. In: Proceedings of the 29th Annual Symposium on Foundations of Computer Science, pp. 68\u201380 (1988)","DOI":"10.1109\/SFCS.1988.21923"},{"key":"19_CR18","volume-title":"Computational Complexity and Statistical Physics","author":"G. Kalai","year":"2005","unstructured":"Kalai, G., Safra, S.: Threshold phenomena and influence. In: Computational Complexity and Statistical Physics, Oxford University Press, Oxford (2005)"},{"issue":"3","key":"19_CR19","doi-asserted-by":"publisher","first-page":"607","DOI":"10.1145\/174130.174138","volume":"40","author":"N. Linial","year":"1993","unstructured":"Linial, N., Mansour, Y., Nisan, N.: Constant depth circuits, Fourier transform and learnability. Journal of the ACM\u00a040(3), 607\u2013620 (1993)","journal-title":"Journal of the ACM"},{"key":"19_CR20","first-page":"101","volume":"10","author":"G. Margulis","year":"1974","unstructured":"Margulis, G.: Probabilistic characteristics of graphs with large connectivity. Prob. Peredachi Inform.\u00a010, 101\u2013108 (1974)","journal-title":"Prob. Peredachi Inform."},{"key":"19_CR21","doi-asserted-by":"crossref","unstructured":"O\u2019Donnell, R., Servedio, R.: Learning monotone decision trees in polynomial time. SIAM J. Comp., 2006 (to appear)","DOI":"10.1137\/060669309"},{"key":"19_CR22","doi-asserted-by":"crossref","first-page":"174","DOI":"10.1017\/CBO9780511526633.014","volume":"169","author":"M. Paterson","year":"1992","unstructured":"Paterson, M., Pippenger, N., Zwick, U.: Optimal carry save networks. Boolean function complexity\u00a0169, 174\u2013201 (1992)","journal-title":"Boolean function complexity"},{"key":"19_CR23","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/BF00535274","volume":"43","author":"L. Russo","year":"1978","unstructured":"Russo, L.: On the critical percolation probabilities. Z. Wahrsch. Werw. Gebiete\u00a043, 39\u201348 (1978)","journal-title":"Z. Wahrsch. Werw. Gebiete"},{"issue":"2","key":"19_CR24","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1007\/BF01844850","volume":"16","author":"M. Talagrand","year":"1996","unstructured":"Talagrand, M.: How much are increasing sets positively correlated? Combinatorica\u00a016(2), 243\u2013258 (1996)","journal-title":"Combinatorica"},{"issue":"3","key":"19_CR25","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1016\/0196-6774(84)90016-6","volume":"5","author":"L. Valiant","year":"1984","unstructured":"Valiant, L.: Short monotone formulae for the majority function. J. Algorithms\u00a05(3), 363\u2013366 (1984)","journal-title":"J. Algorithms"},{"key":"19_CR26","unstructured":"Viola, E.: On probabilistic time versus alternating time. In: ECCC 2005, 173 (2005)"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-73420-8_19.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,13]],"date-time":"2023-05-13T22:39:28Z","timestamp":1684017568000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-73420-8_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540734192","9783540734208"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-73420-8_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}