Tensor Network Complexity of Multilinear Maps

by Per Austrin, Petteri Kaski, and Kaie Kubjas

Theory of Computing, Volume 18(16), pp. 1-54, 2022

Bibliography with links to cited articles

[1]   Amir Abboud, Arturs Backurs, Karl Bringmann, and Marvin Künnemann: Fine-grained complexity of analyzing compressed data: Quantifying improvements over decompress-and-solve. In Proc. 58th FOCS, pp. 192–203. IEEE Comp. Soc., 2017. [doi:10.1109/FOCS.2017.26, arXiv:1803.00796]

[2]   Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams: If the current clique algorithms are optimal, so is Valiant’s parser. SIAM J. Comput., 47(6):2527–2555, 2018. Preliminary version in FOCS’15. [doi:10.1137/16M1061771, arXiv:1504.01431]

[3]   Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen, and Toniann Pitassi: Toward a model for backtracking and dynamic programming. Comput. Complexity, 20(4):679–740, 2011. Preliminary version in CCC’05. [doi:10.1007/s00037-011-0028-y, ECCC:TR09-038]

[4]   Josh Alman and Virginia Vassilevska Williams: A refined laser method and faster matrix multiplication. In Proc. 32nd Ann. ACM–SIAM Symp. on Discrete Algorithms (SODA’21), pp. 522–539. SIAM, 2021. [doi:10.1137/1.9781611976465.32, arXiv:2010.05846]

[5]   Noga Alon and Shai Gutner: Balanced families of perfect hash functions and their applications. ACM Trans. Algorithms, 6(3):54:1–12, 2010. Preliminary version in ICALP’07. [doi:10.1145/1798596.1798607, arXiv:0805.4300]

[6]   Noga Alon, Raphael Yuster, and Uri Zwick: Finding and counting given length cycles. Algorithmica, 17(3):209–223, 1997. Preliminary version in ESA’94. [doi:10.1007/BF02523189]

[7]   Itai Arad and Zeph Landau: Quantum computation and the evaluation of tensor networks. SIAM J. Comput., 39(7):3089–3121, 2010. [doi:10.1137/080739379]

[8]   Sanjeev Arora and Boaz Barak: Computational Complexity: A Modern Approach. Cambridge Univ. Press, 2009. [doi:10.1017/CBO9780511804090]

[9]    Per Austrin, Petteri Kaski, and Kaie Kubjas: Tensor network complexity of multilinear maps. In Proc. 9th Innovations in Theoret. Comp. Sci. Conf. (ITCS’18), pp. 7:1–21. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018. [doi:10.4230/LIPIcs.ITCS.2019.7]

[10]   Fahiem Bacchus, Shannon Dalmao, and Toniann Pitassi: Algorithms and complexity results for #SAT and Bayesian inference. In Proc. 44th FOCS, pp. 340–351. IEEE Comp. Soc., 2003. [doi:10.1109/SFCS.2003.1238208]

[11]   Martin Beaudry and Markus Holzer: The complexity of tensor circuit evaluation. Comput. Complexity, 16(1):60–111, 2007. Preliminary version in MFCS’01. [doi:10.1007/s00037-007-0222-0]

[12]   Austin R. Benson and Grey Ballard: A framework for practical parallel fast matrix multiplication. In Proc. 20th SIGPLAN Symp. Principles and Practice of Parallel Programming (PPoPP’15), pp. 42–53. ACM Press, 2015. [doi:10.1145/2688500.2688513, arXiv:1409.2908]

[13]   Stuart J. Berkowitz: On computing the determinant in small parallel time using a small number of processors. Inform. Process. Lett., 18(3):147–150, 1984. [doi:10.1016/0020-0190(84)90018-8]

[14]   Jacob D. Biamonte, Jason Morton, and Jacob Turner: Tensor network contractions for #SAT. J. Stat. Phys., 160(5):1389–1404, 2015. [doi:10.1007/s10955-015-1276-z, arXiv:1405.7375]

[15]   Andreas Björklund: Below all subsets for some permutational counting problems. In Proc. 15th Scand. Symp. Algorithm Theory (SWAT’16), pp. 17:1–11. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2016. [doi:10.4230/LIPIcs.SWAT.2016.17]

