Publications

Technical Reports (under review or unpublished)

• Quasitubal Tensor Algebra Over Separable Hilbert Spaces
  Uria Mor, Haim Avron

• Higher Order Reduced Rank Regression
  Leia Greenberg, Haim Avron
  

• Hutchinson’s Estimator is Bad at Kronecker-Trace-Estimation
  Raphael A. Meyer, Haim Avron
  

• Manifold Free Riemannian Optimization
  Boris Shustin, Haim Avron, Barak Sober
  

• PCENet: High Dimensional Surrogate Modeling for Learning Uncertainty
  Paz Fink Shustin, Shashanka Ubaru, Vasileios Kalantzis, Lior Horesh, Haim Avron
  

• Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees
  Haim Avron, Michael Kapralov, Cameron Musco, Christopher Musco, Ameya Velingker, Amir Zandieh
  (short version appeared in ICML 2017)
  

• On the Role of Initialization on the Implicit Bias in Deep Linear Networks
  Oria Guber, Haim Avron
  

• Multi-Function Multi-Way Analog Technology for Sustainable Machine Intelligence Computation
  Vassilis Kalantzis, Mark S. Squillante, Shashanka Ubaru, Tayfun Gokmen, Chai Wah Wu, Anshul Gupta, Haim Avron, Tomasz Nowicki, Malte Rasch, Murat Onen, Vanessa Lopez Marrero, Effendi Leobandung, Yasuteru Kohda, Wilfried Haensch, Lior Horesh

2025

• Multivariate Trace Estimation Using Quantum State Space Linear Algebra
  Liron Mor Yosef, Shashanka Ubaru, Lior Horesh, Haim Avron
  SIAM Journal on Matrix Analysis and Applications, 46 (1), 2025

2024

• Faster Randomized Methods for Orthogonality Constrained Problems
  Boris Shustin, Haim Avron
  Journal of Machine Learning Research, 25(257):1−59, 2024
  

• Stable Tensor Neural Networks for Rapid Deep Learning
  Elizabeth Newman, Lior Horesh, Haim Avron, Misha Kilmer
  Frontiers in Big Data, Sec. Data Science, Volume 7, 2024

• Low-Rank Updates of Matrix Square Roots
  Shany Shmueli, Petros Drineas, Haim Avron
  Numerical Linear Algebra with Applications, 31:e2528, 2024

2023

• Near Optimal Reconstruction of Spherical Harmonic Expansions
  Amir Zandieh, Insu Han, Haim Avron
  Advances in Neural Information Processing Systems (NeurIPS), 2023
  

• Experimental Design for Overparameterized Learning with Application to Single Shot Deep Active Learning
  Neta Shoham, Haim Avron
  IEEE Transactions on Pattern Analysis and Machine Intelligence, Volume 45, 2023

• Solving Trust Region Subproblems Using Riemannian Optimization
  Uria Mor, Boris Shustin, Haim Avron
  Numerische Mathematik 154, 1-33, 2023

• Riemannian Optimization with a Preconditioning Scheme on the Generalized Stiefel Manifold
  Boris Shustin, Haim Avron
  Journal of Computational and Applied Mathematics, Volume 423, 2023

• Quasi Monte Carlo Time-Frequency Analysis
  Ron Levie, Haim Avron, Gitta Kutyniok
  Journal of Mathematical Analysis and Applications, 518 (2), 2023

2022

• Faster Randomized Infeasible Interior Point Methods for Tall/Wide Linear Programs
  Agniva Chowdhury, Gregory Dexter, Palma London, Haim Avron, Petros Drineas
  Journal of Machine Learning Research, 23(336) , 2022
  (short version appeared in NeurIPS 2020)

• Dimensionality Reduction of Longitudinal 'Omics Data using Modern Tensor Factorizations
  Uria Mor, Yotam Cohen, Rafael Valdes-Mas, Denise Kviatcovsky, Eran Elinav, Haim Avron
  PLOS Computational Biology, 18(7): e1010212, 2022
  Software Implementation
  

• Random Gegenbauer Features for Scalable Kernel Methods
  Insu Han, Amir Zandieh, Haim Avron
  International Conference on Machine Learning (ICML), 2022
  

