{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T13:53:51Z","timestamp":1773237231236,"version":"3.50.1"},"reference-count":19,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2016,6,7]],"date-time":"2016-06-07T00:00:00Z","timestamp":1465257600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2017,7]]},"abstract":"<jats:p>We study the distribution of products of conjugacy classes in finite simple groups, obtaining effective two-step mixing results, which give rise to an approximation to a conjecture of Thompson.<\/jats:p><jats:p>Our results, combined with work of Gowers and Viola, also lead to the solution of recent conjectures they posed on interleaved products and related complexity lower bounds, extending their work on the groups SL(2,<jats:italic>q<\/jats:italic>) to all (non-abelian) finite simple groups.<\/jats:p><jats:p>In particular it follows that, if<jats:italic>G<\/jats:italic>is a finite simple group, and<jats:italic>A<\/jats:italic>,<jats:italic>B<\/jats:italic>\u2286<jats:italic>G<jats:sup>t<\/jats:sup><\/jats:italic>for<jats:italic>t<\/jats:italic>\u2a7e 2 are subsets of fixed positive densities, then, as<jats:italic>a<\/jats:italic>= (<jats:italic>a<\/jats:italic><jats:sub>1<\/jats:sub>, .\u00a0.\u00a0.,<jats:italic>a<jats:sub>t<\/jats:sub><\/jats:italic>) \u2208<jats:italic>A<\/jats:italic>and<jats:italic>b<\/jats:italic>= (<jats:italic>b<\/jats:italic><jats:sub>1<\/jats:sub>, .\u00a0.\u00a0.,<jats:italic>b<jats:sub>t<\/jats:sub><\/jats:italic>) \u2208<jats:italic>B<\/jats:italic>are chosen uniformly, the interleaved product<jats:italic>a<\/jats:italic>\u2022<jats:italic>b<\/jats:italic>:=<jats:italic>a<\/jats:italic><jats:sub>1<\/jats:sub><jats:italic>b<\/jats:italic><jats:sub>1<\/jats:sub>.\u00a0.\u00a0.<jats:italic>a<jats:sub>t<\/jats:sub>b<jats:sub>t<\/jats:sub><\/jats:italic>is almost uniform on<jats:italic>G<\/jats:italic>(with quantitative estimates) with respect to the \u2113<jats:sub>\u221e<\/jats:sub>-norm.<\/jats:p><jats:p>It also follows that the communication complexity of an old decision problem related to interleaved products of<jats:italic>a<\/jats:italic>,<jats:italic>b<\/jats:italic>\u2208<jats:italic>G<jats:sup>t<\/jats:sup><\/jats:italic>is at least \u03a9(<jats:italic>t<\/jats:italic>log |<jats:italic>G<\/jats:italic>|) when<jats:italic>G<\/jats:italic>is a finite simple group of Lie type of bounded rank, and at least \u03a9(<jats:italic>t<\/jats:italic>log log |<jats:italic>G<\/jats:italic>|) when<jats:italic>G<\/jats:italic>is any finite simple group. Both these bounds are best possible.<\/jats:p>","DOI":"10.1017\/s096354831600016x","type":"journal-article","created":{"date-parts":[[2016,6,7]],"date-time":"2016-06-07T07:56:46Z","timestamp":1465286206000},"page":"628-640","source":"Crossref","is-referenced-by-count":4,"title":["Mixing, Communication Complexity and Conjectures of Gowers and Viola"],"prefix":"10.1017","volume":"26","author":[{"given":"ANER","family":"SHALEV","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2016,6,7]]},"reference":[{"key":"S096354831600016X_ref17","doi-asserted-by":"crossref","unstructured":"Miles E. and Viola E. (2013) Shielding circuits with groups. In Proc. 45th Annual ACM Symposium on the Theory of Computing: STOC, pp. 251\u2013260.","DOI":"10.1145\/2488608.2488640"},{"key":"S096354831600016X_ref3","volume-title":"Methods of Representation Theory","author":"Curtis","year":"1981"},{"key":"S096354831600016X_ref5","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(84)80056-X"},{"key":"S096354831600016X_ref8","doi-asserted-by":"crossref","unstructured":"Gowers W. T. and Viola E. (2015) The communication complexity of interleaved group products. In Proc. 47th Annual ACM Symposium on the Theory of Computing: STOC, pp. 351\u2013360.","DOI":"10.1145\/2746539.2746560"},{"key":"S096354831600016X_ref7","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548307008826"},{"key":"S096354831600016X_ref11","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-2011-00709-1"},{"key":"S096354831600016X_ref13","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2011.174.3.10"},{"key":"S096354831600016X_ref6","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-2012-05427-4"},{"key":"S096354831600016X_ref9","doi-asserted-by":"crossref","unstructured":"Gowers W. T. and Viola E. (2015) The communication complexity of interleaved group products. Electronic Colloquium on Computational Complexity, report 44, revision 1.","DOI":"10.1145\/2746539.2746560"},{"key":"S096354831600016X_ref15","doi-asserted-by":"publisher","DOI":"10.1007\/s00222-004-0390-3"},{"key":"S096354831600016X_ref10","doi-asserted-by":"crossref","unstructured":"Guralnick R. M. and L\u00fcbeck F. (2001) On p-singular elements in Chevalley groups in characteristic p. In Groups and Computation III: Proc. International Conference at the Ohio State University, 1999, Vol. 8 of Ohio State Univ. Math. Res. Inst. Publ., de Gruyter, pp. 169\u2013182.","DOI":"10.1515\/9783110872743.169"},{"key":"S096354831600016X_ref19","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2009.170.1383"},{"key":"S096354831600016X_ref2","unstructured":"Babai L. , Nikolov N. and Pyber L. (2008) Product growth and mixing in finite groups. In Proc. 19th Annual ACM\u2013SIAM Symposium on Discrete Algorithms: SODA, pp. 248\u2013257."},{"key":"S096354831600016X_ref18","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgebra.2007.07.031"},{"key":"S096354831600016X_ref4","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-98-01953-9"},{"key":"S096354831600016X_ref12","doi-asserted-by":"publisher","DOI":"10.1016\/0021-8693(74)90150-1"},{"key":"S096354831600016X_ref16","doi-asserted-by":"publisher","DOI":"10.1112\/S0024611504014935"},{"key":"S096354831600016X_ref14","doi-asserted-by":"publisher","DOI":"10.1016\/S0021-8693(03)00515-5"},{"key":"S096354831600016X_ref1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0072284"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S096354831600016X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,1]],"date-time":"2022-07-01T04:39:12Z","timestamp":1656650352000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S096354831600016X\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,6,7]]},"references-count":19,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,7]]}},"alternative-id":["S096354831600016X"],"URL":"https:\/\/doi.org\/10.1017\/s096354831600016x","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,6,7]]}}}