[16]   Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto: Fourier meets Möbius: fast subset convolution. In Proc. 39th STOC, pp. 67–74. ACM Press, 2007. [doi:10.1145/1250790.1250801, arXiv:cs/0611101]

[17]   Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto: Computing the Tutte polynomial in vertex-exponential time. In Proc. 49th FOCS, pp. 677–686. IEEE Comp. Soc., 2008. [doi:10.1109/FOCS.2008.40, arXiv:0711.2585]

[18]   Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto: Counting paths and packings in halves. In Proc. 17th Eur. Symp. Algorithms (ESA’09), pp. 578–586. Springer, 2009. [doi:10.1007/978-3-642-04128-0_52, arXiv:0904.3093]

[19]   Andreas Björklund, Thore Husfeldt, and Mikko Koivisto: Set partitioning via inclusion-exclusion. SIAM J. Comput., 39(2):546–563, 2009. [doi:10.1137/070683933]

[20]   Andreas Björklund, Petteri Kaski, and Łukasz Kowalik: Counting thin subgraphs via packings faster than meet-in-the-middle time. ACM Trans. Algorithms, 13(4):48:1–26, 2017. Preliminary version in SODA’14. [doi:10.1145/3125500, arXiv:1306.4111]

[21]   Hans L. Bodlaender, Erik Jan van Leeuwen, Johan M. M. van Rooij, and Martin Vatshelle: Faster algorithms on branch and clique decompositions. In Proc. Internat. Symp. Math. Foundations of Comp. Sci. (MFCS’10), pp. 174–185. Springer, 2010. [doi:10.1007/978-3-642-15155-2_17]

[22]   James R. Bunch and John E. Hopcroft: Triangular factorization and inversion by fast matrix multiplication. Math. Comput., 28(125):231–236, 1974. [doi:10.1090/S0025-5718-1974-0331751-8]

[23]   Peter Bürgisser, Michael Clausen, and M. Amin Shokrollahi: Algebraic Complexity Theory. Springer, 1997. [doi:10.1007/978-3-662-03338-8]

[24]   Jin-Yi Cai, Heng Guo, and Tyson Williams: A complete dichotomy rises from the capture of vanishing signatures. SIAM J. Comput., 45(5):1671–1728, 2016. Preliminary version in STOC’13. [doi:10.1137/15M1049798, arXiv:1204.6445]

[25]   Jin-yi Cai, Pinyan Lu, and Mingji Xia: Computational complexity of Holant problems. SIAM J. Comput., 40(4):1101–1132, 2011. [doi:10.1137/100814585]

[26]   Florent Capelli, Arnaud Durand, and Stefan Mengel: The arithmetic complexity of tensor contraction. Theory Computing Sys., 58(4):506–527, 2016. Preliminary version in STACS’13. [doi:10.1007/s00224-015-9630-8, arXiv:1209.4865]

[27]   Arthur Cayley: On the theory of the analytical forms called trees. The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science, 13(85):172–176, 1857. [doi:10.1080/14786445708642275]

[28]   Arthur Cayley: On the analytical forms called trees, part II. The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science, 18(121):374–378, 1859. [doi:10.1080/14786445908642782]

[29]   Andrzej Cichocki, Namgil Lee, Ivan V. Oseledets, Anh Huy Phan, Qibin Zhao, and Danilo P. Mandic: Tensor networks for dimensionality reduction and large-scale optimization: Part 1 Low-rank tensor decompositions. Found. Trends Mach. Learning, 9(4–5):249–429, 2016. [doi:10.1561/2200000059]

[30]   Andrzej Cichocki, Anh Huy Phan, Qibin Zhao, Namgil Lee, Ivan V. Oseledets, Masashi Sugiyama, and Danilo P. Mandic: Tensor networks for dimensionality reduction and large-scale optimization: Part 2 Applications and future perspectives. Found. Trends Mach. Learning, 9(6):431–673, 2017. [doi:10.1561/2200000067, arXiv:1708.09165]

[31]   Alfred Clebsch: Ueber symbolische Darstellung algebraischer Formen. J. reine angew. Math., 59:1–62, 1861. [doi:10.1515/crll.1861.59.1]

[32]   William K. Clifford: Extract of a letter to Mr. Sylvester from Prof. Clifford of University College, London. Amer. J. Math., 1(2):126–128, 1878. [doi:10.2307/2369303]

