{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T05:57:52Z","timestamp":1775282272499,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":34,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540729259","type":"print"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-72927-3_30","type":"book-chapter","created":{"date-parts":[[2007,6,12]],"date-time":"2007-06-12T02:30:27Z","timestamp":1181615427000},"page":"409-423","source":"Crossref","is-referenced-by-count":8,"title":["A Lower Bound for Agnostically Learning Disjunctions"],"prefix":"10.1007","author":[{"given":"Adam R.","family":"Klivans","sequence":"first","affiliation":[]},{"given":"Alexander A.","family":"Sherstov","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1-3","key":"30_CR1","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/S0012-365X(03)00227-9","volume":"273","author":"N. Alon","year":"2003","unstructured":"Alon, N.: Problems and results in extremal combinatorics, Part\u00a0I. Discrete Mathematics\u00a0273(1-3), 31\u201353 (2003)","journal-title":"Discrete Mathematics"},{"key":"30_CR2","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1162\/153244303321897681","volume":"3","author":"S. Ben-David","year":"2003","unstructured":"Ben-David, S., Eiron, N., Simon, H.U.: Limitations of learning via embeddings in Euclidean half spaces. J. Mach. Learn. Res\u00a03, 441\u2013461 (2003)","journal-title":"J. Mach. Learn. Res"},{"issue":"4","key":"30_CR3","doi-asserted-by":"publisher","first-page":"747","DOI":"10.1145\/234533.234564","volume":"43","author":"N.H. Bshouty","year":"1996","unstructured":"Bshouty, N.H., Tamon, C.: On the Fourier spectrum of monotone functions. J. ACM\u00a043(4), 747\u2013770 (1996)","journal-title":"J. ACM"},{"key":"30_CR4","doi-asserted-by":"crossref","unstructured":"Buhrman, H., de Wolf, R.: Communication complexity lower bounds by polynomials. In: Conference on Computational Complexity (CCC), pp. 120\u2013130 (2001)","DOI":"10.1109\/CCC.2001.933879"},{"key":"30_CR5","doi-asserted-by":"crossref","unstructured":"Buhrman, H., Vereshchagin, N.K., de Wolf, R.: On computation and communication with small bias. In: 22nd IEEE Conference on Computational Complexity (2007)","DOI":"10.1109\/CCC.2007.18"},{"key":"30_CR6","doi-asserted-by":"crossref","unstructured":"Decatur, S.E.: Statistical queries and faulty PAC oracles. In: COLT, pp. 262\u2013268 (1993)","DOI":"10.1145\/168304.168346"},{"issue":"4","key":"30_CR7","doi-asserted-by":"publisher","first-page":"612","DOI":"10.1016\/S0022-0000(02)00019-3","volume":"65","author":"J. Forster","year":"2002","unstructured":"Forster, J.: A linear lower bound on the unbounded error probabilistic communication complexity. J. Comput. Syst. Sci.\u00a065(4), 612\u2013625 (2002)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"30_CR8","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1016\/j.tcs.2005.10.015","volume":"350","author":"J. Forster","year":"2006","unstructured":"Forster, J., Simon, H.U.: On the smallest possible dimension and the largest possible margin of linear arrangements representing given concept classes. Theor. Comput. Sci.\u00a0350(1), 40\u201348 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"30_CR9","volume-title":"Matrix computations","author":"G.H. Golub","year":"1996","unstructured":"Golub, G.H., Loan, C.F.V.: Matrix computations, 3rd edn. Johns Hopkins University Press, Baltimore, MD, USA (1996)","edition":"3"},{"key":"30_CR10","unstructured":"Jackson, J.C.: The harmonic sieve: A novel application of Fourier analysis to machine learning theory and practice. PhD thesis, Carnegie Mellon University (1995)"},{"key":"30_CR11","doi-asserted-by":"crossref","unstructured":"Kalai, A., Klivans, A., Mansour, Y., Servedio, R.: Agnostically learning halfspaces. In: FOCS: IEEE Symposium on Foundations of Computer Science (FOCS) (2005)","DOI":"10.1109\/SFCS.2005.13"},{"issue":"4","key":"30_CR12","doi-asserted-by":"crossref","first-page":"535","DOI":"10.4213\/mzm1314","volume":"63","author":"B. Kashin","year":"1998","unstructured":"Kashin, B., Razborov, A.A.: Improved lower bounds on the rigidity of Hadamard matrices (In Russian). Matematicheskie zamet\u00a063(4), 535\u2013540 (1998)","journal-title":"Matematicheskie zamet"},{"key":"30_CR13","doi-asserted-by":"publisher","first-page":"392","DOI":"10.1145\/167088.167200","volume-title":"STOC \u201993: Proceedings of the twenty-fifth annual ACM symposium on theory of computing","author":"M. Kearns","year":"1993","unstructured":"Kearns, M.: Efficient noise-tolerant learning from statistical queries. In: STOC \u201993: Proceedings of the twenty-fifth annual ACM symposium on theory of computing, pp. 392\u2013401. ACM Press, New York (1993)"},{"issue":"4","key":"30_CR14","doi-asserted-by":"publisher","first-page":"807","DOI":"10.1137\/0222052","volume":"22","author":"M. Kearns","year":"1993","unstructured":"Kearns, M., Li, M.: Learning in the presence of malicious errors. SIAM Journal on Computing\u00a022(4), 807\u2013837 (1993)","journal-title":"SIAM Journal on Computing"},{"issue":"2\u20133","key":"30_CR15","first-page":"115","volume":"17","author":"M.J. Kearns","year":"1994","unstructured":"Kearns, M.J., Shapire, R.E., Sellie, L.M.: Toward efficient agnostic learning. Machine Learning\u00a017(2\u20133), 115\u2013141 (1994)","journal-title":"Machine Learning"},{"key":"30_CR16","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/3897.001.0001","volume-title":"An Introduction to Computational Learning Theory","author":"M.J. Kearns","year":"1994","unstructured":"Kearns, M.J., Vazirani, U.V.: An Introduction to Computational Learning Theory. MIT Press, Cambridge, MA, USA (1994)"},{"issue":"4","key":"30_CR17","doi-asserted-by":"publisher","first-page":"808","DOI":"10.1016\/j.jcss.2003.11.002","volume":"68","author":"A.R. Klivans","year":"2004","unstructured":"Klivans, A.R., O\u2019Donnell, R., Servedio, R.A.: Learning intersections and thresholds of halfspaces. J. Comput. Syst. Sci.\u00a068(4), 808\u2013840 (2004)","journal-title":"J. Comput. Syst. Sci."},{"key":"30_CR18","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1145\/380752.380809","volume-title":"STOC \u201901: Proceedings of the thirty-third annual ACM symposium on Theory of computing","author":"A.R. Klivans","year":"2001","unstructured":"Klivans, A.R., Servedio, R.: Learning DNF in time $2^{\\tilde{O}(n^{1\/3})}$ . In: STOC \u201901: Proceedings of the thirty-third annual ACM symposium on Theory of computing, pp. 258\u2013265. ACM Press, New York (2001)"},{"issue":"6","key":"30_CR19","doi-asserted-by":"publisher","first-page":"1331","DOI":"10.1137\/0222080","volume":"22","author":"E. Kushilevitz","year":"1993","unstructured":"Kushilevitz, E., Mansour, Y.: Learning decision trees using the Fourier spectrum. SIAM J. Comput.\u00a022(6), 1331\u20131348 (1993)","journal-title":"SIAM J. Comput."},{"key":"30_CR20","volume-title":"Communication complexity","author":"E. Kushilevitz","year":"1997","unstructured":"Kushilevitz, E., Nisan, N.: Communication complexity. Cambridge University Press, Cambridge (1997)"},{"issue":"3","key":"30_CR21","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. J. ACM\u00a040(3), 607\u2013620 (1993)","journal-title":"J. ACM"},{"key":"30_CR22","doi-asserted-by":"crossref","unstructured":"Linial, N., Mendelson, S., Schechtman, G., Shraibman, A.: Complexity measures of sign matrices. Combinatorica, (2006) To appear, Manuscript at http:\/\/www.cs.huji.ac.il\/\u00f1ati\/PAPERS\/complexity_matrices.ps.gz","DOI":"10.1007\/s00493-007-2160-5"},{"key":"30_CR23","unstructured":"Linial, N., Shraibman, A.: Learning complexity vs.\u00a0communication complexity. (December 2006) Manuscript at http:\/\/www.cs.huji.ac.il\/\u00f1ati\/PAPERS\/lcc.pdf"},{"key":"30_CR24","doi-asserted-by":"crossref","unstructured":"Linial, N., Shraibman, A.: Lower bounds in communication complexity based on factorization norms. (December 2006) Manuscript at http:\/\/www.cs.huji.ac.il\/~nati\/PAPERS\/ccfn.pdf","DOI":"10.1145\/1250790.1250892"},{"issue":"3","key":"30_CR25","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1006\/jcss.2001.1786","volume":"63","author":"S.V. Lokam","year":"2001","unstructured":"Lokam, S.V.: Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity. J. Comput. Syst. Sci.\u00a063(3), 449\u2013473 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"30_CR26","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1145\/130385.130391","volume-title":"COLT \u201992: Proceedings of the Fifth Annual Workshop on Computational Learning Theory","author":"Y. Mansour","year":"1992","unstructured":"Mansour, Y.: An O(n loglogn ) learning algorithm for DNF under the uniform distribution. In: COLT \u201992: Proceedings of the Fifth Annual Workshop on Computational Learning Theory, pp. 53\u201361. ACM Press, New York, USA (1992)"},{"key":"30_CR27","unstructured":"Mansour, Y., Parnas, M.: On learning conjunctions with malicious noise. In: ISTCS, pp. 170\u2013175 (1996)"},{"key":"30_CR28","doi-asserted-by":"crossref","unstructured":"O\u2019Donnell, R., Servedio, R.A.: Extremal properties of polynomial threshold functions. In: IEEE Conference on Computational Complexity, pp. 3\u201312 (2003)","DOI":"10.1109\/CCC.2003.1214406"},{"key":"30_CR29","doi-asserted-by":"crossref","unstructured":"Paturi, R.: On the degree of polynomials that approximate symmetric Boolean functions. In: STOC: ACM Symposium on Theory of Computing (STOC) (1992)","DOI":"10.1145\/129712.129758"},{"key":"30_CR30","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1070\/IM2003v067n01ABEH000422","volume":"67","author":"A.A. Razborov","year":"2002","unstructured":"Razborov, A.A.: Quantum communication complexity of symmetric predicates. Izvestiya of the Russian Academy of Science, Mathematics\u00a067, 145\u2013159 (2002)","journal-title":"Izvestiya of the Russian Academy of Science, Mathematics"},{"key":"30_CR31","volume-title":"Principles of Mathematical Analysis","author":"W. Rudin","year":"1976","unstructured":"Rudin, W.: Principles of Mathematical Analysis, 3rd edn. McGraw-Hill, New York (1976)","edition":"3"},{"key":"30_CR32","doi-asserted-by":"crossref","unstructured":"Sherstov, A.A.: Halfspace matrices. In: Proc. of the 22nd Conference on Computational Complexity (CCC) (2007)","DOI":"10.1109\/CCC.2007.11"},{"key":"30_CR33","doi-asserted-by":"crossref","unstructured":"Sherstov, A.A.: Separating AC0 from depth-2 majority circuits. In: Proc. of the 39th Symposium on Theory of Computing (STOC) (2007)","DOI":"10.1145\/1250790.1250834"},{"key":"30_CR34","first-page":"560","volume":"1","author":"L.G. Valiant","year":"1985","unstructured":"Valiant, L.G.: Learning disjunctions of conjunctions. California\u00a01, 560\u2013566 (1985)","journal-title":"California"}],"container-title":["Lecture Notes in Computer Science","Learning Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-72927-3_30.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T05:52:47Z","timestamp":1737093167000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-72927-3_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540729259"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-72927-3_30","relation":{},"subject":[]}}