Showing cs.DSShow all
3 papers · 1 filter
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.DS2024
Revisit the Partial Coloring Method: Prefix Spencer and Sampling
Dongrun Cai, Xue Chen, Wenxuan Shu +2
As the most powerful tool in discrepancy theory, the partial coloring method has wide applications in many problems including the Beck-Fiala problem and Spencer's celebrated result…