[33]   Henry Cohn, Robert D. Kleinberg, Balázs Szegedy, and Christopher Umans: Group-theoretic algorithms for matrix multiplication. In Proc. 46th FOCS, pp. 379–388. IEEE Comp. Soc., 2005. [doi:10.1109/SFCS.2005.39]

[34]   Henry Cohn and Christopher Umans: Fast matrix multiplication using coherent configurations. In Proc. 24th Ann. ACM–SIAM Symp. on Discrete Algorithms (SODA’13), pp. 1074–1087. SIAM, 2013. [doi:10.1137/1.9781611973105.77, arXiv:1207.6528]

[35]   James W. Cooley and John W. Tukey: An algorithm for the machine calculation of complex Fourier series. Math. Comput., 19(90):297–301, 1965. [doi:10.1090/S0025-5718-1965-0178586-1]

[36]   László Csánky: Fast parallel matrix inversion algorithms. SIAM J. Comput., 5(4):618–623, 1976. Preliminary version in FOCS’75. [doi:10.1137/0205040]

[37]   Radu Curticapean, Holger Dell, and Dániel Marx: Homomorphisms are a good basis for counting small subgraphs. In Proc. 49th STOC, pp. 210–223. ACM Press, 2017. [doi:10.1145/3055399.3055502, arXiv:1705.01595]

[38]   Predrag Cvitanović: Group theory for Feynman diagrams in non-Abelian gauge theories. Phys. Rev. D, 14(6):1536–1553, 1976. [doi:10.1103/PhysRevD.14.1536]

[39]   Predrag Cvitanović and Anthony D. Kennedy: Spinors in negative dimensions. Physica Scripta, 26(1):5–14, 1982. [doi:10.1088/0031-8949/26/1/001]

[40]   Carsten Damm, Markus Holzer, and Pierre McKenzie: The complexity of tensor calculus. Comput. Complexity, 11(1–2):54–89, 2002. Preliminary version in CCC’00. [doi:10.1007/s00037-000-0170-4, ECCC:TR00-036]

[41]   Sashka Davis and Russell Impagliazzo: Models of greedy algorithms for graph problems. Algorithmica, 54(3):269–317, 2009. Preliminary version in SODA’04. [doi:10.1007/s00453-007-9124-4, ECCC:TR05-120]

[42]   Josep Díaz, Maria J. Serna, and Dimitrios M. Thilikos: Counting H-colorings of partial k-trees. Theoret. Comput. Sci., 281(1–2):291–309, 2002. Preliminary version in COCOON’01. [doi:10.1016/S0304-3975(02)00017-8]

[43]   Frederic Dorn: Dynamic programming and fast matrix multiplication. In Proc. 14th Eur. Symp. Algorithms (ESA’06), pp. 280–291. Springer, 2006. [doi:10.1007/11841036_27]

[44]   Friedrich Eisenbrand and Fabrizio Grandoni: On the complexity of fixed parameter clique and dominating set. Theoret. Comput. Sci., 326(1–3):57–67, 2004. [doi:10.1016/j.tcs.2004.05.009]

[45]   Peter Floderus, Miroslaw Kowaluk, Andrzej Lingas, and Eva-Marta Lundell: Detecting and counting small pattern graphs. SIAM J. Discr. Math., 29(3):1322–1339, 2015. Preliminary version in ISAAC’13. [doi:10.1137/140978211]

[46]   Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman, Saket Saurabh, and B. V. Raghavendra Rao: Faster algorithms for finding and counting subgraphs. J. Comput. System Sci., 78(3):698–706, 2012. [doi:10.1016/j.jcss.2011.10.001, arXiv:0912.2371]

[47]   William I. Gasarch: The second P =? NP poll. SIGACT News, 43(2):53–77, 2012. [doi:10.1145/2261417.2261434]

[48]   Johan Håstad: Tensor rank is NP-complete. J. Algorithms, 11(4):644–654, 1990. Preliminary version in ICALP’89. [doi:10.1016/0196-6774(90)90014-6]

[49]   Christopher J. Hillar and Lek-Heng Lim: Most tensor problems are NP-hard. J. ACM, 60(6):45:1–39, 2013. [doi:10.1145/2512329, arXiv:0911.1393]

