On Linear-Algebraic Notions of Expansion
by Yinan Li, Youming Qiao, Avi Wigderson, Yuval Wigderson, and Chuanqi Zhang
Theory of Computing, Volume 21(1), pp. 1-28, 2025
Bibliography with links to cited articles
[1] Noga Alon: Eigenvalues and expanders. Combinatorica, 6(2):83–96, 1986. [doi:10.1007/BF02579166]
[2] Noga Alon and Vitali D. Milman: λ1, isoperimetric inequalities for graphs and superconcentrators. J. Combin. Theory–B, 38(1):73–88, 1985. [doi:10.1016/0095-8956(85)90092-9]
[3] Tom Bannink, Jop Briët, Farrokh Labib, and Hans Maassen: Quasirandom quantum channels. Quantum, 4:298 (1–18), 2020. [doi:10.22331/q-2020-07-16-298]
[4] Boaz Barak, Russell Impagliazzo, Amir Shpilka, and Avi Wigderson: Definition and existence of dimension expanders. Discussion (no written record), 2004.
[5] Avraham Ben-Aroya, Oded Schwartz, and Amnon Ta-Shma: Quantum expanders: Motivation and constructions. Theory of Computing, 6(3):47–79, 2010. [doi:10.4086/toc.2010.v006a003]
[6] Avraham Ben-Aroya and Amnon Ta-Shma: Quantum expanders and the quantum entropy difference problem, 2007. [arXiv:quant-ph/0702129]
[7] Jean Bourgain: Expanders and dimensional expansion. C. R. Math. Acad. Sci. Paris, 347(7–8):357–362, 2009. [doi:10.1016/j.crma.2009.02.009]
[8] Jean Bourgain and Amir Yehudayoff: Expansion in SL2(R) and monotone expanders. Geom. Funct. Anal. (GAFA), 23(1):1–41, 2013. [doi:10.1007/s00039-012-0200-9]
[9] Jeff Cheeger: A lower bound for the smallest eigenvalue of the Laplacian. In Problems in analysis (Sympos. in honor of Salomon Bochner, 1969), pp. 195–199. Princeton Univ. Press, 1971. [doi:10.1515/9781400869312-013]
[10] Ralph Cohen: The topology of fiber bundles. Unpublished lecture notes, available online at https://math.stanford.edu/~ralph/fiber.pdf, 1998.
[11] Jozef Dodziuk: Difference equations, isoperimetric inequality and transience of certain random walks. Trans. AMS, 284(2):787–794, 1984. [doi:10.2307/1999107]
[12] Zeev Dvir and Amir Shpilka: Towards dimension expanders over finite fields. Combinatorica, 31(3):305–320, 2011. [doi:10.1007/s00493-011-2540-8]
[13] Zeev Dvir and Avi Wigderson: Monotone expanders: Constructions and applications. Theory of Computing, 6(12):291–308, 2010. [doi:10.4086/toc.2010.v006a012]
[14] Michael A. Forbes and Venkatesan Guruswami: Dimension expanders via rank condensers. In Proc. 19th Internat. Workshop on Randomization and Computation (RANDOM’15), pp. 800–814. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2015. [doi:10.4230/LIPIcs.APPROX-RANDOM.2015.800]
[15] William Cole Franks and Ankur Moitra: Rigorous guarantees for Tyler’s M-estimator via quantum expansion. In Proc. 33rd Ann. Conf. on Learning Theory (COLT’20), pp. 1601–1632. MLR Press, 2020. PMLR.
[16] Ankit Garg, Leonid Gurvits, Rafael M. Oliveira, and Avi Wigderson: Operator scaling: Theory and applications. Found. Computational Math., 20(2):223–290, 2020. [doi:10.1007/s10208-019-09417-z]
[17] Jonathan L. Gross: Every connected regular graph of even degree is a Schreier coset graph. J. Combin. Theory–B, 22(3):227–232, 1977. [doi:10.1016/0095-8956(77)90068-5]
[18] Leonid Gurvits: Classical complexity and quantum entanglement. J. Comput. System Sci., 69(3):448–484, 2004. [doi:10.1016/j.jcss.2004.06.003]
[19] Joe Harris: Algebraic Geometry: A First Course. Springer, 1995. [doi:10.1007/978-1-4757-2189-8]
[20] Aram W. Harrow: Quantum expanders from any classical Cayley graph expander. Quantum Inf. Comput., 8(8–9):715–721, 2008. [doi:10.26421/QIC8.8-9-2]
[21] Matthew B. Hastings: Entropy and entanglement in quantum ground states. Phys. Rev. B, 76(3):035114, 2007. [doi:10.1103/PhysRevB.76.035114]
[22] Matthew B. Hastings: Random unitaries give quantum expanders. Phys. Rev. A (3), 76(3):032315, 2007. [doi:10.1103/PhysRevA.76.032315]
[23] Matthew B. Hastings and Aram W. Harrow: Classical and quantum tensor product expanders. Quantum Inf. Comput., 9(3–4):336–360, 2009. [doi:10.26421/QIC9.3-4-9]
[24] Shlomo Hoory, Nathan Linial, and Avi Wigderson: Expander graphs and their applications. Bull. AMS, 43(4):439–561, 2006. [doi:10.1090/S0273-0979-06-01126-8]
[25] Ivan Kolář, Peter W. Michor, and Jan Slovák: Natural Operations in Differential Geometry. Springer, 1993. [doi:10.1007/978-3-662-02950-3]
[26] Tsz Chiu Kwok, Lap Chi Lau, and Akshay Ramachandran: Spectral analysis of matrix scaling and operator scaling. SIAM J. Comput., 50(3):1034–1102, 2021. [doi:10.1137/20M1315981]
[27] Yinan Li, Youming Qiao, Avi Wigderson, Yuval Wigderson, and Chuanqi Zhang: Connections between graphs and matrix spaces. Israel J. Math., 256(2):513–580, 2023. [doi:10.1007/s11856-023-2515-7]
[28] Alexander Lubotzky: Discrete Groups, Expanding Graphs and Invariant Measures. Volume 125 of Progress in Mathematics. Birkhäuser Verlag, Basel, 1994. [doi:10.1007/978-3-0346-0332-4]
[29] Alexander Lubotzky and Efim Zelmanov: Dimension expanders. J. Algebraic Geom., 319(2):730–738, 2008. [doi:10.1016/j.jalgebra.2005.12.033]
[30] Jiří Matoušek: On embedding expanders into ℓp spaces. Israel J. Math., 102(3):189–197, 1997. [doi:10.1007/BF02773799]
[31] Roy Meshulam and Avi Wigderson: Expanders in group algebras. Combinatorica, 24(4):659–680, 2004. [doi:10.1007/s00493-004-0040-9]
[32] Michael A. Nielsen and Isaac L. Chuang: Quantum Computation and Quantum Information. Cambridge Univ. Press, 2000. [doi:10.1017/CBO9780511976667]
[33] Pranab Sen: Efficient quantum tensor product expanders and unitary t-designs via the zigzag product. 2018. [arXiv:1808.10521]
[34] Kristan Temme, Michael J. Kastoryano, Mary Beth Ruskai, Michael M. Wolf, and Frank Verstraete: The χ2-divergence and mixing times of quantum Markov processes. J. Math. Phys., 51(12):122201, 19, 2010. [doi:10.1063/1.3511335]