{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T10:59:28Z","timestamp":1758279568754,"version":"3.41.0"},"reference-count":21,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2012,8,27]],"date-time":"2012-08-27T00:00:00Z","timestamp":1346025600000},"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":["SIGACT News"],"published-print":{"date-parts":[[2012,8,27]]},"abstract":"<jats:p>This text is meant to be an introduction to a recent strategy introduced by Bourgain and Gamburd (following a work of Helfgott) for proving graph-expansion. The strategy is designed for graphs H that are defined using some underlying group G.<\/jats:p>\n          <jats:p>The strategy consists of three steps, which, in Sarnak's terminology, correspond to the three steps of a chess game: opening, middle-game and endgame. In the opening, the objective is to prove that the girth of H is logarithmic. In the middle-game, the goal is to prove a productgrowth theorem for subsets of G. The endgame consists of establishing a \"mixing property\" for G. There are two methods for proving a mixing property: using pairwise independence and using basic representation theory.<\/jats:p>","DOI":"10.1145\/2421096.2421115","type":"journal-article","created":{"date-parts":[[2013,1,2]],"date-time":"2013-01-02T13:23:15Z","timestamp":1357132995000},"page":"67-84","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Proving expansion in three steps"],"prefix":"10.1145","volume":"43","author":[{"given":"Amir","family":"Yehudayoff","sequence":"first","affiliation":[{"name":"Technion-IIT, Haifa, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,8,27]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"248","volume-title":"SODA","author":"Babai L.","year":"2008"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"J. Bourgain and A. Gamburd On the spectral gap for finitely-generated subgroups of SU(2) Inventiones Mathematicae 171 (1) pages 83--121 2007.  J. Bourgain and A. Gamburd On the spectral gap for finitely-generated subgroups of SU(2) Inventiones Mathematicae 171 (1) pages 83--121 2007.","DOI":"10.1007\/s00222-007-0072-z"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2008.167.625"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214073"},{"key":"e_1_2_1_5_1","unstructured":"E. Breuillard B. Green and T. Tao The structure of approximate groups arXiv:1110.5008 2011.  E. Breuillard B. Green and T. Tao The structure of approximate groups arXiv:1110.5008 2011."},{"key":"e_1_2_1_6_1","unstructured":"G. Davidoff P. Sarnak and A. Valette Elementary number theory group theory and Ramanujan graphs London Mathematical Society Student Texts (No. 55).  G. Davidoff P. Sarnak and A. Valette Elementary number theory group theory and Ramanujan graphs London Mathematical Society Student Texts (No. 55)."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/2011679.2011685"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(81)90040-4"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548307008826"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"H. A. Helfgott Growth and generation in SL2(Z\/pZ) Annals of Mathematics 167 (2) pages 601--623 2008.  H. A. Helfgott Growth and generation in SL2(Z\/pZ) Annals of Mathematics 167 (2) pages 601--623 2008.","DOI":"10.4007\/annals.2008.167.601"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-06-01126-8"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1959-0109367-6"},{"key":"e_1_2_1_13_1","first-page":"155","volume-title":"London Math. Soc. Lecture Note Ser. 18","author":"Lubotzky A.","year":"1995"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02126799"},{"key":"e_1_2_1_15_1","unstructured":"G. A. Margulis Explicit constructions of expanders Problemy Peredaci Informacii 9 (4) pages 71--80 1973.  G. A. Margulis Explicit constructions of expanders Problemy Peredaci Informacii 9 (4) pages 71--80 1973."},{"key":"e_1_2_1_16_1","unstructured":"L. Pyber and E. Szabo Growth in finite simple groups of Lie type of bounded rank arXiv:1005.1858 2010.  L. Pyber and E. Szabo Growth in finite simple groups of Lie type of bounded rank arXiv:1005.1858 2010."},{"issue":"1","key":"e_1_2_1_17_1","first-page":"157","volume":"155","author":"Reingold O.","year":"2002","journal-title":"Entropy waves, the zig-zag graph product, and new constant-degree expanders, Annals of Mathematics"},{"key":"e_1_2_1_18_1","unstructured":"P. Sarnak Notes on thin groups Notes prepared for MSRI hot topics workshop on super-strong approximations 2012.  P. Sarnak Notes on thin groups Notes prepared for MSRI hot topics workshop on super-strong approximations 2012."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1215\/S0012-7094-91-06410-0"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-9458-7"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-008-2271-7"}],"container-title":["ACM SIGACT News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2421096.2421115","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2421096.2421115","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:18:34Z","timestamp":1750234714000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2421096.2421115"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,8,27]]},"references-count":21,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2012,8,27]]}},"alternative-id":["10.1145\/2421096.2421115"],"URL":"https:\/\/doi.org\/10.1145\/2421096.2421115","relation":{},"ISSN":["0163-5700"],"issn-type":[{"type":"print","value":"0163-5700"}],"subject":[],"published":{"date-parts":[[2012,8,27]]},"assertion":[{"value":"2012-08-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}