Tootfinder

On computing sparse universal solvers for key problems in statistics
Ananias Sousa Machado, Marcia Fampa, Jon Lee
https://arxiv.org/abs/2509.04264 https://…

On computing sparse universal solvers for key problems in statistics
We give sparsity results and present algorithms for calculating minimum (vector) 1-norm universal solvers connected to least-squares problems. In particular, besides universal least-squares solvers, we consider minimum-rank universal least-squares solvers, and simultaneous universal minimum-norm/least-squares solvers. For all of these, we present and compare several new alternative linear-optimization formulations and very effective proximal-point algorithms. Overall, we found that our new Doug…

ViLLA-MMBench: A Unified Benchmark Suite for LLM-Augmented Multimodal Movie Recommendation
Fatemeh Nazary, Ali Tourani, Yashar Deldjoo, Tommaso Di Noia
https://arxiv.org/abs/2508.04206

ViLLA-MMBench: A Unified Benchmark Suite for LLM-Augmented Multimodal Movie Recommendation
Recommending long-form video content demands joint modeling of visual, audio, and textual modalities, yet most benchmarks address only raw features or narrow fusion. We present ViLLA-MMBench, a reproducible, extensible benchmark for LLM-augmented multimodal movie recommendation. Built on MovieLens and MMTF-14K, it aligns dense item embeddings from three modalities: audio (block-level, i-vector), visual (CNN, AVF), and text. Missing or sparse metadata is automatically enriched using state-of-the…

Polynomial Lattices for the BIKE Cryptosystem
Michael Schaller
https://arxiv.org/abs/2507.23641 https://arxiv.org/pdf/2507.23641

Polynomial Lattices for the BIKE Cryptosystem
In this paper we introduce a rank $2$ lattice over a polynomial ring arising from the public key of the BIKE cryptosystem \cite{aragon2022bike}. The secret key is a sparse vector in this lattice. We study properties of this lattice and generalize the recovery of weak keys from \cite{BardetDLO16}. In particular, we show that they implicitly solved a shortest vector problem in the lattice we constructed. Rather than finding only a shortest vector, we obtain a reduced basis of the lattice which ma…

Improving SpGEMM Performance Through Matrix Reordering and Cluster-wise Computation
Abdullah Al Raqibul Islam, Helen Xu, Dong Dai, Ayd{\i}n Bulu\c{c}
https://arxiv.org/abs/2507.21253

Improving SpGEMM Performance Through Matrix Reordering and Cluster-wise Computation
Sparse matrix-sparse matrix multiplication (SpGEMM) is a key kernel in many scientific applications and graph workloads. Unfortunately, SpGEMM is bottlenecked by data movement due to its irregular memory access patterns. Significant work has been devoted to developing row reordering schemes towards improving locality in sparse operations, but prior studies mostly focus on the case of sparse-matrix vector multiplication (SpMV). In this paper, we address these issues with hierarchical clusterin…

A threshold for online balancing of sparse i.i.d. vectors
Dylan J. Altschuler, Konstantin Tikhomirov
https://arxiv.org/abs/2509.02432 https://arxiv.org/pdf…

A threshold for online balancing of sparse i.i.d. vectors
Consider the task of \textit{online} vector balancing for stochastic arrivals $(X_i)_{i \in [T]}$, where the time horizon satisfies $T = Θ(n)$, and the $X_i$ are i.i.d uniform $d$--sparse $n$--dimensional binary vectors, with $2\leq d \le (\log\log n)^2/\log\log\log n$. We show that for this range of parameters, every online algorithm incurs discrepancy at least $Ω(\log \log n)$, and there is an efficient algorithm which achieves a matching discrepancy bound of $O(\log\log n)$ w.h.p. This est…

Near-Optimal Differentially Private Graph Algorithms via the Multidimensional AboveThreshold Mechanism
Laxman Dhulipala, Monika Henzinger, George Z. Li, Quanquan C. Liu, A. R. Sricharan, Leqi Zhu
https://arxiv.org/abs/2508.02182

