Publications

2026

Group-Algebraic Tensors: Provably-optimal Equivariant Learning and Physical Symmetry Discovery
P. Hoyos, S. Ubaru, D. Huh, V. Kalantzis, K. L. Clarkson, M. Kilmer, H. Avron, and L. Horesh, 2026
[ arXiv]
Interpretable epistemic uncertainty decomposition in sequential generative models via polynomial chaos surrogates
R. Kaluarachchi, S. Ubaru, M. Zimon, D. Huh, R. Sawko, L. Horesh, and Y. Bengio, 2026
[ arXiv]
AVSAD: Automating Vector Symbolic Architecture Discovery with Iterative Evolution
D. Scott, D. Zubarev, M. Esposito, A. Shinnar, A. Rahimi, K. L. Clarkson, L. Horesh, M. Hersche, and S. Ubaru
ICLR Workshop on Logical Reasoning of Large Language Models, 2026.
[ Link]
PCENet: High Dimensional Surrogate Modeling for Learning Uncertainty
P.F. Shustin, S. Ubaru, M. Zimon, S. Lu, V. Kalantzis, L. Horesh, and H. Avron
SIAM/ASA Journal on Uncertainty Quantification (JUQ), 14 (1), 168-196, 2026.
[ arXiv, Link]

2025

Advances in Analog Architectures and Randomized Algorithms: Computational and Energy Efficiencies
V. Kalantzis, M. S. Squillante, S. Ubaru, T. Gokmen, H. Avron, W. Haensch, L. Horesh, et al.
ACM Computing Surveys, accepted, 2025.
[ arXiv]
Quantifying policy uncertainty in generative flow networks with uncertain rewards
R. Kaluarachchi, R. Sawko, S. Ubaru, D. Huh, M. Zimon, and L. Horesh
NeurIPS Workshop MLxOR, 2025.
[ Link ]
Capacity Analysis of Vector Symbolic Architectures
K. L. Clarkson, S. Ubaru, and E. Yang
Journal of Artificial Intelligence Research (JAIR), accepted, 2025.
[ arXiv]
Transformers Learn Faster with Semantic Focus
P. Ram, K.L. Clarkson, T. Klinger, S. Ubaru, and A. Gray
Advances in Neural Information Processing Systems (NeurIPS), 2025.
[ arXiv]
Comparing quantum and classical Monte Carlo algorithms for estimating Betti numbers of clique complexes
I. Y. Akhalwaya, A. Bhayat, A. Connolly, S. Herbert, L. Horesh, J. Sorci, and S. Ubaru
Quantum Journal, 9, 1901, 2025.
[ arXiv, Link]
Iterative Solution of Sparse Linear Systems on Hybrid Architectures Using Homomorphic Encryption
L. Horesh, V. Kalantzis, B. Trager, and S. Ubaru
IEEE High Performance Extreme Computing Conference, 2025.
[ Link]
Power iteration with probabilistic updates for systems with heterogeneous performance
S. Ghosh, L. Horesh, V. Kalantzis, G. Kollias, Y. Lu, T. Nowicki, and S. Ubaru
IEEE High Performance Extreme Computing Conference, 2025.
[ Link]
On Eﬃcient Solutions of General Structured Markov Processes in Quantum Computational Environments
V. Kalantzis, M. S. Squillante, and S. Ubaru
IFIP Performance Conference, 2025.
[ arXiv]
Combinatorial Multi-armed Bandits: Arm Selection via Group Testing
A. Mukherjee, S. Ubaru, K. Murugesan, K. Shanmugam, and A. Tajer
Transactions on Machine Learning Research (TMLR), 2025.
[ arXiv, Link]
Randomized matrix-free quadrature: unified and uniform bounds for stochastic Lanczos quadrature and the kernel polynomial method
T. Chen, T. Trogdon, and S. Ubaru
SIAM Journal on Scientific Computing (SISC), 47 (3), A1733-A1757, 2025.
[ arXiv, Link]
Single-Pass Top-N Subgraph Centrality of Graphs via Subspace Projections
V. Kalantzis, G. Kollias, S. Ubaru, N. Abe, and L. Horesh
Journal of Complex Networks, 13 (1), cnae049, 2025.
[ Link]
Multivariate trace estimation using quantum state space linear algebra
L. M. Yosef, S. Ubaru, L. Horesh, and H. Avron
SIAM Journal on Matrix Analysis and Applications (SIMAX), 46(1), 172–209, 2025.
[ arXiv, Link]

2024