[50]   Jianyu Huang, Leslie Rice, Devin A. Matthews, and Robert A. van de Geijn: Generating families of practical fast matrix multiplication algorithms. In Proc. Internat. Parallel and Distrib. Processing Symp. (IPDPS’17), pp. 656–667. IEEE Comp. Soc., 2017. [doi:10.1109/IPDPS.2017.56, arXiv:1611.01120]

[51]   Russell Impagliazzo and Ramamohan Paturi: On the complexity of k-SAT. J. Comput. System Sci., 62(2):367–375, 2001. [doi:10.1006/jcss.2000.1727]

[52]   Russell Impagliazzo, Ramamohan Paturi, and Francis Zane: Which problems have strongly exponential complexity? J. Comput. System Sci., 63(4):512–530, 2001. Preliminary version in FOCS’98. [doi:10.1006/jcss.2001.1774]

[53]   Alon Itai and Michael Rodeh: Finding a minimum circuit in a graph. SIAM J. Comput., 7(4):413–423, 1978. Preliminary version in STOC’77. [doi:10.1137/0207033]

[54]   Norman P. Jouppi, Cliff Young, Nishant Patil, and David Patterson +72: In-datacenter performance analysis of a tensor processing unit. In Proc. 44th Internat. Symp. Computer Architecture (ISCA’17), pp. 1–12. ACM Press, 2017. [doi:10.1145/3079856.3080246, arXiv:1704.04760]

[55]   Matti Karppa, Petteri Kaski, and Jukka Kohonen: A faster subquadratic algorithm for finding outlier correlations. ACM Trans. Algorithms, 14(3):31:1–26, 2018. Preliminary version in SODA’16. [doi:10.1145/3174804, arXiv:1510.03895]

[56]   Louis H. Kauffman: Knots, abstract tensors and the Yang-Baxter equation. In L. Lussana, editor, Knots, Topology and Quantum Field Theories, pp. 179–334. World Scientific, 1989.

[57]   Alfred Bray Kempe: On the application of Clifford’s graphs to ordinary binary quantics. Proc. London Math. Soc., 17(1):107–123, 1885. [doi:10.1112/plms/s1-17.1.107]

[58]   Alfred Bray Kempe: On the application of the Sylvester–Clifford graphs to ordinary binary quantics. (Second part.). Proc. London Math. Soc., 24(1):97–118, 1892. [doi:10.1112/plms/s1-24.1.97]

[59]   Ton Kloks, Dieter Kratsch, and Haiko Müller: Finding and counting small induced subgraphs efficiently. Inform. Process. Lett., 74(3–4):115–121, 2000. Preliminary version in WG’95. [doi:10.1016/S0020-0190(00)00047-8]

[60]   Tamara Gibson Kolda: Multilinear operators for higher-order decompositions. Technical Report SAND2006-2081, Sandia National Laboratories, 2006. [doi:10.2172/923081]

[61]    Tamara Gibson Kolda and Brett W. Bader: Tensor decompositions and applications. SIAM Rev., 51(3):455–500, 2009. [doi:10.1137/07070111X]

[62]   Daphne Koller and Nir Friedman: Probabilistic Graphical Models. MIT Press, 2009. MIT Press.

[63]   Joseph B. Kruskal: Three-way arrays: rank and uniqueness of trilinear decompositions, with application to arithmetic complexity and statistics. Lin. Alg. Appl., 18(2):95–138, 1977. [doi:10.1016/0024-3795(77)90069-6]

[64]   Greg Kuperberg: Involutory Hopf algebras and 3-manifold invariants. Internat. J. Mathematics, 2(1):41–66, 1991. [doi:10.1142/S0129167X91000053]

[65]   Chi-Chung Lam, P. Sadayappan, and Rephael Wenger: On optimizing a class of multi-dimensional loops with reduction for parallel execution. Parallel Process. Lett., 7(2):157–168, 1997. [doi:10.1142/S0129626497000176]

[66]   Joseph M. Landsberg: Tensors: Geometry and Applications. Amer. Math. Soc., 2012. [doi:10.1090/gsm/128]

[67]   Joseph M. Landsberg, Yang Qi, and Ke Ye: On the geometry of tensor network states. Quantum Inf. Comput., 12(3& 4):346–354, 2012. [doi:10.26421/QIC12.3-4-12]