Near-Optimal Differentially Private Graph Algorithms via the Multidimensional AboveThreshold Mechanism
Many differentially private and classical non-private graph algorithms rely crucially on determining whether some property of each vertex meets a threshold. For example, for the $k$-core decomposition problem, the classic peeling algorithm iteratively removes a vertex if its induced degree falls below a threshold. The sparse vector technique (SVT) is generally used to transform non-private threshold queries into private ones with only a small additive loss in accuracy. However, a naive applicat…

Learning to Ask: Decision Transformers for Adaptive Quantitative Group Testing
Mahdi Soleymani, Tara Javidi
https://arxiv.org/abs/2509.01723 https://arxiv.…

Learning to Ask: Decision Transformers for Adaptive Quantitative Group Testing
We consider the problem of quantitative group testing (QGT), where the goal is to recover a sparse binary vector from aggregate subset-sum queries: each query selects a subset of indices and returns the sum of those entries. Information-theoretic results suggest that adaptivity could yield up to a twofold reduction in the total number of required queries, yet no algorithm has surpassed the non-adaptive bound, leaving its practical benefit an open question. In this paper, we reduce the QGT probl…

Quantum Algorithms for Projection-Free Sparse Convex Optimization
Jianhao He, John C. S. Lui
https://arxiv.org/abs/2507.08543 https://

Quantum Algorithms for Projection-Free Sparse Convex Optimization
This paper considers the projection-free sparse convex optimization problem for the vector domain and the matrix domain, which covers a large number of important applications in machine learning and data science. For the vector domain $\mathcal{D} \subset \mathbb{R}^d$, we propose two quantum algorithms for sparse constraints that finds a $\varepsilon$-optimal solution with the query complexity of $O(\sqrt{d}/\varepsilon)$ and $O(1/\varepsilon)$ by using the function value oracle, reducing a fa…

Is Sparse Matrix Reordering Effective for Sparse Matrix-Vector Multiplication?
Omid Asudeh, Sina Mahdipour Saravani, Gerald Sabin, Fabrice Rastello, P Sadayappan
https://arxiv.org/abs/2506.10356

Is Sparse Matrix Reordering Effective for Sparse Matrix-Vector Multiplication?
This work evaluates the impact of sparse matrix reordering on the performance of sparse matrix-vector multiplication across different multicore CPU platforms. Reordering can significantly enhance performance by optimizing the non-zero element patterns to reduce total data movement and improve the load-balancing. We examine how these gains vary over different CPUs for different reordering strategies, focusing on both sequential and parallel execution. We address multiple aspects, including appro…

Communication-Efficient Publication of Sparse Vectors under Differential Privacy
Quentin Hillebrand, Vorapong Suppakitpaisarn, Tetsuo Shibuya
https://arxiv.org/abs/2506.20234

Communication-Efficient Publication of Sparse Vectors under Differential Privacy
In this work, we propose a differentially private algorithm for publishing matrices aggregated from sparse vectors. These matrices include social network adjacency matrices, user-item interaction matrices in recommendation systems, and single nucleotide polymorphisms (SNPs) in DNA data. Traditionally, differential privacy in vector collection relies on randomized response, but this approach incurs high communication costs. Specifically, for a matrix with $N$ users, $n$ columns, and $m$ nonzero …

