6 papers
Learning Multiband Signals and Fourier-sparse Signals
Dongrun Cai, Xue Chen, Xiaowei Shao
We consider efficient algorithms to learn multiband signals and Fourier-sparse signals. A mutliband signal has a Fourier transform supported by a bounded number of intervals, say $…
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…
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…
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…
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…
Effective Resistances in Non-Expander Graphs
Dongrun Cai, Xue Chen, Pan Peng
Effective resistances are ubiquitous in graph algorithms and network analysis. In this work, we study sublinear time algorithms to approximate the effective resistance of an adjace…