[68]   François Le Gall: Faster algorithms for rectangular matrix multiplication. In Proc. 53rd FOCS, pp. 514–523. IEEE Comp. Soc., 2012. [doi:10.1109/FOCS.2012.80, arXiv:1204.1111]

[69]   François Le Gall: Powers of tensors and fast matrix multiplication. In Proc. 39th Internat. Symp. Symbolic and Algebraic Computation (ISSAC’14), pp. 296–303. ACM Press, 2014. [doi:10.1145/2608628.2608664, arXiv:1401.7714]

[70]   François Le Gall and Florent Urrutia: Improved rectangular matrix multiplication using powers of the Coppersmith-Winograd tensor. In Proc. 29th Ann. ACM–SIAM Symp. on Discrete Algorithms (SODA’18), pp. 1029–1046. SIAM, 2018. [doi:10.1137/1.9781611975031.67, arXiv:1708.05622]

[71]   James R. Lee, Prasad Raghavendra, and David Steurer: Lower bounds on the size of semidefinite programming relaxations. In Proc. 47th STOC, pp. 567–576. ACM Press, 2015. [doi:10.1145/2746539.2746599, arXiv:1411.6317]

[72]   Andrea Lincoln, Virginia Vassilevska Williams, and R. Ryan Williams: Tight hardness for shortest cycles and paths in sparse graphs. In Proc. 29th Ann. ACM–SIAM Symp. on Discrete Algorithms (SODA’18), pp. 1236–1252. SIAM, 2018. [doi:10.1137/1.9781611975031.80, arXiv:1712.08147]

[73]   Stefano Markidis, Steven Wei Der Chien, Erwin Laure, Ivy Bo Peng, and Jeffrey S. Vetter: NVIDIA tensor core programmability, performance & precision. In Proc. Internat. Parallel and Distrib. Processing Symp. (IPDPS’18), pp. 522–531. IEEE Comp. Soc., 2018. [doi:10.1109/IPDPSW.2018.00091, arXiv:1803.04014]

[74]   Ankur Moitra and Alexander S. Wein: Spectral methods from tensor networks. In Proc. 51st STOC, pp. 926–937. ACM Press, 2019. [doi:10.1145/3313276.3316357, arXiv:1811.00944]

[75]   Jarik Nešetřil and Svatopluk Poljak: On the complexity of the subgraph problem. Commentationes Mathematicae Universitatis Carolinae, 26(2):415–419, 1985. EuDML.

[76]   Noam Nisan: Lower bounds for non-commutative computation (extended abstract). In Proc. 23rd STOC, pp. 410–418. ACM Press, 1991. [doi:10.1145/103418.103462]

[77]   Stephan Olariu: Paw-free graphs. Inform. Process. Lett., 28(1):53–54, 1988. [doi:10.1016/0020-0190(88)90143-3]

[78]   Román Orús: A practical introduction to tensor networks: Matrix product states and projected entangled pair states. Ann. Phys., 349:117–158, 2014. [doi:10.1016/j.aop.2014.06.013, arXiv:1306.2164]

[79]   Victor Y. Pan: Matrix multiplication, trilinear decompositions, APA algorithms, and summation, 2014. [arXiv:1412.1145]

[80]   Roger Penrose: Tensor Methods in Algebraic Geometry. Ph. D. thesis, St. John’s College, 1956.

[81]   Roger Penrose: Applications of negative dimensional tensors. In D. J. A. Welsh, editor, Combinatorial Mathematics and its Applications, pp. 221–244. Academic Press, 1971. LINK.

[82]   Roger Penrose and Wolfgang Rindler: Spinors and space-time. Vol. 1. Cambridge Univ. Press, 1984. [doi:10.1017/CBO9780511564048]

[83]   Robert N. C. Pfeifer, Jutho Haegeman, and Frank Verstraete: Faster identification of optimal contraction sequences for tensor networks. Phys. Rev. E, 90(3), 2014. [doi:10.1103/PhysRevE.90.033315]

[84]   Ran Raz: Tensor-rank and lower bounds for arithmetic formulas. J. ACM, 60(6):40:1–15, 2013. Preliminary version in STOC’10. [doi:10.1145/2535928, ECCC:TR10-002]

