{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,27]],"date-time":"2026-04-27T19:26:20Z","timestamp":1777317980455,"version":"3.51.4"},"publisher-location":"New York, NY, USA","reference-count":40,"publisher":"ACM","license":[{"start":{"date-parts":[[2018,6,20]],"date-time":"2018-06-20T00:00:00Z","timestamp":1529452800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2018,6,20]]},"DOI":"10.1145\/3188745.3188890","type":"proceedings-article","created":{"date-parts":[[2018,6,20]],"date-time":"2018-06-20T20:15:46Z","timestamp":1529525746000},"page":"1102-1114","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["A matrix expander Chernoff bound"],"prefix":"10.1145","author":[{"given":"Ankit","family":"Garg","sequence":"first","affiliation":[{"name":"Microsoft Research, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yin Tat","family":"Lee","sequence":"additional","affiliation":[{"name":"University of Washington, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhao","family":"Song","sequence":"additional","affiliation":[{"name":"Harvard University, USA \/ University of Texas at Austin, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nikhil","family":"Srivastava","sequence":"additional","affiliation":[{"name":"University of California at Berkeley, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,6,20]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.985947"},{"key":"e_1_3_2_2_2_1","unstructured":"Rajendra Bhatia. 1997.  Rajendra Bhatia. 1997."},{"key":"e_1_3_2_2_3_1","volume-title":"Springer Science &amp","author":"Vol Matrix","unstructured":"Matrix analysis. Vol . 169. Springer Science &amp ; Business Media . Matrix analysis. Vol. 169. Springer Science & Business Media."},{"key":"e_1_3_2_2_4_1","unstructured":"Herman Chernoff. 1952.  Herman Chernoff. 1952."},{"key":"e_1_3_2_2_5_1","volume-title":"The Annals of Mathematical Statistics","author":"A","year":"1952","unstructured":"A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. The Annals of Mathematical Statistics ( 1952 ), 493\u2013507. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. The Annals of Mathematical Statistics (1952), 493\u2013507."},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2006.10129115"},{"key":"e_1_3_2_2_7_1","unstructured":"Kai-min Chung Henry Lam Zhenming Liu and Michael Mitzenmacher. 2012.  Kai-min Chung Henry Lam Zhenming Liu and Michael Mitzenmacher. 2012."},{"key":"e_1_3_2_2_8_1","volume-title":"arXiv preprint arXiv:1201.0559","author":"Markov Chains Chernoff-Hoeffding","year":"2012","unstructured":"Chernoff-Hoeffding Bounds for Markov Chains : Generalized and Simplified. arXiv preprint arXiv:1201.0559 ( 2012 ). Chernoff-Hoeffding Bounds for Markov Chains: Generalized and Simplified. arXiv preprint arXiv:1201.0559 (2012)."},{"key":"e_1_3_2_2_9_1","unstructured":"John B. Conway. 1978.  John B. Conway. 1978."},{"key":"e_1_3_2_2_10_1","volume-title":"Graduate Texts in Mathematics","author":"Complex Variable Functions","unstructured":"Functions of one Complex Variable . Graduate Texts in Mathematics ( Second Edition), Vol. I . Springer New York , Heidelberg, Berlin . Functions of one Complex Variable. Graduate Texts in Mathematics (Second Edition), Vol. I. Springer New York, Heidelberg, Berlin."},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794268765"},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRev.137.B1127"},{"key":"e_1_3_2_2_13_1","unstructured":"Loukas Grafakos. 2008.  Loukas Grafakos. 2008."},{"key":"e_1_3_2_2_14_1","volume-title":"Graduate Texts in Mathematics","author":"Analysis Classical Fourier","unstructured":"Classical Fourier Analysis . Graduate Texts in Mathematics , Vol. 249 . Springer New York . Classical Fourier Analysis. Graduate Texts in Mathematics, Vol. 249. Springer New York."},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-007-0238-5"},{"key":"e_1_3_2_2_16_1","unstructured":"Fumio Hiai Robert Koenig and Marco Tomamichel. 2016.  Fumio Hiai Robert Koenig and Marco Tomamichel. 2016."},{"key":"e_1_3_2_2_17_1","volume-title":"arXiv preprint arXiv:1609.01999 (Sept","author":"Log-Majorization Generalized","year":"2016","unstructured":"Generalized Log-Majorization and Multivariate Trace Inequalities . arXiv preprint arXiv:1609.01999 (Sept . 2016 ). arXiv: math-ph\/1609.01999 Generalized Log-Majorization and Multivariate Trace Inequalities. arXiv preprint arXiv:1609.01999 (Sept. 2016). arXiv: math-ph\/1609.01999"},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548397003209"},{"key":"e_1_3_2_2_19_1","unstructured":"Michel Ledoux and Michel Talagrand. 2013.  Michel Ledoux and Michel Talagrand. 2013."},{"key":"e_1_3_2_2_20_1","volume-title":"isoperimetry and processes","author":"Banach Spaces Probability","unstructured":"Probability in Banach Spaces : isoperimetry and processes . Springer Science & amp; Business Media. Probability in Banach Spaces: isoperimetry and processes. Springer Science & Business Media."},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1214\/105051604000000170"},{"key":"e_1_3_2_2_22_1","volume-title":"Chernoff-type bound for finite Markov chains. Annals of Applied Probability","author":"Lezaud Pascal","year":"1998","unstructured":"Pascal Lezaud . 1998. Chernoff-type bound for finite Markov chains. Annals of Applied Probability ( 1998 ), 849\u2013867. Pascal Lezaud. 1998. Chernoff-type bound for finite Markov chains. Annals of Applied Probability (1998), 849\u2013867."},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02126799"},{"key":"e_1_3_2_2_24_1","unstructured":"Assaf Naor Yuval Peres Oded Schramm Scott Sheffield etal 2006.  Assaf Naor Yuval Peres Oded Schramm Scott Sheffield et al. 2006."},{"key":"e_1_3_2_2_25_1","volume-title":"Duke Mathematical Journal 134, 1","author":"Markov","year":"2006","unstructured":"Markov chains in smooth Banach spaces and Gromov-hyperbolic metric spaces. Duke Mathematical Journal 134, 1 ( 2006 ), 165\u2013197. Markov chains in smooth Banach spaces and Gromov-hyperbolic metric spaces. Duke Mathematical Journal 134, 1 (2006), 165\u2013197."},{"key":"e_1_3_2_2_26_1","volume-title":"A Sharp Tail Bound for the Expander Random Sampler. arXiv preprint arXiv:1703.10205","author":"Rao Shravas","year":"2017","unstructured":"Shravas Rao and Oded Regev . 2017. A Sharp Tail Bound for the Expander Random Sampler. arXiv preprint arXiv:1703.10205 ( 2017 ). Shravas Rao and Oded Regev. 2017. A Sharp Tail Bound for the Expander Random Sampler. arXiv preprint arXiv:1703.10205 (2017)."},{"key":"e_1_3_2_2_27_1","unstructured":"Omer Reingold Salil Vadhan and Avi Wigderson. 2000.  Omer Reingold Salil Vadhan and Avi Wigderson. 2000."},{"key":"e_1_3_2_2_28_1","volume-title":"Foundations of Computer Science, 2000. Proceedings. 41st Annual Symposium on. IEEE, 3\u201313","author":"Entropy","unstructured":"Entropy waves , the zig-zag graph product, and new constant-degree expanders and extractors . In Foundations of Computer Science, 2000. Proceedings. 41st Annual Symposium on. IEEE, 3\u201313 . Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors. In Foundations of Computer Science, 2000. Proceedings. 41st Annual Symposium on. IEEE, 3\u201313."},{"key":"e_1_3_2_2_29_1","unstructured":"Mark Rudelson. 1999.  Mark Rudelson. 1999."},{"key":"e_1_3_2_2_30_1","volume-title":"Journal of Functional Analysis 164, 1","author":"Random","year":"1999","unstructured":"Random vectors in the isotropic position. Journal of Functional Analysis 164, 1 ( 1999 ), 60\u201372. Random vectors in the isotropic position. Journal of Functional Analysis 164, 1 (1999), 60\u201372."},{"key":"e_1_3_2_2_31_1","unstructured":"David Sutter Mario Berta and Marco Tomamichel. 2017.  David Sutter Mario Berta and Marco Tomamichel. 2017."},{"key":"e_1_3_2_2_32_1","volume-title":"Communications in Mathematical Physics 352, 1","author":"Inequalities Multivariate Trace","year":"2017","unstructured":"Multivariate Trace Inequalities . Communications in Mathematical Physics 352, 1 ( 2017 ), 37\u201358. 016- 2778- 5 arXiv:1604.03023. Multivariate Trace Inequalities. Communications in Mathematical Physics 352, 1 (2017), 37\u201358. 016- 2778- 5 arXiv:1604.03023."},{"key":"e_1_3_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1063\/1.1704727"},{"key":"e_1_3_2_2_34_1","unstructured":"Joel A Tropp. 2012.  Joel A Tropp. 2012."},{"key":"e_1_3_2_2_35_1","volume-title":"Foundations of computational mathematics 12, 4","year":"2012","unstructured":"User-friendly tail bounds for sums of random matrices. Foundations of computational mathematics 12, 4 ( 2012 ), 389\u2013434. User-friendly tail bounds for sums of random matrices. Foundations of computational mathematics 12, 4 (2012), 389\u2013434."},{"key":"e_1_3_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1561\/2200000048"},{"key":"e_1_3_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548307008772"},{"key":"e_1_3_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.8"},{"key":"e_1_3_2_2_39_1","unstructured":"Avi Wigderson and David Xiao. 2006.  Avi Wigderson and David Xiao. 2006."},{"key":"e_1_3_2_2_40_1","unstructured":"Retraction of Wigderson-Xiao: A randomness-efficient sampler for matrix valued functions eccc tr05-107. (2006).  Retraction of Wigderson-Xiao: A randomness-efficient sampler for matrix valued functions eccc tr05-107. (2006)."}],"event":{"name":"STOC '18: Symposium on Theory of Computing","location":"Los Angeles CA USA","acronym":"STOC '18","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3188745.3188890","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3188745.3188890","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:07:10Z","timestamp":1750212430000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3188745.3188890"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,20]]},"references-count":40,"alternative-id":["10.1145\/3188745.3188890","10.1145\/3188745"],"URL":"https:\/\/doi.org\/10.1145\/3188745.3188890","relation":{},"subject":[],"published":{"date-parts":[[2018,6,20]]},"assertion":[{"value":"2018-06-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}