• On the Convergence of Inexact Predictor-Corrector Methods for Linear Programming
  Gregory Dexter, Agniva Chowdhury, Haim Avron, Petros Drineas
  International Conference on Machine Learning (ICML), 2022
  

• Randomized Continuous Frames in Time-Frequency Analysis
  Ron Levie, Haim Avron
  Advances in Computational Mathematics, 48:25, 2022
  

• Gauss-Legendre Features for Gaussian Process Regression
  Paz Fink Shustin, Haim Avron
  Journal of Machine Learning Research, 23(92):1-47, 2022
  

• Semi-Infinite Linear Regression and Its Applications
  Paz Fink Shustin, Haim Avron
  SIAM Journal on Matrix Analysis and Applications, 43 (1), 2022
  

2021

• Randomized Signal Processing with Continuous Frames
  Ron Levie, Haim Avron
  Journal of Fourier Analysis and Applications, 28 (5), 2021
  

• Scaling Neural Tangent Kernels via Sketching and Random Features
  Amir Zandieh, Insu Han, Haim Avron, Neta Shoham, Chaewon Kim, Jinwoo Shin
  Advances in Neural Information Processing Systems (NeurIPS), 2021
  

• Tensor-Tensor Algebra for Optimal Representation and Compression of Multiway Data
  Misha Kilmer, Lior Horesh, Haim Avron, Elizabeth Newman
  Proceedings of the National Academy of Sciences, 118 (28), 2021
  SIAM Activity Group on Computational Science and Engineering Best Paper Prize 2025
  

• Dynamic Graph Convolutional Networks Using the Tensor M-Product
  Osman Malik, Shashanka Ubaru, Lior Horesh, Misha Kilmer, Haim Avron
  SIAM International Conference on Data Mining (SDM), 2021
  

• Solving Sparse Linear Systems with Approximate Inverse Preconditioners on Analog Devices
  V. Kalantzis, A. Gupta, L. Horesh, T. Nowicki, M. S. Squillante, C. W. Wu, T. Gokmen, and H. Avron
  IEEE Conference on High Performance Extreme Computing (HPEC), 2021
  

• Flexible GMRES with Analog Accelerators
  A. Gupta, V. Kalantzis, M. S. Squillante, C. W. Wu, H. Avron, S. Ubaru, T. Gokmen, M. Rasche, T. Nowicki, L. Horesh
  Poster in Supercomputing (SC), 2021, 2 pages

2020

• Faster Randomized Infeasible Interior Point Methods for Tall/Wide Linear Programs
  Agniva Chowdhury, Palma London, Haim Avron, Petros Drineas
  Advances in Neural Information Processing Systems (NeurIPS), 2020
  

• Polynomial Tensor Sketch for Element-wise Functions of Low-Rank Matrices
  Insu Han, Haim Avron, Jinwoo Shin
  International Conference on Machine Learning (ICML), 2020
  

2019

• A Universal Sampling Method for Reconstructing Signals with Simple Fourier Transforms
  Haim Avron, Michael Kapralov, Cameron Musco, Christopher Musco, Ameya Velingker, Amir Zandieh
  ACM Symposium on the Theory of Computing (STOC), 2019
  (conferece proceedings version)

• Sketching for Principal Component Regression
  Liron Mor-Yosef, Haim Avron
  SIAM Journal on Matrix Analysis and Applications, 40 (2), 2019
  

• Spectral Condition-Number Estimation of Large Sparse Matrices
  Haim Avron, Alex Druinsky, Sivan Toledo
  Numerical Linear Algebra with Applications, 26 (3), 2019
  

• A Scalable Randomized Least Squares Solver for Terabyte-sized Dense Overdetermined Systems
  Chander Iyer, Haim Avron, Georgios Kollias, Yves Ineichen, Christopher Carothers, Petros Drineas
  Journal of Computational Science, Volume 36, 2019
  

2018

• Stochastic Chebyshev Gradient Descent for Spectral Optimization
  Insu Han, Haim Avron, Jinwoo Shin
  Advances in Neural Information Processing Systems (NeurIPS), 2018