Counting Triangles of Graphs via Matrix Partitioning
G. Kollias, V. Kalantzis, L. Horesh, S. Ubaru, and P. Traganitis
IEEE International Workshop on Machine Learning for Signal Processing (MLSP) 2024.
[ Link]
Asynchronous Randomized Trace Estimation
V. Kalantzis, S. Ubaru, C. W. Wu, G. Kollias, and L. Horesh
International Conference on Artificial Intelligence and Statistics (AISTATS), 2024.
[ Link]
Topological Data Analysis on Noisy Quantum Computers
I. Akhalwaya^*, S. Ubaru^*, K. L. Clarkson, M. Squillante, V. Jejjala, Y.H. He, K. Naidoo, V. Kalantzis, and L. Horesh
International Conference on Learning Representations (ICLR), 2024
[ arXiv] *(Oral presentation, 1.2% of submissions)*

2023

Solving Sparse Linear Systems via Flexible GMRES with In-Memory Analog Preconditioning
V. Kalantzis, M. Squillante, C.W. Wu, A. Gupta, S. Ubaru, T. Gokmen, and L. Horesh
IEEE High Performance Extreme Computing Conference, 2023.
[ Link]
Accelerating matrix trace estimation by Aitken’s Δ2 process
V. Kalantzis, G. Kollias, S. Ubaru, and T. Salonidis
International Conference on Acoustics, Speech, and Signal Processing (ICASSP), 2023.
[ Link]
Quantum Graph Transformers
G. Kollias, V. Kalantzis, T. Salonidis, and S. Ubaru
International Conference on Acoustics, Speech, and Signal Processing (ICASSP), 2023.
[ Link]

2022

On Quantum Algorithms for Random Walks in the Nonnegative Quarter Plane
V. Kalantzis, M. S. Squillante, S. Ubaru, and L. Horesh.
Workshop on Mathematical performance Modeling and Analysis (MAMA), 2022.
[ Link]
Representation of the Fermionic Boundary Operator
I.Y. Akhalwaya, Y.H. He, L. Horesh, V. Jejjala, W. Kirby, K. Naidoo, and S. Ubaru.
Physical Review A, volume 106, 022407, 2022.
[ PRA, arXiv]

2021

Quantum Topological Data Analysis with Linear Depth and Exponential Speedup
S. Ubaru, I. Akhalwaya, M. Squillante, K. Clarkson, and L. Horesh, 2021.
[ arXiv]
Dynamic graph and polynomial chaos based models for contact tracing data analysis and optimal testing prescription
S. Ubaru, L. Horesh, and G. Cohen
Journal of Biomedical Informatics (JBI), Special Issue on Novel Informatics Approaches to COVID-19 Research, Volume 122, 103901, 2021. [ Link, arXiv]
Efficient Scaling of Dynamic Graph Neural Networks.
V. Chakaravarthy, S. Pandian, S. Raje, Y. Sabharwal, T. Suzumura, and S. Ubaru
Supercomputing (SC21), 2021.
[ arXiv]
Analysis of stochastic Lanczos quadrature for spectrum approximation
Tyler Chen, Thomas Trogdon, and S. Ubaru
International Conference on Machine Learning (ICML), 2021.
[ arXiv]
Projection techniques to update the truncated SVD of evolving matrices
V. Kalantzis, G. Kollias, S. Ubaru, A. Nikolakopoulos, L. Horesh, and K.L. Clarkson
International Conference on Machine Learning (ICML), 2021.
[ arXiv]
Sparse graph based sketching for fast numerical linear algebra
D. Hu, S. Ubaru, A. Gittens, K.L. Clarkson, L. Horesh, and V. Kalantzis
International Conference on Acoustics, Speech, and Signal Processing (ICASSP), 2021.
[ arXiv]
Dynamic Graph Convolutional Networks Using the Tensor M-Product
O. Malik, S. Ubaru, L. Horesh, M. Kilmer, and H. Avron
SIAM International Conference on Data Mining (SDM), 2021.
[ arXiv]

2020

Spectrum-Adapted Polynomial Approximation for Matrix Functions with Applications in Graph Signal Processing
L. Fan, D. Shuman, S. Ubaru, and Y. Saad,
Algorithms, Special Issue : Efficient Graph Algorithms in Machine Learning, 13(11), 295; 2020.
[ Link]
Multilabel Classification by Hierarchical Partitioning and Data-dependent Grouping
S. Ubaru, S. Dash, O. Gunluk, and A. Mazumdar
Neural Information Processing Systems (NeurIPS), 2020.
[ arXiv]
Unsupervised Hierarchical Graph Representation Learning with Variational Bayes
S. Ubaru and J. Chen, 2020.
[ Link]

2019