Exploiting repeated matrix block structures for more efficient CFD on modern supercomputers
Josep Plana-Riu, F. Xavier Trias, \`Adel Alsalti-Baldellou, Xavier \'Alvarez-Farr\'e, Guillem Colomer, Assensi Oliva
https://arxiv.org/abs/2508.06710

Exploiting repeated matrix block structures for more efficient CFD on modern supercomputers
Computational Fluid Dynamics (CFD) simulations are often constrained by the memory-bound nature of sparse matrix-vector operations, which eventually limits performance on modern high-performance computing (HPC) systems. This work introduces a novel approach to increase arithmetic intensity in CFD by leveraging repeated matrix block structures. The method transforms the conventional sparse matrix-vector product (SpMV) into a sparse matrix-matrix product (SpMM), enabling simultaneous processing o…

High-dimensional regression with outcomes of mixed-type using the multivariate spike-and-slab LASSO
Soham Ghosh, Sameer K. Deshpande
https://arxiv.org/abs/2506.13007

High-dimensional regression with outcomes of mixed-type using the multivariate spike-and-slab LASSO
We consider a high-dimensional multi-outcome regression in which $q,$ possibly dependent, binary and continuous outcomes are regressed onto $p$ covariates. We model the observed outcome vector as a partially observed latent realization from a multivariate linear regression model. Our goal is to estimate simultaneously a sparse matrix ($B$) of latent regression coefficients (i.e., partial covariate effects) and a sparse latent residual precision matrix ($Ω$), which induces partial correlations …

Toward Efficient SpMV in Sparse LLMs via Block Extraction and Compressed Storage
Junqing Lin, Jingwei Sun, Mingge Lu, Guangzhong Sun
https://arxiv.org/abs/2507.12205

Toward Efficient SpMV in Sparse LLMs via Block Extraction and Compressed Storage
Sparse Matrix-Vector Multiplication (SpMV) has become a critical performance bottleneck in the local deployment of sparse Large Language Models (LLMs), where inference predominantly operates on workloads during the decoder phase with a batch size of one. Existing SpMV kernels and sparse matrix formats, originally designed for scientific computing, fail to exploit the unique structure patterns inherent in sparse LLMs, resulting in suboptimal performance and excessive storage overhead. This paper…

Basis pursuit by inconsistent alternating projections
Roger Behling, Yunier Bello-Cruz, Luiz-Rafael Santos, Paulo J. S. Silva
https://arxiv.org/abs/2508.15026 https://

Basis pursuit by inconsistent alternating projections
Basis pursuit is the problem of finding a vector with smallest $\ell_1$-norm among the solutions of a given linear system of equations. It is a famous convex relaxation of what the literature refers to as sparse affine feasibility problem, in which sparse solutions to underdetermined systems are sought. In addition to enjoying convexity, the basis pursuit can be trivially rewritten as a linear program, and thus standard tools in linear programming apply for solving it. In turn, we tackle the …

Query Efficient Structured Matrix Learning
Noah Amsel, Pratyush Avi, Tyler Chen, Feyza Duman Keles, Chinmay Hegde, Cameron Musco, Christopher Musco, David Persson
https://arxiv.org/abs/2507.19290

Query Efficient Structured Matrix Learning
We study the problem of learning a structured approximation (low-rank, sparse, banded, etc.) to an unknown matrix $A$ given access to matrix-vector product (matvec) queries of the form $x \rightarrow Ax$ and $x \rightarrow A^Tx$. This problem is of central importance to algorithms across scientific computing and machine learning, with applications to fast multiplication and inversion for structured matrices, building preconditioners for first-order optimization, and as a model for differential …

Latent confounding in high-dimensional nonlinear models
Yuhao Wang, Rajen Shah
https://arxiv.org/abs/2508.06274 https://arxiv.org/pdf/2508.06274

Latent confounding in high-dimensional nonlinear models
We consider the the problem of identifying causal effects given a high-dimensional treatment vector in the presence of low-dimensional latent confounders. We assume a parametric structural causal model in which the outcome is permitted to depend on a sparse linear combination of the treatment vector and confounders nonlinearly. We consider a generalisation of the LAVA estimator of Chernozhukov et al. [2017] for estimating the treatment effects and show that under the so-called `dense confoundin…

Matrix Weighted $L^p$ Estimates in the Nonhomogeneous Setting
Fernando Benito-de la Cigo\~na, Tainara Borges, Francesco D'Emilio, Marcus Pasquariello, Nathan A. Wagner
https://arxiv.org/abs/2506.15570

Matrix Weighted $L^p$ Estimates in the Nonhomogeneous Setting
We establish a modified pointwise convex body domination for vector-valued Haar shifts in the nonhomogeneous setting, strengthening and extending the scalar case developed in arXiv:2309.13943. Moreover, we identify a subclass of shifts, called $L^1$-normalized, for which the standard convex body domination holds without requiring any regularity assumption on the measure. Finally, we extend the best-known matrix weighted $L^p$ estimates for sparse forms to the nonhomogeneous setting. The key dif…