[85]   Jürgen Richter-Gebert and Peter Lebmeir: Diagrams, tensors and geometric reasoning. Discr. Comput. Geom., 42(2):305–334, 2009. [doi:10.1007/s00454-009-9188-9]

[86]   Neil Robertson and Paul D. Seymour: Graph minors. X. Obstructions to tree-decomposition. J. Combin. Theory–B, 52(2):153–190, 1991. [doi:10.1016/0095-8956(91)90061-N]

[87]   Elina Robeva and Anna Seigal: Duality of graphical models and tensor networks. Inf. Inference, 8(2):273–288, 2018. [doi:10.1093/imaiai/iay009, arXiv:1710.01437]

[88]   Günter Rote: Division-free algorithms for the determinant and the Pfaffian: Algebraic and combinatorial approaches. In Helmut Alt, editor, Computational Discrete Mathematics, Advanced Lectures, pp. 119–135. Springer, 2001. [doi:10.1007/3-540-45506-X_9]

[89]   Herbert John Ryser: Combinatorial Mathematics. Amer. Math. Soc., 1963.

[90]   Alexander Schrijver: On traces of tensor representations of diagrams. Lin. Alg. Appl., 476:28–41, 2015. [doi:10.1016/j.laa.2015.02.037]

[91]   Edgar Solomonik and Torsten Hoefler: Sparse tensor algebra as a parallel programming model, 2015. [arXiv:1512.00066]

[92]   Edgar Solomonik, Devin Matthews, Jeff R. Hammond, John F. Stanton, and James Demmel: A massively parallel tensor contraction framework for coupled-cluster computations. J. Parallel Distrib. Comput., 74(12):3176–3190, 2014. [doi:10.1016/j.jpdc.2014.06.002]

[93]   Volker Strassen: Gaussian elimination is not optimal. Numerische Mathematik, 13(4):354–356, 1969. [doi:10.1007/BF02165411]

[94]   James J. Sylvester: On an application of the new atomic theory to the graphical representation of the invariants and covariants of binary quantics, with three appendices. Amer. J. Math., 1(1):64–104, 1878. [doi:10.2307/2369436]

[95]   Leslie G. Valiant: The complexity of computing the permanent. Theoret. Comput. Sci., 8(2):189–201, 1979. [doi:10.1016/0304-3975(79)90044-6]

[96]   Leslie G. Valiant: Holographic algorithms. SIAM J. Comput., 37(5):1565–1594, 2008. Preliminary version in FOCS’04. [doi:10.1137/070682575, ECCC:TR05-099]

[97]   Charles Van Loan: Computational Frameworks for the Fast Fourier Transform. SIAM, 1992. [doi:10.1137/1.9781611970999]

[98]   Virginia Vassilevska Williams: Multiplying matrices faster than Coppersmith–Winograd. In Proc. 44th STOC, pp. 887–898. ACM Press, 2012. [doi:10.1145/2213977.2214056]

[99]   Virginia Vassilevska Williams, Joshua R. Wang, R. Ryan Williams, and Huacheng Yu: Finding four-node subgraphs in triangle time. In Proc. 26th Ann. ACM–SIAM Symp. on Discrete Algorithms (SODA’15), pp. 1671–1680. SIAM, 2015. [doi:10.1137/1.9781611973730.111]

[100]   Virginia Vassilevska Williams and R. Ryan Williams: Finding, minimizing, and counting weighted subgraphs. SIAM J. Comput., 42(3):831–854, 2013. Preliminary version in STOC’09. [doi:10.1137/09076619X]

[101]   Martin J. Wainwright and Michael I. Jordan: Graphical models, exponential families, and variational inference. Found. Trends Mach. Learning, 1(1–2):1–305, 2008. [doi:10.1561/2200000001]

[102]   R. Ryan Williams: A new algorithm for optimal 2-constraint satisfaction and its implications. Theoret. Comput. Sci., 348(2–3):357–365, 2005. Preliminary version in ICALP’04. [doi:10.1016/j.tcs.2005.09.023]

[103]   R. Ryan Williams: Faster all-pairs shortest paths via circuit complexity. SIAM J. Comput., 47(5):1965–1985, 2018. Preliminary version in STOC’14. [doi:10.1137/15M1024524]

[104]   Frank Yates: The Design and Analysis of Factorial Experiments. Imperial Bureau of Soil Science, 1937. Rothamsted Repository.