• Experimental Design for Non-Parametric Correction of Misspecified Dynamical Models
  Gal Shulkind, Lior Horesh, Haim Avron
  SIAM/ASA Journal on Uncertainty Quantification, 6 (2), 2018
  

2017

• Faster Kernel Ridge Regression Using Sketching and Preconditioning
  Haim Avron, Kenneth Clarkson, David Woodruff
  SIAM Journal on Matrix Analysis and Applications, 38 (4), 2017
  

• Sharper Bounds for Regularized Data Fitting
  Haim Avron, Kenneth Clarkson, David Woodruff
  International Workshop on Randomization and Computation (RANDOM), 2017
  

• Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees
  Haim Avron, Michael Kapralov, Cameron Musco, Christopher Musco, Ameya Velingker, Amir Zandieh
  International Conference on Machine Learning (ICML), 2017
  

• Hierarchically Compositional Kernels for Scalable Nonparametric Learning
  Jie Chen, Haim Avron, Vikas Sindhwani
  Journal of Machine Learning Research, 18 (66), 2017
  

• Approximating Spectral Sums of Large-scale Matrices using Chebyshev Approximations
  Insu Han, Dmitry Malioutov, Haim Avron, Jinwoo Shin
  SIAM Journal on Scientific Computing, 39 (4), 2017
  

• Should You Derive, Or Let the Data Drive? An Optimization Framework for Hybrid First-Principles Data-Driven Modeling
  Remi R. Lam, Lior Horesh, Haim Avron, Karen E. Willcox

2016

• Quasi-Monte Carlo Feature Maps for Shift-Invariant Kernels
  Haim Avron, Vikas Sindhwani, Jiyan Yang, Michael Mahoney
  Journal of Machine Learning Research, 17(120):1-38, 2016
  (short version appeared in ICML 2014)
  

• High-performance Kernel Machines with Implicit Distributed Optimization and Randomization
  Haim Avron and Vikas Sindhwani
  Technometrics, 58 (3) (special issue on Big Data), 2016
  

2015

• Revisiting Asynchronous Linear Solvers: Provable Convergence Rate Through Randomization
  Haim Avron, Alex Druinsky, Anshul Gupta
  Journal of the ACM, 62 (6):51, 2015
  (short version appeared in IPDPS 2014)
  

• Community Detection Using Time-Dependent Personalized PageRank
  Haim Avron and Lior Horesh
  International Conference on Machine Learning (ICML), 2015
  

• A Scalable Randomized Least Squares Solver for Dense Overdetermined Systems
  Chander Iyer, Haim Avron, Georgios Kollias, Yves Ineichen, Christopher Carothers, Petros Drineas
  Workshop on Latest Advances in Scalable Algorithms for Large-Scale Systems (ScalA), 2015
  

• libSkylark: A Framework for High-Performance Matrix Sketching for Statistical Computing
  Georgios Kollias, Yves Ineichen, Haim Avron, Vikas Sindhwani, Ken Clarkson, Costas Bekas, Alessandro Curioni
  Supercomputing (SC) 2015 (Poster)

2014

• Efficient Dimensionality Reduction for Canonical Correlation Analysis
  Haim Avron, Christos Boutsidis, Sivan Toledo, Anastasios Zouzias
  SIAM Journal on Scientific Computing, 36 (5), 2014
  (short version appeared in ICML 2013)
  

• Quasi-Monte Carlo Feature Maps for Shift-Invariant Kernels
  Jiyan Yang, Vikas Sindhwani, Haim Avron, Michael Mahoney
  International Conference on Machine Learning (ICML), 2014
  

• Subspace Embedding for the Polynomial Kernel
  Haim Avron, Huy Nguyen and David Woodruff
  Advances in Neural Information Processing Systems (NIPS), 2014

• Revisiting Asynchronous Linear Solvers: Provable Convergence Rate Through Randomization
  Haim Avron, Alex Druinsky, Anshul Gupta
  International Symposium on Parallel & Distributed Processing (IPDPS), 2014
  

• Random Laplace Feature Maps for Semigroup Kernels on Histograms
  Jiyan Yang, Vikas Sindhwani, Quanfu Fan, Haim Avron and Michael Mahoney
  Conference on Computer Vision and Pattern Recognition (CVPR), 2014
  

