{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T19:55:18Z","timestamp":1725738918149},"publisher-location":"Berlin, Heidelberg","reference-count":35,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642392054"},{"type":"electronic","value":"9783642392061"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-39206-1_32","type":"book-chapter","created":{"date-parts":[[2013,7,2]],"date-time":"2013-07-02T13:20:16Z","timestamp":1372771216000},"page":"376-387","source":"Crossref","is-referenced-by-count":1,"title":["A Robust Khintchine Inequality, and Algorithms for Computing Optimal Constants in Fourier Analysis and High-Dimensional Geometry"],"prefix":"10.1007","author":[{"given":"Anindya","family":"De","sequence":"first","affiliation":[]},{"given":"Ilias","family":"Diakonikolas","sequence":"additional","affiliation":[]},{"given":"Rocco","family":"Servedio","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"3","key":"32_CR1","doi-asserted-by":"publisher","first-page":"784","DOI":"10.1016\/j.jctb.2011.12.002","volume":"102","author":"N. Alon","year":"2012","unstructured":"Alon, N., Huang, H., Sudakov, B.: Nonnegative k-sums, fractional covers, and probability of small deviations. J. Combin. Theory, Series B\u00a0102(3), 784\u2013796 (2012)","journal-title":"J. Combin. Theory, Series B"},{"unstructured":"Bentkus, V., Dzindzalieta, D.: A tight Gaussian bound for weighted sums of Rademacher random variables. Technical report (2012) (preprint)","key":"32_CR2"},{"issue":"3","key":"32_CR3","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1006\/jcss.1998.1569","volume":"56","author":"S. Ben-David","year":"1998","unstructured":"Ben-David, S., Dichterman, E.: Learning with restricted focus of attention. Journal of Computer and System Sciences\u00a056(3), 277\u2013298 (1998)","journal-title":"Journal of Computer and System Sciences"},{"key":"32_CR4","doi-asserted-by":"publisher","first-page":"1650","DOI":"10.1214\/009117904000000360","volume":"32","author":"V. Bentkus","year":"2004","unstructured":"Bentkus, V.: On Hoeffding\u2019s Inequality. Annals of Probability\u00a032, 1650\u20131673 (2004)","journal-title":"Annals of Probability"},{"key":"32_CR5","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."},{"issue":"2","key":"32_CR6","doi-asserted-by":"publisher","first-page":"535","DOI":"10.1137\/S1052623401392354","volume":"13","author":"A. Ben-Tal","year":"2002","unstructured":"Ben-Tal, A., Nemirovski, A., Roos, C.: Robust Solutions of Uncertain Quadratic and Conic-Quadratic Problems. SIAM J. Optimization\u00a013(2), 535\u2013560 (2002)","journal-title":"SIAM J. Optimization"},{"doi-asserted-by":"crossref","unstructured":"De, A., Diakonikolas, I., Feldman, V., Servedio, R.: Near-optimal solutions for the Chow Parameters Problem and low-weight approximation of halfspaces. In: Proc. 44th ACM Symposium on Theory of Computing (STOC), pp. 729\u2013746 (2012)","key":"32_CR7","DOI":"10.1145\/2213977.2214043"},{"issue":"8","key":"32_CR8","doi-asserted-by":"publisher","first-page":"3441","DOI":"10.1137\/100783030","volume":"39","author":"I. Diakonikolas","year":"2010","unstructured":"Diakonikolas, I., Gopalan, P., Jaiswal, R., Servedio, R., Viola, E.: Bounded independence fools halfspaces. SIAM J. on Comput.\u00a039(8), 3441\u20133462 (2010)","journal-title":"SIAM J. on Comput."},{"doi-asserted-by":"crossref","unstructured":"Diakonikolas, I., Servedio, R.: Improved approximation of linear threshold functions. In: Proc. 24th CCC, pp. 161\u2013172 (2009)","key":"32_CR9","DOI":"10.1109\/CCC.2009.8"},{"unstructured":"Filmus, Y.: Khintchine-Kahane using Fourier Analysis (2012), Posted at \n                    \n                      http:\/\/www.cs.toronto.edu\/~yuvalf\/KK.pdf","key":"32_CR10"},{"issue":"1","key":"32_CR11","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/BF01305949","volume":"14","author":"C. Gotsman","year":"1994","unstructured":"Gotsman, C., Linial, N.: Spectral properties of threshold functions. Combinatorica\u00a014(1), 35\u201350 (1994)","journal-title":"Combinatorica"},{"key":"32_CR12","doi-asserted-by":"publisher","first-page":"279","DOI":"10.2307\/2323678","volume":"93","author":"R.K. Guy","year":"1986","unstructured":"Guy, R.K.: Any answers anent these analytical enigmas? American Math. Monthly\u00a093, 279\u2013281 (1986)","journal-title":"American Math. Monthly"},{"key":"32_CR13","doi-asserted-by":"crossref","first-page":"231","DOI":"10.4064\/sm-70-3-231-283","volume":"70","author":"U. Haagerup","year":"1982","unstructured":"Haagerup, U.: The best constants in the Khintchine inequality. Studia Math.\u00a070, 231\u2013283 (1982)","journal-title":"Studia Math."},{"issue":"3","key":"32_CR14","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/BF01285819","volume":"12","author":"R. Holzman","year":"1992","unstructured":"Holzman, R., Kleitman, D.J.: On the product of sign vectors and unit vectors. Combinatorica\u00a012(3), 303\u2013316 (1992)","journal-title":"Combinatorica"},{"doi-asserted-by":"crossref","unstructured":"Hitczenko, P., Kwapie\u0144, S.: On the Rademacher series. In: Probability in Banach Spaces, pp. 31\u201336 (1994)","key":"32_CR15","DOI":"10.1007\/978-1-4612-0253-0_2"},{"key":"32_CR16","doi-asserted-by":"publisher","first-page":"503","DOI":"10.1137\/070679041","volume":"19","author":"S. He","year":"2008","unstructured":"He, S., Luo, Z., Nie, J., Zhang, S.: Semidefinite Relaxation Bounds for Indefinite Homogenous Quadratic Optimization. SIAM J. Optimization\u00a019, 503\u2013523 (2008)","journal-title":"SIAM J. Optimization"},{"key":"32_CR17","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"304","DOI":"10.1007\/11776420_24","volume-title":"Learning Theory","author":"J.C. Jackson","year":"2006","unstructured":"Jackson, J.C.: Uniform-distribution learnability of noisy linear threshold functions with restricted focus of attention. In: Lugosi, G., Simon, H.U. (eds.) COLT 2006. LNCS (LNAI), vol.\u00a04005, pp. 304\u2013318. Springer, Heidelberg (2006)"},{"key":"32_CR18","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1006\/jfan.1996.0030","volume":"136","author":"S. Kwapie\u0144","year":"1996","unstructured":"Kwapie\u0144, S., Latala, R., Oleszkiewicz, K.: Comparison of moments of sums of independent random variables and differential inequalities. J. Funct. Anal.\u00a0136, 258\u2013268 (1996)","journal-title":"J. Funct. Anal."},{"key":"32_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1515\/crll.1999.511.1","volume":"511","author":"H. K\u00f6nig","year":"1999","unstructured":"K\u00f6nig, H., Sch\u00fctt, C., Tomczak-Jaegermann, N.: Projection constants of symmetric spaces and variants of Khintchine\u2019s inequality. J. Reine Agnew. Math.\u00a0511, 1\u201342 (1999)","journal-title":"J. Reine Agnew. Math."},{"key":"32_CR20","first-page":"101","volume":"109","author":"R. Latala","year":"1994","unstructured":"Latala, R., Oleszkiewicz, K.: On the best constant in the Khinchin-Kahane inequality. Studia Math.\u00a0109, 101\u2013104 (1994)","journal-title":"Studia Math."},{"issue":"5","key":"32_CR21","doi-asserted-by":"publisher","first-page":"2004","DOI":"10.1137\/070707890","volume":"39","author":"K. Matulef","year":"2010","unstructured":"Matulef, K., O\u2019Donnell, R., Rubinfeld, R., Servedio, R.: Testing halfspaces. SIAM J. on Comput.\u00a039(5), 2004\u20132047 (2010)","journal-title":"SIAM J. on Comput."},{"doi-asserted-by":"crossref","unstructured":"Montgomery-Smith, S.: The distribution of Rademacher sums. In: Proceedings of the American Mathematical Society, pp. 517\u2013522 (1990)","key":"32_CR22","DOI":"10.2307\/2048015"},{"unstructured":"Maass, W., Turan, G.: How fast can a threshold gate learn? In: Computational Learning Theory and Natural Learning Systems: Volume I: Constraints and Prospects, pp. 381\u2013414. MIT Press (1994)","key":"32_CR23"},{"unstructured":"O\u2019Donnell, R.: Analysis of boolean functions. Technical report (2012), Book serialization available at \n                    \n                      http:\/\/analysisofbooleanfunctions.org\/","key":"32_CR24"},{"key":"32_CR25","first-page":"127","volume":"16","author":"K. Oleszkiewicz","year":"1996","unstructured":"Oleszkiewicz, K.: On the Stein property of Rademacher sequences. Probability and Mathematical Statistics\u00a016, 127\u2013130 (1996)","journal-title":"Probability and Mathematical Statistics"},{"doi-asserted-by":"crossref","unstructured":"Oleszkiewicz, K.: Comparison of moments via Poincar\u00e9-type inequality. In: Contemporary Mathematics, vol.\u00a0234, pp. 135\u2013148 (1999)","key":"32_CR26","DOI":"10.1090\/conm\/234\/03451"},{"issue":"1","key":"32_CR27","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1137\/090756466","volume":"40","author":"R. O\u2019Donnell","year":"2011","unstructured":"O\u2019Donnell, R., Servedio, R.: The Chow Parameters Problem. SIAM J. on Comput.\u00a040(1), 165\u2013199 (2011)","journal-title":"SIAM J. on Comput."},{"unstructured":"Peres, Y.: Noise stability of weighted majority (2004), \n                    \n                      http:\/\/arxiv.org\/abs\/math\/0412377","key":"32_CR28"},{"key":"32_CR29","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1214\/aos\/1176325373","volume":"22","author":"I. Pinelis","year":"1994","unstructured":"Pinelis, I.: Extremal probabilistic problems and Hotelling\u2019s t\n                           2 test under a symmetry condition. Ann. Statist.\u00a022, 357\u2013368 (1994)","journal-title":"Ann. Statist."},{"key":"32_CR30","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1214\/EJP.v17-2026","volume":"17","author":"I. Pinelis","year":"2012","unstructured":"Pinelis, I.: An asymptotically Gaussian bound on the Rademacher tails. Electronic Journal of Probability\u00a017, 1\u201322 (2012)","journal-title":"Electronic Journal of Probability"},{"doi-asserted-by":"crossref","unstructured":"Renegar, J.: A faster PSPACE algorithm for deciding the existential theory of the reals. In: IEEE Annual Symposium on Foundations of Computer Science, pp. 291\u2013295 (1988)","key":"32_CR31","DOI":"10.1109\/SFCS.1988.21945"},{"issue":"2","key":"32_CR32","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1007\/s00037-007-0228-7","volume":"16","author":"R. Servedio","year":"2007","unstructured":"Servedio, R.: Every linear threshold function has a low-weight approximator. Comput. Complexity\u00a016(2), 180\u2013209 (2007)","journal-title":"Comput. Complexity"},{"unstructured":"So, A.M.-C.: Improved approximation bound for quadratic optimization problems with orthogonality constraints. In: SODA, pp. 1201\u20131209 (2009)","key":"32_CR33"},{"key":"32_CR34","doi-asserted-by":"crossref","first-page":"197","DOI":"10.4064\/sm-58-2-197-208","volume":"58","author":"S.J. Szarek","year":"1976","unstructured":"Szarek, S.J.: On the best constants in the Khinchine inequality. Studia Math.\u00a058, 197\u2013208 (1976)","journal-title":"Studia Math."},{"issue":"2","key":"32_CR35","first-page":"103","volume":"111","author":"B. Tomaszewski","year":"1987","unstructured":"Tomaszewski, B.: A simple and elementary proof of the Khintchine inequality with the best constant. Bull. Sci. Math.\u00a0111(2), 103\u2013109 (1987)","journal-title":"Bull. Sci. Math."}],"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-642-39206-1_32","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,15]],"date-time":"2019-05-15T05:19:04Z","timestamp":1557897544000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-39206-1_32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642392054","9783642392061"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-39206-1_32","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}