[1]   Ahmed Alaoui and Michael W. Mahoney: Fast randomized kernel ridge regression with statistical guarantees. In Adv. Neural Info. Proc. Sys. 30 (NIPS’15), pp. 775–783. Curran Assoc., Inc., 2015. NIPS. [arXiv:1411.0306]

[2]   Joshua Batson, Daniel A. Spielman, and Nikhil Srivastava: Twice-Ramanujan sparsifiers. SIAM J. Comput., 41(6):1704–1721, 2012. Preliminary version in STOC’09. [doi:10.1137/090772873, arXiv:0808.0163]

[3]   Antoine Bordes and Léon Bottou: The huller: a simple and efficient online SVM. In Machine Learning: ECML’05, pp. 505–512. Springer, 2005. [doi:10.1007/11564096_48]

[4]   Christos Boutsidis, Dan Garber, Zohar Karnin, and Edo Liberty: Online principal components analysis. In Proc. 26th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’15), pp. 887–901. ACM Press, 2015. [doi:10.1137/1.9781611973730.61]

[5]   Christos Boutsidis and David P. Woodruff: Optimal CUR matrix decompositions. SIAM J. Comput., 46(2):543–589, 2017. Preliminary version in STOC’14. [arXiv:1405.7910]

[6]   Vladimir Braverman, Petros Drineas, Cameron Musco, Christopher Musco, Jalaj Upadhyay, David P. Woodruff, and Samson Zhou: Numerical linear algebra in the online and sliding window models. In Proc. 61st FOCS, pp. 517–528. IEEE Comp. Soc., 2020. [doi:10.1109/FOCS46700.2020.00055, arXiv:1805.03765]

[7]   Daniele Calandriello, Alessandro Lazaric, and Michal Valko: Efficient second-order online kernel learning with adaptive embedding. In Adv. Neural Info. Proc. Sys. 30 (NIPS’17), pp. 6140–6150. Curran Assoc., Inc., 2017. NIPS.

[8]   Daniele Calandriello, Alessandro Lazaric, and Michal Valko: Second-order kernel online convex optimization with adaptive sketching. In Proc. 34th Int. Conf. on Machine Learning (ICML’17), pp. 645–653, 2017. MLR Press. [arXiv:1706.04892]

[9]   Kenneth L. Clarkson and David P. Woodruff: Low rank approximation and regression in input sparsity time. J. ACM, 63(6):54:1–54:45, 2017. Preliminary version in in STOC’13. [doi:10.1145/3019134, arXiv:1207.6365]

[10]   Michael B. Cohen, Sam Elder, Cameron Musco, Christopher Musco, and Madalina Persu: Dimensionality reduction for k-means clustering and low rank approximation. In Proc. 47th STOC, pp. 163–172. ACM Press, 2015. [doi:10.1145/2746539.2746569, arXiv:1410.6801]

[11]   Michael B. Cohen, Yin Tat Lee, Cameron Musco, Christopher Musco, Richard Peng, and Aaron Sidford: Uniform sampling for matrix approximation. In Proc. 6th Innovations in Theoret. Comp. Sci. conf. (ITCS’15), pp. 181–190. ACM Press, 2015. [doi:10.1145/2688073.2688113, arXiv:1408.5099]

[12]   Michael B. Cohen, Cameron Musco, and Christopher Musco: Input sparsity time low-rank approximation via ridge leverage score sampling. In Proc. 28th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’17), pp. 1758–1777. ACM Press, 2017. [doi:10.1137/1.9781611974782.115, arXiv:1511.07263]

[13]   Michael B. Cohen, Cameron Musco, and Jakub Pachocki: Online row sampling. In Proc 19th Internat. Workshop on Approximation Algorithms for Combinat. Opt. Probl. (APPROX’16), pp. 7:1–7:18. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2016. [doi:10.4230/LIPIcs.APPROX-RANDOM.2016.7]

[14]   Koby Crammer, Ofer Dekel, Joseph Keshet, Shai Shalev-Shwartz, and Yoram Singer: Online passive-aggressive algorithms. J. Mach. Learning Res., 7:551–585, 2006. JMLR.

[15]   Michael Kapralov, Yin Tat Lee, Cameron Musco, Christopher Musco, and Aaron Sidford: Single pass spectral sparsification in dynamic streams. SIAM J. Comput., 46(1):456–477, 2017. Preliminary version in in FOCS’14. [doi:10.1137/141002281, arXiv:1407.1289]

[16]   Jonathan A. Kelner and Alex Levin: Spectral sparsification in the semi-streaming setting. Theory Comput. Sys., 53(2):243–262, 2013. [doi:10.1007/s00224-012-9396-1]

[17]   Ioannis Koutis, Gary L. Miller, and Richard Peng: Approaching optimality for solving SDD linear systems. SIAM J. Comput., 43(1):337–354, 2014. Preliminary version in in FOCS’10. [doi:10.1137/110845914, arXiv:1003.2958]

[18]   Rasmus Kyng, Jakub Pachocki, Richard Peng, and Sushant Sachdeva: A framework for analyzing resparsification algorithms. In Proc. 28th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’17), pp. 2032–2043. ACM Press, 2017. [doi:10.1137/1.9781611974782.132, arXiv:1611.06940]

[19]   Yin Tat Lee and He Sun: Constructing linear-sized spectral sparsification in almost-linear time. SIAM J. Comput., 47(6):2315–2336, 2018. Preliminary version in in FOCS’15. [doi:10.1137/16M1061850, arXiv:1508.03261]

[20]   Mu Li, Gary L. Miller, and Richard Peng: Iterative row sampling. In Proc. 54th FOCS, pp. 127–136. IEEE Comp. Soc., 2013. [doi:10.1109/FOCS.2013.22, arXiv:1211.2713]

[21]   Edo Liberty, Ram Sriharsha, and Maxim Sviridenko: An algorithm for online k-means clustering. In Proc. 18th Workshop on Algorithm Engineering and Experiments (ALENEX’16), pp. 81–89, 2016. [doi:10.1137/1.9781611974317.7, arXiv:1412.5721]

[22]   Xiangrui Meng and Michael W. Mahoney: Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression. In Proc. 45th STOC, pp. 91–100. ACM Press, 2013. [doi:10.1145/2488608.2488621, arXiv:1210.3135]

[23]   Jelani Nelson and Huy Lê Nguy n: OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings. In Proc. 54th FOCS, pp. 117–126. IEEE Comp. Soc., 2013. [doi:10.1109/FOCS.2013.21, arXiv:1211.1002]

[24]   Jack Sherman and Winifred J. Morrison: Adjustment of an inverse matrix corresponding to a change in one element of a given matrix. Ann. Math. Stat., 21(1):124–127, 1950. JSTOR.

[25]   Daniel A. Spielman and Nikhil Srivastava: Graph sparsification by effective resistances. SIAM J. Comput., 40(6):1913–1926, 2011. Preliminary version in in STOC’08. [doi:10.1137/080734029, arXiv:0803.0929]

[26]   Daniel A. Spielman and Shang-Hua Teng: Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In Proc. 36th STOC, pp. 81–90. ACM Press, 2004. [doi:10.1145/1007352.1007372, arXiv:cs/0310051]

[27]   Daniel A. Spielman and Shang-Hua Teng: Nearly linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems. SIAM J. Matrix Anal. Appl., 35(3):835–885, 2014. [doi:10.1137/090771430]

[28]   Joel A. Tropp: Freedman’s inequality for matrix martingales. Electr. Comm. Probability, 16(25):262–270, 2011. [doi:10.1214/ECP.v16-1624, arXiv:1101.3039]