• Kernel Methods Match Deep Neural Networks on TIMIT
  Po-Sen Huang, Haim Avron, Tara N. Sainath, Vikas Sindhwani, Bhuvana. Ramabhadran
  International Conference on Acoustics, Speech, and Signal Processing (ICASSP), 2014
  

2013

• Faster Subset Selection for Matrices and Applications
  Haim Avron and Christos Boutsidis
  SIAM Journal on Matrix Analysis and Applications, 34 (4), 2013
  

• Solving Hermitian Positive Definite Systems using Indefinite Incomplete Factorizations
  Haim Avron, Anshul Gupta, Sivan Toledo
  Journal of Computational and Applied Mathematics, 243, 2013

• Sketching Structured Matrices for Faster Nonlinear Regression
  Haim Avron, Vikas Sindhwani, David Woodruff
  Advances in Neural Information Processing Systems (NIPS), 2013
  

• Efficient Dimensionality Reduction for Canonical Correlation Analysis
  Haim Avron, Christos Boutsidis, Sivan Toledo, Anastasios Zouzias
  International Conference on Machine Learning (ICML), 2013
  

2012

• Managing Data-Movement for Effective Shared-Memory Parallelization of Out-of-Core Sparse Solvers
  Haim Avron and Anshul Gupta
  Supercomputing (SC) 2015
  

• Efficient and Practical Stochastic Subgradient Descent for Nuclear Norm Regularization
  Haim Avron, Satyen Kale, Shiva Kasiviswanathan, Vikas Sidhwani
  International Conference on Machine Learning (ICML), 2012
  

• Combinatorial Preconditioners
  Sivan Toledo and Haim Avron
  Book Chapter. Combinatorial Scientific Computing, Uwe Naumann (ed.) and Olaf Schenk (ed.)
  Chapman and Hall/CRC Computational Science Series
  

2011

• Randomized Algorithms for Estimating the Trace of an Implicit Symmetric Positive Definite Matrix
  Haim Avron and Sivan Toledo
  Journal of the ACM, 58 (2):8, 2011
  

• Effective Stiffness: Generalizing Effective Resistance Sampling to Finite Element Matrices
  Haim Avron and Sivan Toledo
  

2010

• Advanced Algorithmic Techniques in Numerical Linear Algebra: Hybridization and Randomization
  Haim Avron
  Ph.D. Dissertation - Tel Aviv University
  

• L1-Sparse Reconstruction of Sharp Point Set Surfaces
  Haim Avron, Andrei Sharf, Chen Greif, Danny Cohen-Or
  ACM Transactions on Graphics, 29 (5): 135, 2010
  

• Blendnpik: Supercharging LAPACK's Least-Squares Solver
  Haim Avron, Petar Maymounkov, Sivan Toledo
  SIAM Journal on Scientific Computing, 32 (3), 2010
  

• Counting Triangles in Large Graphs using Randomized Matrix Trace Estimation
  Haim Avron
  KDD Workshop on Large-Scale Data Mining: Theory and Applications, 2010
  

2009

• Using Perturbed QR Factorizations to Solve Linear Least-Squares Problems
  Haim Avron, Esmond Ng, Sivan Toledo
  SIAM Journal on Matrix Analysis and Applications, 31 (2), 2009
  

• Combinatorial Preconditioners for Scalar Elliptic Finite-Elements Problems
  Haim Avron, Doron Chen, Gil Shklarski, Sivan Toledo
  SIAM Journal on Matrix Analysis and Applications, 31 (2), 2009
  

• PFunc: Modern Task Parallelism For Modern High Performance Computing
  Prabhanjan Kambadur, Anshul Gupta, Amol Ghoting, Haim Avron, Andrew Lumsdaine
  Supercomputing (SC), 2009
  

2008

• Parallel Unsymmetric-Pattern Multifrontal Sparse LU with Column Preordering
  Haim Avron, Gil Shklarski, Sivan Toledo
  ACM Transactions on Mathematical Software, 34 (2), 2008
  

• A Generalized Courant-Fischer Minimax Theorem
  Haim Avron, Esmond Ng, Sivan Toledo
  Lawrence Berkeley National Laboratory Technical Report, LBNL-6393E, 2008