Multilabel prediction in log time and data-dependent grouping
S. Ubaru, S. Dash, O. Gunluk, and A. Mazumdar
NeurIPS - Workshop on Information Theory and Machine Learning, 2019.
[ link]
Tensor graph neural networks for prediction on time varying graphs
O. Malik, S. Ubaru, L. Horesh, M. Kilmer, and S. Becker
NeurIPS - Workshop on Graph Representation Learning, 2019.
[ link]
Find the dimension that counts: Fast dimension estimation and Krylov PCA
S. Ubaru, A-K. Seghouane, and Y. Saad
SIAM International Conference on Data Mining (SDM), 2019.
[ arXiv, SIAM]
Spectrum-Adapted Polynomial Approximation for Matrix Functions
L. Fan, D. Shuman, S. Ubaru, and Y. Saad,
International Conference on Acoustics, Speech, and Signal Processing (ICASSP), 2019.
[ arXiv]
Sampling and multilevel algorithms for fast matrix approximations
S. Ubaru and Y. Saad,
Numerical Linear Algebra with Applications, vol 26 (3), e2234, 2019.
[ arXiv, , NLAA]
Provably convergent acceleration in factored gradient descent with applications in matrix sensing.
T Ajayi, D Mildebrath, A Kyrillidis, S. Ubaru, G Kollias, and K Bouchard, 2019.
[ arXiv]

2018

Algorithmic advances in learning from large dimensional matrices and scientific data
Ph.D. Thesis, University of Minnesota, Minneapolis, May. 2018. [ PDF]
Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness
C. Musco, P. Netrapalli, A. Sifford, S. Ubaru and D.P. Woodruff
Innovations in Theoretical Computer Science (ITCS), 2018.
[ arXiv]
Applications of trace estimation techniques
S. Ubaru and Yousef Saad
High Performance Computing in Science and Engineering (HPCSE), LNCS, vol. 11087, 19-33, 2018.
[ Link, PDF]

2017

UoI-NMF_cluster : A Robust Nonnegative Matrix Factorization Algorithm for Improved Parts-Based Decomposition and Reconstruction of Noisy Data
S. Ubaru , Kesheng Wu and Kristofer E. Bouchard
IEEE International Conference on Machine Learning and Applications (ICMLA), 2017.
[ PDF, IEEE] *Winner of the Best Paper Award*
Union of Intersections (UoI) for Interpretable Data Driven Discovery and Prediction
K. E. Bouchard, A. F. Bujan, F. Roosta-Khorasani, S. Ubaru, Prabhat, A. M. Snijders, J.-H. Mao, E. F. Chang, M. W. Mahoney, and S. Bhattacharyya
Neural Information Processing Systems (NeurIPS), 2017.
[ arXiv, NIPS]
Multilabel Classification with Group Testing and Codes
S. Ubaru and Arya Mazumdar
International Conference on Machine Learning (ICML), 2017.
[ PDF, ICML]
Fast estimation of tr(f(A)) via Stochastic Lanczos Quadrature
S. Ubaru, Jie Chen, and Yousef Saad
SIAM Journal on Matrix Analysis and Applications (SIMAX), 38(4), 1075–1099, 2017.
[ SIMAX, PDF, Codes]
Low rank approximation and decomposition of large matrices using error correcting codes
S. Ubaru, Arya Mazumdar, and Yousef Saad
IEEE Transactions on Information Theory, 63(9), 5544-5558, 2017.
[ arXiv, TofIT]
Formation enthalpies for transition metal alloys using machine learning
S. Ubaru, Agnieszka Miedlar, Yousef Saad and James R. Chelikowsky
Physcal Review B, (Vol.95, No.21) 2017.
[ PRB]
Fast estimation of approximate matrix ranks using spectral densities
S. Ubaru, Yousef Saad, and Abd-Krim Seghouane
Neural Computation, 29(5):1317-1351, 2017.
[ arXiv, NC]
Improving the Incoherence of a Learned Dictionary via Rank Shrinkage
S. Ubaru, Abd-Krim Seghouane, and Yousef Saad
Neural Computation, 29(1):263-285, 2017.
[ PDF, NC]

2016

Fast methods for estimating the Numerical rank of large matrices
S. Ubaru and Yousef Saad
International Conference on Machine Learning (ICML), 2016.
[ PDF, ICML, Codes]
Group testing schemes from low-weight codewords of BCH codes
S. Ubaru, Arya Mazumdar, and Alexander Barg
IEEE International Symposium on Information Theory (ISIT), 2016.
[ PDF, ISIT]

2015 and before

Low rank approximation using error correcting coding matrices
S. Ubaru, Arya Mazumdar, and Yousef Saad
International Conference on Machine Learning (ICML), 2015.
[ PDF, talk, slides]
Published version contains some minor errors that have since been corrected in the above revised version.
Randomized techniques for matrix decomposition and estimating the approximate rank of a matrix
M. S. Thesis, University of Minnesota, Minneapolis, Nov. 2014. [ Link, PDF]
Displaying gray scales by cross pairing select and data voltages in multi-line addressed LCD
S. Ubaru and Temkar N. Ruckmongathan
IEEE, Journal of Display Technology, vol 8, no. 11, pp 669–677, November, 2012.
[ JDT]