3 papers
cs.DS2026
Improved Algorithms for Learning Fourier-sparse Signals
Dongrun Cai, Xue Chen, Xiaowei Shao +1
A classical problem in sparse Fourier transforms, which dates back to the work by Prony in 1795 at least, is to learn a -Fourier-sparse signal $x(t):=\sum_{j=1}^k α_j e^{2 π\mat…
cs.DS2026
Sparsify Submodular Functions under Cardinality Constraints
Zhengting Bao, Dongrun Cai, Xue Chen
Submodular sparsification generalizes the classical sparsification problems of graphs and matrices to summations of submodular functions. Given the summation $F(S):=f_1(S)+\cdots+f…
cs.CR2025
Algorithms for Sparse LPN and LSPN Against Low-noise
Xue Chen, Wenxuan Shu, Zhaienhe Zhou
We consider sparse variants of the classical Learning Parities with random Noise (LPN) problem. Our main contribution is a new algorithmic framework that provides learning algorith…