{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:23:52Z","timestamp":1750220632258,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":54,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T00:00:00Z","timestamp":1623715200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1612\/17"],"award-info":[{"award-number":["1612\/17"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Binational US-Israel Science Foundation","award":["2014290"],"award-info":[{"award-number":["2014290"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,15]]},"DOI":"10.1145\/3406325.3451011","type":"proceedings-article","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T01:26:13Z","timestamp":1623806773000},"page":"1656-1669","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Local concentration inequalities and Tomaszewski\u2019s conjecture"],"prefix":"10.1145","author":[{"given":"Nathan","family":"Keller","sequence":"first","affiliation":[{"name":"Bar-Ilan University, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ohad","family":"Klein","sequence":"additional","affiliation":[{"name":"Bar-Ilan University, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","first-page":"913","volume-title":"Geom. Func. Anal. 14 ( 5 ) ( 2004 )","author":"Alon N.","unstructured":"N. Alon, I. Dinur, E. Friedgut, and B. Sudakov, Graph Products, Fourier Analysis and Spectral Techniques, Geom. Func. Anal. 14 ( 5 ) ( 2004 ), pp. 913-940."},{"key":"e_1_3_2_1_2_1","series-title":"SIAM J. Optimization, 13 ( 2 ) ( 2002 )","first-page":"535","volume-title":"Robust solutions of uncertain quadratic and conic-quadratic problems","author":"Ben-Tal A.","unstructured":"A. Ben-Tal, A. Nemirovski, and C. Roos, Robust solutions of uncertain quadratic and conic-quadratic problems, SIAM J. Optimization, 13 ( 2 ) ( 2002 ), pp. 535-560."},{"key":"e_1_3_2_1_3_1","first-page":"1231","volume-title":"Bernoulli, 21 ( 2 ) ( 2015 )","author":"Bentkus V. K.","unstructured":"V. K. Bentkus and D. Dzindzalieta, A tight Gaussian bound for weighted sums of Rademacher random variables, Bernoulli, 21 ( 2 ) ( 2015 ), pp. 1231-1237."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004400050136"},{"key":"e_1_3_2_1_5_1","first-page":"851","volume-title":"Ann. Statistics, 25 ( 2 ) ( 1997 )","author":"Bentkus V.","unstructured":"V. Bentkus, F. G\u00f6tze, and W. R. van Zwet, An Edgeworth expansion for symmetric statistics, Ann. Statistics, 25 ( 2 ) ( 1997 ), pp. 851-896."},{"key":"e_1_3_2_1_6_1","volume":"49","author":"Berry A. C.","unstructured":"A. C. Berry, The accuracy of the Gaussian approximation to the sum of independent variates, Trans. Amer. Math. Soc., 49 ( 1 ) ( 1941 ), pp. 122-136.","journal-title":"Trans. Amer. Math. Soc."},{"key":"e_1_3_2_1_7_1","first-page":"1238","volume-title":"Ann. Probab., 30 ( 3 ) ( 2002 )","author":"Blonzelis M.","unstructured":"M. Blonzelis and F. G\u00f6tze, An Edgeworth expansion for symmetric finite population statistics, Ann. Probab., 30 ( 3 ) ( 2002 ), pp. 1238-1265."},{"key":"e_1_3_2_1_8_1","first-page":"1021","volume-title":"Russian Math. Surveys, 71 ( 6 ) ( 2016 )","author":"Bobkov S. G.","unstructured":"S. G. Bobkov, Proximity of probability distributions in terms of Fourier-Stieltjes transforms, Russian Math. Surveys, 71 ( 6 ) ( 2016 ), pp. 1021-1079."},{"key":"e_1_3_2_1_9_1","first-page":"439","volume":"7","author":"Bobkov S. G.","unstructured":"S. G. Bobkov, F. G\u00f6tze, and C. Houdr\u00e9, On Gaussian and Bernoulli covariance representations, Bernoulli, 7 ( 2001 ), pp. 439-451.","journal-title":"On Gaussian and Bernoulli covariance representations, Bernoulli"},{"key":"e_1_3_2_1_10_1","volume-title":"Tomaszewski's problem on randomly signed sums, revisited, preprint","author":"Boppana R. B.","year":"2020","unstructured":"R. B. Boppana, H. Hendriks, and M. C. A. van Zuijlen, Tomaszewski's problem on randomly signed sums, revisited, preprint, 2020. Available at https:\/\/arxiv.org\/abs\/ 2003.06433v2."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"crossref","unstructured":"R. B. Boppana R. Holzman Tomaszewski's problem on randomly signed sums: Breaking the 3\/8 barrier Electron. J. Combin. 24 ( 3 ) ( 2017 ) P3. 40.","DOI":"10.37236\/6949"},{"key":"e_1_3_2_1_12_1","series-title":"SIAM J. Disc. Math., 30 ( 2 ) ( 2016 )","first-page":"1058","volume-title":"A robust Khintchine inequality, and algorithms for computing optimal constants in Fourier analysis and highdimensional geometry","author":"De A.","unstructured":"A. De, I. Diakonikolas, and R. A. Servedio, A robust Khintchine inequality, and algorithms for computing optimal constants in Fourier analysis and highdimensional geometry, SIAM J. Disc. Math., 30 ( 2 ) ( 2016 ), pp. 1058-1094."},{"key":"e_1_3_2_1_13_1","first-page":"143","volume":"36","author":"Devroye L.","unstructured":"L. Devroye and G. Lugosi, Local tail bounds for functions of independent random variables, Ann. Probab., 36 ( 2008 ), pp. 143-159.","journal-title":"Probab."},{"key":"e_1_3_2_1_14_1","first-page":"1","volume-title":"J. ACM, 54 ( 3 ) ( 2007 )","author":"Dinur I.","unstructured":"I. Dinur, The PCP theorem by gap amplification, J. ACM, 54 ( 3 ) ( 2007 ), pp. 1-44."},{"key":"e_1_3_2_1_15_1","volume":"34","author":"Dvo\u0159\u00e1k V.","unstructured":"V. Dvo\u0159\u00e1k, P. van Hintum, and M. Tiba, Improved bound for Tomaszewski's problem, SIAM J. Discret. Math., 34 ( 4 ) ( 2020 ), pp. 2239-2249.","journal-title":"Improved bound for Tomaszewski's problem, SIAM J. Discret. Math."},{"key":"e_1_3_2_1_16_1","volume-title":"Probability mass of Rademacher sums beyond one standard deviation, preprint","author":"Dvo\u0159\u00e1k V.","year":"2021","unstructured":"V. Dvo\u0159\u00e1k and O. Klein, Probability mass of Rademacher sums beyond one standard deviation, preprint, 2021."},{"key":"e_1_3_2_1_17_1","first-page":"403","volume-title":"Lith. Math. J., 54 ( 4 ) ( 2014 )","author":"Dzindzalieta D.","unstructured":"D. Dzindzalieta, A note on random signs, Lith. Math. J., 54 ( 4 ) ( 2014 ), pp. 403-408."},{"key":"e_1_3_2_1_19_1","first-page":"114","volume-title":"Theory Probab. Appl., 65 ( 1 ) ( 2020 )","author":"Dzindzalieta D.","unstructured":"D. Dzindzalieta and F G\u00f6tze, Half-spaces with influential variable, Theory Probab. Appl., 65 ( 1 ) ( 2020 ), pp. 114-120."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177696897"},{"key":"e_1_3_2_1_21_1","first-page":"1278","volume":"64","author":"Efron B.","unstructured":"B. Efron, Student's t-test under symmetry conditions, J. Amer. Statist. Assoc., 64 ( 1969 ), pp. 1278-1302.","journal-title":"J. Amer. Statist. Assoc."},{"key":"e_1_3_2_1_22_1","first-page":"1","volume-title":"Arkiv Mat. Astronom. Fys., A28 ( 1942 )","author":"Esseen C.-G.","unstructured":"C.-G. Esseen, On the Liapunof limit of error in the theory of probability, Arkiv Mat. Astronom. Fys., A28 ( 1942 ), pp. 1-19."},{"key":"e_1_3_2_1_23_1","first-page":"160","volume-title":"Skand. Aktuarietidskr., 39 ( 1956 )","author":"Esseen C.-G.","unstructured":"C.-G. Esseen, A moment inequality with an application to the central limit theorem, Skand. Aktuarietidskr., 39 ( 1956 ), pp. 160-170."},{"key":"e_1_3_2_1_24_1","volume-title":"Real analysis in computer science: A collection of open problems, manuscript","author":"Filmus Y.","year":"2014","unstructured":"Y. Filmus, H. Hatami, S. Heilman, E. Mossel, R. O 'Donnell, S. Sachdeva, A. Wan, and K. Wimmer, Real analysis in computer science: A collection of open problems, manuscript, 2014. Available at https:\/\/simons.berkeley.edu\/sites\/default\/files\/openprobsmerged.pdf."},{"key":"e_1_3_2_1_25_1","first-page":"503","volume-title":"Combinatorica 28 ( 2008 )","author":"Friedgut E.","unstructured":"E. Friedgut, On the measure of intersecting families, uniqueness and stability, Combinatorica 28 ( 2008 ), pp. 503--528."},{"key":"e_1_3_2_1_26_1","first-page":"354","volume-title":"Explicit rates of approximation in the CLT for quadratic forms, Ann. Probab., 42 ( 1 ) ( 2014 )","author":"G\u00f6tze F.","unstructured":"F. G\u00f6tze and A. Yu. Zaitsev, Explicit rates of approximation in the CLT for quadratic forms, Ann. Probab., 42 ( 1 ) ( 2014 ), pp. 354-397."},{"key":"e_1_3_2_1_27_1","first-page":"279","volume-title":"Amer. Math. Monthly, 93 ( 4 ) ( 1986 )","author":"Guy R. K.","unstructured":"R. K. Guy, Any answers anent these analytical enigmas?, Amer. Math. Monthly, 93 ( 4 ) ( 1986 ), pp. 279-281."},{"key":"e_1_3_2_1_28_1","first-page":"1419","volume-title":"Ann. Probab., 32 ( 2 ) ( 2004 )","author":"Hall P.","unstructured":"P. Hall and Q. Wang, Exact convergence rate and leading term in Central Limit Theorem for Student's t statistic, Ann. Probab., 32 ( 2 ) ( 2004 ), pp. 1419-1437."},{"key":"e_1_3_2_1_29_1","volume-title":"Linear combinations of Rademacher random variables","author":"Hendriks H.","year":"2017","unstructured":"H. Hendriks and M. C. A. van Zuijlen, Linear combinations of Rademacher random variables, 2017. Available at: https:\/\/arxiv.org\/pdf\/1703.07251.pdf"},{"key":"e_1_3_2_1_30_1","first-page":"454","volume-title":"A new series of conjectures and open questions in optimization and matrix analysis","author":"Hiriart-Urruty J.-B.","year":"2009","unstructured":"J.-B. Hiriart-Urruty, A new series of conjectures and open questions in optimization and matrix analysis, ESAIM: Control, Optimisation and Calculus of Variations, 15 ( 2 ) ( 2009 ), pp. 454-470."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0253-0_2"},{"key":"e_1_3_2_1_32_1","first-page":"303","volume-title":"Combinatorica, 12 ( 3 ) ( 1992 )","author":"Holzman R.","unstructured":"R. Holzman and D. J. Kleitman, On the product of sign vectors and unit vectors, Combinatorica, 12 ( 3 ) ( 1992 ), pp. 303-316."},{"key":"e_1_3_2_1_33_1","volume-title":"Some Random Series of Functions","author":"Kahane J. P.","year":"1993","unstructured":"J. P. Kahane, Some Random Series of Functions, Cambridge University Press, 1993."},{"key":"e_1_3_2_1_34_1","first-page":"412","volume-title":"Adv. Appl. Math. 29 ( 3 ) ( 2002 )","author":"Kalai G.","unstructured":"G. Kalai, A Fourier-theoretic perspective on the Condorcet paradox and Arrow's theorem, Adv. Appl. Math. 29 ( 3 ) ( 2002 ), pp. 412-426."},{"key":"e_1_3_2_1_35_1","first-page":"1","volume-title":"Discrete Analysis, 2019","author":"Keller N.","year":"2019","unstructured":"N. Keller and O. Klein, Biased halfspaces, noise sensitivity, and relative Chernof inequalities, Discrete Analysis, 2019 : 13 ( 2019 ), pp. 1-50."},{"key":"e_1_3_2_1_36_1","first-page":"2006","author":"Keller N.","year":"2020","unstructured":"N. Keller and O. Klein, Proof of Tomaszewski's Conjecture on Randomly Signed Sums (long version ), 2020. Available at arXiv: 2006.16834.","journal-title":"Proof of Tomaszewski's Conjecture on Randomly Signed Sums (long version )"},{"volume-title":"On the","author":"K\u00f6nig H.","key":"e_1_3_2_1_37_1","unstructured":"H. K\u00f6nig and M. Rudelson, On the volume of non-central sections of a cube, Adv. Math., to appear. Available at https:\/\/arxiv.org\/abs\/ 1908.09358."},{"key":"e_1_3_2_1_38_1","first-page":"638","volume-title":"Theory Probab. Appl., 54 ( 4 ) ( 2010 )","author":"Korolev V. Yu.","unstructured":"V. Yu. Korolev and I. G. Shevtsova, On the upper bound for the absolute constant in the Berry-Esseen inequality, Theory Probab. Appl., 54 ( 4 ) ( 2010 ), pp. 638-658."},{"key":"e_1_3_2_1_39_1","first-page":"727","volume-title":"Trans. Amer. Math. Soc. 370 ( 1 ) ( 2018 )","author":"Mattner L.","unstructured":"L. Mattner and J. Schulz, On normal approximations to symmetric hypergeometric laws, Trans. Amer. Math. Soc. 370 ( 1 ) ( 2018 ), pp. 727-748."},{"key":"e_1_3_2_1_40_1","series-title":"SIAM J. Comput. 39 ( 5 ) ( 2010 )","first-page":"2004","volume-title":"Testing halfspaces","author":"Matulef K.","year":"2009","unstructured":"K. Matulef, R. O 'Donnell, R. Rubinfeld, and R. A. Servedio, Testing halfspaces, SIAM J. Comput. 39 ( 5 ) ( 2010 ), pp. 2004-2047. Extended abstract appeared at SODA' 2009."},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1990-1013975-0"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139814782"},{"key":"e_1_3_2_1_43_1","series-title":"SIAM J. Comput. 40 ( 1 ) ( 2011 )","first-page":"165","volume-title":"The Chow parameters problem","author":"O'Donnell R.","year":"2008","unstructured":"R. O'Donnell and R. A. Servedio, The Chow parameters problem, SIAM J. Comput. 40 ( 1 ) ( 2011 ), pp. 165-199. Extended abstract appeared at STOC' 2008."},{"key":"e_1_3_2_1_44_1","first-page":"127","volume-title":"Probab. Math. Statist., 16 ( 1996 )","author":"Oleszkiewicz K.","unstructured":"K. Oleszkiewicz, On the Stein property of Rademacher sequences, Probab. Math. Statist., 16 ( 1996 ), pp. 127-130."},{"key":"e_1_3_2_1_45_1","first-page":"357","volume":"22","author":"Pinelis I.","unstructured":"I. Pinelis, Extremal probabilistic problems and Hotelling's T 2 test under a symmetry condition, Ann. Statist., 22 ( 1994 ), pp. 357-368.","journal-title":"Ann. Statist."},{"key":"e_1_3_2_1_46_1","first-page":"1","volume-title":"Electron. J. Probab., 17 ( 2012 )","author":"Pinelis I.","unstructured":"I. Pinelis, An asymptotically Gaussian bound on the Rademacher tails, Electron. J. Probab., 17 ( 2012 ), pp. 1-22."},{"key":"e_1_3_2_1_47_1","first-page":"138","volume-title":"Skand. Aktuarietidskr.","author":"Prawitz H.","year":"1972","unstructured":"H. Prawitz, Limits for a distribution, if the characteristic function is given in a ifnite domain, Skand. Aktuarietidskr., 1972(2) ( 1972 ), pp. 138-154."},{"key":"e_1_3_2_1_48_1","volume":"62","author":"Samorodnitsky A.","unstructured":"A. Samorodnitsky, On the entropy of a noisy function, IEEE Trans. Inform. Th. 62 ( 10 ) ( 2016 ), pp. 5446--5464.","journal-title":"Trans. Inform. Th."},{"key":"e_1_3_2_1_49_1","first-page":"26","volume-title":"Refinement of estimates for the rate of convergence in Lyapunov's theorem. Dokl. Akad. Nauk, 435 ( 1 ) ( 2010 )","author":"Shevtsova I. G.","unstructured":"I. G. Shevtsova. Refinement of estimates for the rate of convergence in Lyapunov's theorem. Dokl. Akad. Nauk, 435 ( 1 ) ( 2010 ), pp. 26-28."},{"key":"e_1_3_2_1_50_1","volume-title":"On a sum of centered random variables with nonreducing variances, manuscrupt","author":"Shnurnikov I.","year":"2012","unstructured":"I. Shnurnikov, On a sum of centered random variables with nonreducing variances, manuscrupt, 2012. Available at arXiv: 1202. 2990v2."},{"key":"e_1_3_2_1_51_1","first-page":"1201","volume-title":"proceedings of SODA 2009 conference","author":"C.","unstructured":"A.M.-C. So, Improved approximation bound for quadratic optimization problems with orthogonality constraints, proceedings of SODA 2009 conference, pp. 1201-1209."},{"key":"e_1_3_2_1_52_1","volume-title":"Analysis of Boolean functions-lecture notes from a series of lectures by Ryan O'Donnell","author":"Tan L.-Y.","year":"2012","unstructured":"L.-Y. Tan, Analysis of Boolean functions-lecture notes from a series of lectures by Ryan O'Donnell, 2012. Available at https:\/\/arxiv.org\/abs\/1205.0314."},{"key":"e_1_3_2_1_54_1","volume-title":"On a conjecture concerning the sum of independent Rademacher random variables","author":"van Zuijlen M. C. A.","year":"2011","unstructured":"M. C. A. van Zuijlen, On a conjecture concerning the sum of independent Rademacher random variables, 2011. Available at arXiv: 1112. 4988v1."},{"key":"e_1_3_2_1_55_1","first-page":"231","volume-title":"Colloq. Math., 113 ( 2008 )","author":"Veraar M.","unstructured":"M. Veraar, A note on optimal probability lower bounds for centered random variables, Colloq. Math., 113 ( 2008 ), pp. 231-240."},{"key":"e_1_3_2_1_56_1","volume-title":"Ideas for an old analytic enigma about the sphere that fail in intriguing ways, manuscript","author":"von Heymann F.","year":"2012","unstructured":"F. von Heymann, Ideas for an old analytic enigma about the sphere that fail in intriguing ways, manuscript, 2012. Available at http:\/\/www.mi.unikoeln.de\/opt\/wp-content\/uploads\/2017\/02\/Cube_sphere.pdf."}],"event":{"name":"STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Virtual Italy","acronym":"STOC '21"},"container-title":["Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451011","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451011","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:01:44Z","timestamp":1750197704000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451011"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":54,"alternative-id":["10.1145\/3406325.3451011","10.1145\/3406325"],"URL":"https:\/\/doi.org\/10.1145\/3406325.3451011","relation":{},"subject":[],"published":{"date-parts":[[2021,6,15]]},"assertion":[{"value":"2021-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}