{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,5]],"date-time":"2025-11-05T06:18:37Z","timestamp":1762323517445},"reference-count":60,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2012,8,22]],"date-time":"2012-08-22T00:00:00Z","timestamp":1345593600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2013,9]]},"DOI":"10.1007\/s00037-012-0045-5","type":"journal-article","created":{"date-parts":[[2012,8,21]],"date-time":"2012-08-21T08:08:15Z","timestamp":1345536495000},"page":"623-677","source":"Crossref","is-referenced-by-count":9,"title":["Improved Approximation of Linear Threshold Functions"],"prefix":"10.1007","volume":"22","author":[{"given":"Ilias","family":"Diakonikolas","sequence":"first","affiliation":[]},{"given":"Rocco A.","family":"Servedio","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2012,8,22]]},"reference":[{"issue":"1\u20132","key":"45_CR1","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1007\/s00440-007-0125-7","volume":"143","author":"Aizenman M.","year":"2009","unstructured":"M. Aizenman, F. Germinet, A. Klein, S. Warzel (2009) On Bernoulli decompositions for random variables, concentration bounds, and spectral localization. Probability Theory and Related Fields 143(1\u20132): 219\u2013238","journal-title":"Probability Theory and Related Fields"},{"issue":"1","key":"45_CR2","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1006\/jcta.1997.2780","volume":"79","author":"Alon N","year":"1997","unstructured":"N Alon, V. H. Vu (1997) Anti-Hadamard Matrices, Coin Weighing, Threshold Gates, and Indecomposable Hypergraphs. Journal of Combinatorial Theory, Series A 79(1): 133\u2013160","journal-title":"Anti-Hadamard Matrices, Coin Weighing, Threshold Gates, and Indecomposable Hypergraphs. Journal of Combinatorial Theory, Series A"},{"key":"45_CR3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0166-218X(94)00007-Z","volume":"61","author":"Anthony M","year":"1995","unstructured":"M Anthony, G. Brightwell, J. Shawe-Taylor (1995) On specifying Boolean functions using labelled examples. Discrete Applied Mathematics 61: 1\u201325","journal-title":"Discrete Applied Mathematics"},{"key":"45_CR4","first-page":"159","volume":"102","author":"Beckner W","year":"1975","unstructured":"W Beckner (1975) Inequalities in Fourier analysis. Annals of Mathematics 102: 159\u2013182","journal-title":"Inequalities in Fourier analysis. Annals of Mathematics"},{"key":"45_CR5","doi-asserted-by":"crossref","unstructured":"R. Beigel (1994). Perceptrons, PP, and the Polynomial Hierarchy. Computational Complexity 4, 339\u2013349.","DOI":"10.1007\/BF01263422"},{"issue":"1","key":"45_CR6","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/j.ipl.2005.09.008","volume":"97","author":"Beimel A","year":"2006","unstructured":"A Beimel, E. Weinreb (2006) Monotone circuits for monotone weighted threshold functions. Information Processing Letters 97(1): 12\u201318","journal-title":"Information Processing Letters"},{"key":"45_CR7","unstructured":"M. Bellare & J. Rompel (1994). Randomness-Efficient Oblivious Sampling. In 35th Annual Symposium on Foundations of Computer Science (FOCS), 276\u2013287."},{"issue":"2","key":"45_CR8","doi-asserted-by":"crossref","first-page":"335","DOI":"10.5802\/aif.357","volume":"20","author":"Bonami A","year":"1970","unstructured":"A Bonami (1970) Etude des coefficients Fourier des fonctiones de L p (G). Ann. Inst. Fourier (Grenoble) 20(2): 335\u2013402","journal-title":"Ann. Inst. Fourier (Grenoble)"},{"key":"45_CR9","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF02785861","volume":"131","author":"Bourgain J","year":"2002","unstructured":"J Bourgain (2002) On the distributions of the Fourier spectrum of Boolean functions. Israel J. Math. 131: 269\u2013276","journal-title":"Israel J. Math."},{"issue":"1","key":"45_CR10","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1137\/0221003","volume":"21","author":"Bruck J","year":"1992","unstructured":"J Bruck, R. Smolensky (1992) Polynomial threshold functions, AC 0 functions and spectral norms. SIAM Journal on Computing 21(1): 33\u201342","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"45_CR11","doi-asserted-by":"crossref","first-page":"747","DOI":"10.1145\/234533.234564","volume":"43","author":"Bshouty N","year":"1996","unstructured":"N Bshouty, C. Tamon (1996) On the Fourier spectrum of monotone functions. Journal of the ACM 43(4): 747\u2013770","journal-title":"Journal of the ACM"},{"issue":"2","key":"45_CR12","doi-asserted-by":"crossref","first-page":"94","DOI":"10.1007\/s00037-006-0210-9","volume":"15","author":"Chawla S","year":"2006","unstructured":"S Chawla, R. Krauthgamer, R. Kumar, Y. Rabani, D. Sivakumar (2006) On the Hardness of Approximating Multicut and Sparsest-Cut. Computational Complexity 15(2): 94\u2013114","journal-title":"Computational Complexity"},{"key":"45_CR13","unstructured":"M. Dertouzos (1965). Threshold Logic: A Synthesis Approach. MIT Press, Cambridge, MA."},{"issue":"8","key":"45_CR14","doi-asserted-by":"crossref","first-page":"3441","DOI":"10.1137\/100783030","volume":"39","author":"Diakonikolas I","year":"2010","unstructured":"I Diakonikolas, P. Gopalan, R. Jaiswal, R. Servedio, E. Viola (2010) Bounded independence fools halfspaces. SIAM J. on Comput. 39(8): 3441\u20133462","journal-title":"SIAM J. on Comput."},{"issue":"1","key":"45_CR15","doi-asserted-by":"crossref","first-page":"439","DOI":"10.4007\/annals.2005.162.439","volume":"162","author":"Dinur I","year":"2005","unstructured":"I Dinur, S. Safra (2005) On the Hardness of Approximating Minimum Vertex-Cover. Annals of Mathematics 162(1): 439\u2013485","journal-title":"Annals of Mathematics"},{"key":"45_CR16","first-page":"2027","volume":"202","author":"Doeblin W","year":"1936","unstructured":"W Doeblin, P. L\u00e9vy (1936) Calcul des probabilit\u00e9s. Sur les sommes de variables al\u00e9atoires ind\u00e9pendantes \u2019a dispersions born\u00e9es inf\u00e9rieurement. C.R. Acad. Sci. 202: 2027\u20132029","journal-title":"Sur les sommes de variables al\u00e9atoires ind\u00e9pendantes \u2019a dispersions born\u00e9es inf\u00e9rieurement. C.R. Acad. Sci."},{"key":"45_CR17","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511581274","volume-title":"Concentration of measure for the analysis of randomized algorithms","author":"Dubhashi D","year":"2009","unstructured":"D Dubhashi, A. Panconesi (2009) Concentration of measure for the analysis of randomized algorithms. Cambridge University Press, Cambridge"},{"key":"45_CR18","doi-asserted-by":"crossref","first-page":"898","DOI":"10.1090\/S0002-9904-1945-08454-7","volume":"51","author":"Erd\u00f6s P","year":"1945","unstructured":"P Erd\u00f6s (1945) On a lemma of Littlewood and Offord. Bull. Amer. Math. Soc. 51: 898\u2013902","journal-title":"Bull. Amer. Math. Soc."},{"key":"45_CR19","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1090\/pspum\/008\/0174539","volume":"8","author":"Erd\u00f6s P","year":"1965","unstructured":"P Erd\u00f6s (1965) Extremal Problems in Number Theory. Proc. Sympos. Pure Math. 8: 181\u2013189","journal-title":"Proc. Sympos. Pure Math."},{"key":"45_CR20","doi-asserted-by":"crossref","first-page":"290","DOI":"10.1007\/BF00531753","volume":"9","author":"Ess\u00e9en C.G.","year":"1968","unstructured":"C.G. Ess\u00e9en (1968) On the concentration function of a sum of independent random variables. Z. Wahrscheinlichkeitstheorie verw. Geb. 9: 290\u2013308","journal-title":"Z. Wahrscheinlichkeitstheorie verw. Geb."},{"issue":"2","key":"45_CR21","doi-asserted-by":"crossref","first-page":"606","DOI":"10.1137\/070684914","volume":"39","author":"Feldman V","year":"2009","unstructured":"V Feldman, P. Gopalan, S. Khot, A. Ponnuswami (2009) On Agnostic Learning of Parities, Monomials, and Halfspaces. SIAM J. Comput. 39(2): 606\u2013645","journal-title":"SIAM J. Comput."},{"key":"45_CR22","unstructured":"W. Feller (1968). An introduction to probability theory and its applications. John Wiley & Sons."},{"key":"45_CR23","unstructured":"A. Fiat & D. Pechyony (2004). Decision Trees: More Theoretical Justification for Practical Algorithms. In Algorithmic Learning Theory, 15th International Conference (ALT 2004), 156\u2013170."},{"issue":"1","key":"45_CR24","doi-asserted-by":"crossref","first-page":"474","DOI":"10.1007\/PL00009809","volume":"18","author":"Friedgut E","year":"1998","unstructured":"E Friedgut (1998) Boolean functions with low average sensitivity depend on few coordinates. Combinatorica 18(1): 474\u2013483","journal-title":"Combinatorica"},{"key":"45_CR25","doi-asserted-by":"crossref","first-page":"2993","DOI":"10.1090\/S0002-9939-96-03732-X","volume":"124","author":"Friedgut E","year":"1996","unstructured":"E Friedgut, G. Kalai (1996) Every Monotone Graph Property has a Sharp Threshold. Proc. Amer. Math. Soc. 124: 2993\u20133002","journal-title":"Proc. Amer. Math. Soc."},{"key":"45_CR26","doi-asserted-by":"crossref","unstructured":"D. Glasner, R. A. Servedio (2009). Distribution-Free Testing Lower Bound for Basic Boolean Functions. Theory of Computing 5(1), 191\u2013216.","DOI":"10.4086\/toc.2009.v005a010"},{"key":"45_CR27","doi-asserted-by":"crossref","first-page":"328","DOI":"10.1137\/S0895480103426765","volume":"20","author":"Goldberg P","year":"2006","unstructured":"P Goldberg (2006) A Bound on the Precision Required to Estimate a Boolean Perceptron from its Average Satisfying Assignment. SIAM Journal on Discrete Mathematics 20: 328\u2013343","journal-title":"SIAM Journal on Discrete Mathematics"},{"issue":"4","key":"45_CR28","doi-asserted-by":"crossref","first-page":"1061","DOI":"10.2307\/2373688","volume":"97","author":"Gross L","year":"1975","unstructured":"L Gross (1975) Logarithmic Sobolev inequalities. Amer. J. Math. 97(4): 1061\u20131083","journal-title":"J. Math."},{"issue":"3","key":"45_CR29","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1007\/BF02018403","volume":"8","author":"Hal\u00e1sz G","year":"1977","unstructured":"G Hal\u00e1sz (1977) Estimates for the concentration function of combinatorial number theory and probability. Period. Math. Hungar. 8(3): 197\u2013211","journal-title":"Math. Hungar."},{"key":"45_CR30","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1007\/BF00336991","volume":"53","author":"Hampson S","year":"1986","unstructured":"S Hampson, D. Volper (1986) Linear function neurons: structure and training. Biological Cybernetics 53: 203\u2013217","journal-title":"Biological Cybernetics"},{"issue":"3","key":"45_CR31","doi-asserted-by":"crossref","first-page":"484","DOI":"10.1137\/S0895480192235878","volume":"7","author":"H\u00e5stad J","year":"1994","unstructured":"J H\u00e5stad (1994) On the size of weights for threshold gates. SIAM Journal on Discrete Mathematics 7(3): 484\u2013492","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"45_CR32","unstructured":"J. H\u00e5stad (2005). Personal communication."},{"key":"45_CR33","unstructured":"J. Hong (1987). On connectionist models. Technical Report 87-012, Dept. of Computer Science, University of Chicago."},{"key":"45_CR34","doi-asserted-by":"crossref","unstructured":"J. Kahn, G. Kalai& N. Linial (1988). The influence of variables on boolean functions. In Proc. 29th Annual Symposium on Foundations of Computer Science (FOCS), 68\u201380.","DOI":"10.1109\/SFCS.1988.21923"},{"key":"45_CR35","doi-asserted-by":"crossref","unstructured":"A. Kalai (2007). Learning Nested Halfspaces and Uphill Decision Trees. In Proc. 20th Annual Conference on Learning Theory (COLT), 378\u2013392.","DOI":"10.1007\/978-3-540-72927-3_28"},{"issue":"6","key":"45_CR36","doi-asserted-by":"crossref","first-page":"1777","DOI":"10.1137\/060649057","volume":"37","author":"Kalai A","year":"2008","unstructured":"A Kalai, A. Klivans, Y. Mansour, R. Servedio (2008) Agnostically Learning Halfspaces. SIAM Journal on Computing 37(6): 1777\u20131805","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"45_CR37","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/j.jcss.2007.06.019","volume":"74","author":"Khot S","year":"2008","unstructured":"S Khot, O. Regev (2008) Vertex cover might be hard to approximate to within $${2 - \\epsilon}$$ . Journal of Computer & System Sciences 74(3): 335\u2013349","journal-title":"Journal of Computer & System Sciences"},{"issue":"1","key":"45_CR38","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1016\/j.jcss.2010.06.010","volume":"77","author":"Khot S","year":"2011","unstructured":"S Khot, R. Saket (2011) On the hardness of learning intersections of two halfspaces. J. Comput. Syst. Sci. 77(1): 129\u2013141","journal-title":"J. Comput. Syst. Sci."},{"key":"45_CR39","unstructured":"A.N. Kolmogorov (1958-60). Sur les propri\u00e9t\u00e9s des fonctions de concentration de M. P. L\u00e9vy. Ann. Inst. H. Poincar\u00e9 16, 27\u201334."},{"issue":"6","key":"45_CR40","doi-asserted-by":"crossref","first-page":"2487","DOI":"10.1137\/060660126","volume":"38","author":"Krauthgamer R","year":"2009","unstructured":"R Krauthgamer, Y. Rabani (2009) Improved Lower Bounds for Embeddings into L1. SIAM J. Comput. 38(6): 2487\u20132498","journal-title":"SIAM J. Comput."},{"key":"45_CR41","unstructured":"J. E. Littlewood & A. C. Offord (1943). On the number of real roots of a random algebraic equation. III. Rec. Math. [Mat. Sbornik] N.S. 12, 277\u2013286."},{"issue":"5","key":"45_CR42","doi-asserted-by":"crossref","first-page":"2004","DOI":"10.1137\/070707890","volume":"39","author":"Matulef K","year":"2010","unstructured":"K Matulef, R. O\u2019Donnell, R. Rubinfeld, R. Servedio (2010) Testing Halfspaces. SIAM J. on Comput. 39(5): 2004\u20132047","journal-title":"SIAM J. on Comput."},{"key":"45_CR43","volume-title":"Threshold logic and its applications","author":"Muroga S","year":"1971","unstructured":"S Muroga (1971) Threshold logic and its applications. Wiley-Interscience, New York."},{"key":"45_CR44","doi-asserted-by":"crossref","first-page":"376","DOI":"10.1016\/0016-0032(61)90702-5","volume":"271","author":"Muroga S","year":"1961","unstructured":"S Muroga, I. Toda, S. Takasu (1961) Theory of majority switching elements. J. Franklin Institute 271: 376\u2013418","journal-title":"J. Franklin Institute"},{"key":"45_CR45","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1007\/BF01263419","volume":"4","author":"Nisan N","year":"1994","unstructured":"N Nisan, M. Szegedy (1994) On the degree of Boolean functions as real polynomials. Comput. Complexity 4: 301\u2013313","journal-title":"Comput. Complexity"},{"issue":"3","key":"45_CR46","doi-asserted-by":"crossref","first-page":"827","DOI":"10.1137\/060669309","volume":"37","author":"O\u2019Donnell R","year":"2007","unstructured":"R O\u2019Donnell, R. Servedio (2007) Learning monotone decision trees in polynomial time. SIAM J. on Comput. 37(3): 827\u2013844","journal-title":"SIAM J. on Comput."},{"issue":"1","key":"45_CR47","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1137\/090756466","volume":"40","author":"O\u2019Donnell R","year":"2011","unstructured":"R O\u2019Donnell, R. Servedio (2011) The Chow Parameters Problem. SIAM J. on Comput. 40(1): 165\u2013199","journal-title":"SIAM J. on Comput."},{"issue":"8","key":"45_CR48","doi-asserted-by":"crossref","first-page":"3501","DOI":"10.1137\/090764190","volume":"39","author":"Rabani Y","year":"2010","unstructured":"Y Rabani, A. Shpilka (2010) Explicit construction of a small epsilon-net for linear threshold functions. SIAM J. on Comput. 39(8): 3501\u20133520","journal-title":"SIAM J. on Comput."},{"key":"45_CR49","unstructured":"P. Raghavan (1988). Learning in threshold networks. In First Workshop on Computational Learning Theory, 19\u201327."},{"key":"45_CR50","unstructured":"B.A. Rogozin (1973). An integral-type estimate for concentration functions of sums of independent random variables. Dokl. Akad. Nauk SSSR 211, 1067\u20131070."},{"issue":"2","key":"45_CR51","doi-asserted-by":"crossref","first-page":"600","DOI":"10.1016\/j.aim.2008.01.010","volume":"218","author":"Rudelson M","year":"2008","unstructured":"M Rudelson, R. Vershynin (2008) The Littlewood-Offord Problem and invertibility of random matrices. Advances in Mathematics 218(2): 600\u2013633","journal-title":"Advances in Mathematics"},{"key":"45_CR52","doi-asserted-by":"crossref","unstructured":"A. S\u00e1rk\u00f6zy & E. Szemer\u00e9di (1965). \u00dcber ein Problem von Erd\u00f6s und Moser. Acta Arithmetica 11, 205\u2013208.","DOI":"10.4064\/aa-11-2-205-208"},{"issue":"2","key":"45_CR53","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1007\/s00037-007-0228-7","volume":"16","author":"R. Servedio","year":"2007","unstructured":"Servedio R. (2007) Every linear threshold function has a low-weight approximator. Comput. Complexity 16(2): 180\u2013209","journal-title":"Comput. Complexity"},{"issue":"2","key":"45_CR54","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1007\/s00037-008-0242-4","volume":"17","author":"Sherstov A.A.","year":"2008","unstructured":"A.A. Sherstov (2008) Halfspace Matrices. Comput. Complexity 17(2): 149\u2013178","journal-title":"Comput. Complexity"},{"key":"45_CR55","doi-asserted-by":"crossref","unstructured":"I.S. Shiganov (1986). Refinement of the upper bound of the constant in the central limit theorem. Journal of Soviet Mathematics 2545\u20132550.","DOI":"10.1007\/BF01121471"},{"key":"45_CR56","unstructured":"K.-Y. Siu, V.P. Roychowdhury & T. Kailath (1995). Discrete Neural Computation: A Theoretical Foundation. Prentice-Hall, Englewood Cliffs, NJ."},{"key":"45_CR57","unstructured":"T. Tao & V. Vu (2006). Additive Combinatorics. Cambridge Studies in Advanced Mathematics, Cambridge University Press, Cambridge."},{"key":"45_CR58","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1090\/S0273-0979-09-01252-X","volume":"46","author":"Tao T","year":"2009","unstructured":"T Tao, V. Vu (2009) From the Littlewood-Offord problem to the Circular Law: universality of the spectral distribution of random matrices. Bull. Amer. Math. Soc. 46: 377\u2013396","journal-title":"Bull. Amer. Math. Soc."},{"key":"45_CR59","doi-asserted-by":"crossref","unstructured":"V. Vu (2008). A Structural Approach to Subset-Sum Problems. In Building Bridges, volume 19 of Bolyai Society Mathematical Studies, 525\u2013545. Springer, Berlin, Heidelberg.","DOI":"10.1007\/978-3-540-85221-6_19"},{"key":"45_CR60","unstructured":"A. Wigderson (1994). The amazing power of pairwise independence. In Proceedings of the 26th ACM Symposium on Theory of Computing, 645\u2013647."}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-012-0045-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-012-0045-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-012-0045-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,3]],"date-time":"2019-07-03T00:42:30Z","timestamp":1562114550000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-012-0045-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,8,22]]},"references-count":60,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2013,9]]}},"alternative-id":["45"],"URL":"https:\/\/doi.org\/10.1007\/s00037-012-0045-5","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,8,22]]}}}