Zhao Song - RankMe

438 papers A* 107A 28B 18C 1Misc 1Journal 268Unranked 13

Year	Rank	Type	Title / Venue / Authors
2026	A*	`conf`	L SODA Honghao Lin, Zhao Song, David P. Woodruff, Shenghao Xie, Samson Zhou
2026	J	`jnl`	Lazy Kronecker Product. CoRR Zhao Song
2026	J	`jnl`	Sublinear Time Quantum Algorithm for Attention Approximation. CoRR Zhao Song, Jianfei Xue, Jiahao Zhang, Lichen Zhang
2026	J	`jnl`	Tensor Hinted Mv Conjectures. CoRR Zhao Song
2025	A	`conf`	A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Time. UAI Yeqi Gao, Zhao Song, Weixin Wang, Junze Yin
2025	J	`jnl`	A Theoretical Analysis of Discrete Flow Matching Generative Models. CoRR Maojiang Su, Mingcheng Lu, Jerry Yao-Chieh Hu, Shang Wu, Zhao Song, Alex Daniel Reneau, Han Liu
2025	B	`conf`	A Theoretical Framework Bridging Attention and SVM Optimization Dynamics and Sparsity. IEEE Big Data Zhihang Li, Zhao Song, Jiale Zhao
2025	B	`conf`	Accelerating k-means ++ Algorithm. IEEE Big Data Jiehao Liang, Somdeb Sarkhel, Zhao Song, Chenbo Yin, Zhen Zhuang, Danyang Zhuo
2025	J	`jnl`	Accept More, Reject Less: Reducing up to 19% Unnecessary Desk-Rejections over 11 Years of ICLR Data. CoRR Xiaoyu Li, Zhao Song, Jiahao Zhang
2025	A	`conf`	An Iterative Algorithm for Rescaled Hyperbolic Functions Regression. AISTATS Yeqi Gao, Zhao Song, Junze Yin
2025	J	`jnl`	Approximation Algorithms for LCS and LIS with Truly Improved Running Times. SIAM J. Comput. Aviad Rubinstein, Saeed Seddighin, Zhao Song, Xiaorui Sun
2025	J	`jnl`	Are Hallucinations Bad Estimations? CoRR Hude Liu, Jerry Yao-Chieh Hu, Jennifer Yuntong Zhang, Zhao Song, Han Liu
2025	J	`jnl`	Attention Mechanism, Max-Affine Partition, and Universal Approximation. CoRR Hude Liu, Jerry Yao-Chieh Hu, Zhao Song, Han Liu
2025	A*	`conf`	Beyond Linear Approximations: A Novel Pruning Approach for Attention Matrix. ICLR Yingyu Liang, Jiangxuan Long, Zhenmei Shi, Zhao Song, Yufa Zhou
2025	A*	`conf`	Binary Hypothesis Testing for Softmax Models and Leverage Score Models. ICML Yuzhou Gu, Zhao Song, Junze Yin
2025	A	`conf`	Bypassing the Exponential Dependency: Looped Transformers Efficiently Learn In-context by Multi-step Gradient Descent. AISTATS Bo Chen, Xiaoyu Li, Yingyu Liang, Zhenmei Shi, Zhao Song
2025	J	`jnl`	Can You Count to Nine? A Human Evaluation Benchmark for Counting Limits in Modern Text-to-Video Models. CoRR Xuyang Guo, Zekai Huang, Jiayan Huo, Yingyu Liang, Zhenmei Shi, Zhao Song, Jiahao Zhang
2025	A*	`conf`	Circuit Complexity Bounds for RoPE-based Transformer Architecture. EMNLP Bo Chen, Xiaoyu Li, Yingyu Liang, Jiangxuan Long, Zhenmei Shi, Zhao Song, Jiahao Zhang
2025	J	`jnl`	Circuit Complexity Bounds for Visual Autoregressive Model. CoRR Yekun Ke, Xiaoyu Li, Yingyu Liang, Zhenmei Shi, Zhao Song
2025	A*	`conf`	Computational Limits of Low-Rank Adaptation (LoRA) Fine-Tuning for Transformer Models. ICLR Jerry Yao-Chieh Hu, Maojiang Su, En-Jui Kuo, Zhao Song, Han Liu
2025	—	`conf`	Conv-Basis: A New Paradigm for Efficient Attention Inference and Gradient Computation in Transformers. EMNLP (Findings) Yingyu Liang, Heshan Liu, Zhenmei Shi, Zhao Song, Zhuoyan Xu, Jiale Zhao, Zhen Zhuang
2025	—	`conf`	Curse of Attention: A Kernel-Based Perspective for Why Transformers Fail to Generalize on Time Series Forecasting and Beyond. CPAL Yekun Ke, Yingyu Liang, Zhenmei Shi, Zhao Song, Chiwun Yang
2025	J	`jnl`	DPBloomfilter: Securing Bloom Filters with Differential Privacy. CoRR Yekun Ke, Yingyu Liang, Zhizhou Sha, Zhenmei Shi, Zhao Song
2025	A*	`conf`	Deterministic Sparse Fourier Transform for Continuous Signals with Frequency Gap. ICML Xiaoyu Li, Zhao Song, Shenghao Xie
2025	A	`conf`	Differential Privacy Mechanisms in Neural Tangent Kernel Regression. WACV Jiuxiang Gu, Yingyu Liang, Zhizhou Sha, Zhenmei Shi, Zhao Song
2025	J	`jnl`	Differential Privacy for Euclidean Jordan Algebra with Applications to Private Symmetric Cone Programming. CoRR Zhao Song, Jianfei Xue, Lichen Zhang
2025	B	`conf`	Diffusion Modeling is Volumetric Barrier Function. IEEE Big Data Yang Cao, Yubin Chen, Xiaoyu Li, Zhao Song
2025	A*	`conf`	Discrepancy Minimization in Input-Sparsity Time. ICML Yichuan Deng, Xiaoyu Li, Zhao Song, Omri Weinstein
2025	J	`jnl`	Discriminator-Free Direct Preference Optimization for Video Diffusion. CoRR Haoran Cheng, Qide Dong, Liang Peng, Zhizhou Sha, Weiguo Feng, Jinghui Xie, Zhao Song, Shilei Wen, Xiaofei He, Boxi Wu
2025	A*	`conf`	Dissecting Submission Limit in Desk-Rejections: A Mathematical Analysis of Fairness in AI Conference Policies. ICML Yuefan Cao, Xiaoyu Li, Yingyu Liang, Zhizhou Sha, Zhenmei Shi, Zhao Song, Jiahao Zhang
2025	J	`jnl`	Dissecting Submission Limit in Desk-Rejections: A Mathematical Analysis of Fairness in AI Conference Policies. CoRR Yuefan Cao, Xiaoyu Li, Yingyu Liang, Zhizhou Sha, Zhenmei Shi, Zhao Song, Jiahao Zhang
2025	A	`conf`	Dynamic Maintenance of Kernel Density Estimation Data Structure: From Practice to Theory. UAI Jiehao Liang, Zhao Song, Zhaozhuo Xu, Junze Yin, Danyang Zhuo
2025	A*	`conf`	Efficient Alternating Minimization with Applications to Weighted Low Rank Approximation. ICLR Zhao Song, Mingquan Ye, Junze Yin, Lichen Zhang
2025	J	`jnl`	Evaluating Frontier LLMs on PhD-Level Mathematical Reasoning: A Benchmark on a Textbook in Theoretical Computer Science about Randomized Algorithms. CoRR Yang Cao, Yubin Chen, Xuyang Guo, Zhao Song, Song Yue, Jiahao Zhang, Jiale Zhao
2025	J	`jnl`	Exploring the Limits of KV Cache Compression in Visual Autoregressive Transformers. CoRR Bo Chen, Xiaoyu Li, Yekun Ke, Yingyu Liang, Zhenmei Shi, Zhao Song
2025	—	`conf`	Fast John Ellipsoid Computation with Differential Privacy Optimization. CPAL Xiaoyu Li, Yingyu Liang, Zhenmei Shi, Zhao Song, Junwei Yu
2025	J	`jnl`	Fast RoPE Attention: Combining the Polynomial Method and Fast Fourier Transform. CoRR Josh Alman, Zhao Song
2025	A*	`conf`	Fast Sampling for Privacy-Preserving Lazy Multiplicative Weight Update. ICDM Xiaoyu Li, Zhao Song, Jiale Zhao
2025	—	`conf`	Fast and Efficient Matching Algorithm with Deadline Instances. CPAL Zhao Song, Weixin Wang, Chenbo Yin, Junze Yin
2025	A*	`conf`	Faster Algorithms for Structured Linear and Kernel Support Vector Machines. ICLR Yuzhou Gu, Zhao Song, Lichen Zhang
2025	A	`conf`	Force Matching with Relativistic Constraints: A Physics-Inspired Approach to Stable and Efficient Generative Modeling. CIKM Yang Cao, Bo Chen, Xiaoyu Li, Yingyu Liang, Zhizhou Sha, Zhenmei Shi, Zhao Song, Mingda Wan
2025	J	`jnl`	Force Matching with Relativistic Constraints: A Physics-Inspired Approach to Stable and Efficient Generative Modeling. CoRR Yang Cao, Bo Chen, Xiaoyu Li, Yingyu Liang, Zhizhou Sha, Zhenmei Shi, Zhao Song, Mingda Wan
2025	A	`conf`	Fourier Circuits in Neural Networks and Transformers: A Case Study of Modular Arithmetic with Multiple Inputs. AISTATS Chenyang Li, Yingyu Liang, Zhenmei Shi, Zhao Song, Tianyi Zhou
2025	J	`jnl`	Fundamental Limits of Crystalline Equivariant Graph Neural Networks: A Circuit Complexity Perspective. CoRR Yang Cao, Zhao Song, Jiahao Zhang, Jiale Zhao
2025	A*	`conf`	Fundamental Limits of Prompt Tuning Transformers: Universality, Capacity and Efficiency. ICLR Jerry Yao-Chieh Hu, Wei-Po Wang, Ammar Gilani, Chenyang Li, Zhao Song, Han Liu
2025	A*	`conf`	Fundamental Limits of Visual Autoregressive Transformers: Universal Approximation Abilities. ICML Yifang Chen, Xiaoyu Li, Yingyu Liang, Zhenmei Shi, Zhao Song
2025	J	`jnl`	HOFAR: High-Order Augmentation of Flow Autoregressive Transformers. CoRR Yingyu Liang, Zhizhou Sha, Zhenmei Shi, Zhao Song, Mingda Wan
2025	—	`conf`	HSR-Enhanced Sparse Attention Acceleration. CPAL Bo Chen, Yingyu Liang, Zhizhou Sha, Zhenmei Shi, Zhao Song
2025	J	`jnl`	High-Order Matching for One-Step Shortcut Diffusion Models. CoRR Bo Chen, Chengyue Gong, Xiaoyu Li, Yingyu Liang, Zhizhou Sha, Zhenmei Shi, Zhao Song, Mingda Wan
2025	A*	`conf`	In-Context Deep Learning via Transformer Models. ICML Weimin Wu, Maojiang Su, Jerry Yao-Chieh Hu, Zhao Song, Han Liu
2025	J	`jnl`	L CoRR Honghao Lin, Zhao Song, David P. Woodruff, Shenghao Xie, Samson Zhou
2025	A*	`conf`	LazyDiT: Lazy Learning for the Acceleration of Diffusion Transformers. AAAI Xuan Shen, Zhao Song, Yufa Zhou, Bo Chen, Yanyu Li, Yifan Gong, Kai Zhang, Hao Tan, Jason Kuen, Henghui Ding, Zhihao Shu, Wei Niu, Pu Zhao, Yanzhi Wang, Jiuxiang Gu
2025	A	`conf`	Looped ReLU MLPs May Be All You Need as Practical Programmable Computers. AISTATS Yingyu Liang, Zhizhou Sha, Zhenmei Shi, Zhao Song, Yufa Zhou
2025	J	`jnl`	Minimalist Softmax Attention Provably Learns Constrained Boolean Functions. CoRR Jerry Yao-Chieh Hu, Xiwen Zhang, Maojiang Su, Zhao Song, Han Liu
2025	A	`conf`	NRFlow: Towards Noise-Robust Generative Modeling via High-Order Mechanism. UAI Bo Chen, Chengyue Gong, Xiaoyu Li, Yingyu Liang, Zhizhou Sha, Zhenmei Shi, Zhao Song, Mingda Wan, Xugang Ye
2025	J	`jnl`	Neural Algorithmic Reasoning for Hypergraphs with Looped Transformers. CoRR Xiaoyu Li, Yingyu Liang, Jiangxuan Long, Zhenmei Shi, Zhao Song, Zhen Zhuang
2025	A*	`conf`	Numerical Pruning for Efficient Autoregressive Models. AAAI Xuan Shen, Zhao Song, Yufa Zhou, Bo Chen, Jing Liu, Ruiyi Zhang, Ryan A. Rossi, Hao Tan, Tong Yu, Xiang Chen, Yufan Zhou, Tong Sun, Pu Zhao, Yanzhi Wang, Jiuxiang Gu
2025	J	`jnl`	On Computational Limits and Provably Efficient Criteria of Visual Autoregressive Models: A Fine-Grained Complexity Analysis. CoRR Yekun Ke, Xiaoyu Li, Yingyu Liang, Zhizhou Sha, Zhenmei Shi, Zhao Song
2025	J	`jnl`	On Computational Limits of FlowAR Models: Expressivity and Efficiency. CoRR Chengyue Gong, Yekun Ke, Xiaoyu Li, Yingyu Liang, Zhizhou Sha, Zhenmei Shi, Zhao Song
2025	A*	`conf`	On Differential Privacy for Adaptively Solving Search Problems via Sketching. ICML Shiyuan Feng, Ying Feng, George Zhaoqi Li, Zhao Song, David P. Woodruff, Lichen Zhang
2025	J	`jnl`	On Differential Privacy for Adaptively Solving Search Problems via Sketching. CoRR Shiyuan Feng, Ying Feng, George Z. Li, Zhao Song, David P. Woodruff, Lichen Zhang
2025	B	`conf`	On Efficient Computation of Generalized Distance Oracles. IEEE Big Data Zhao Song, Jason Zhang, Jiahao Zhang
2025	J	`jnl`	On the Computational Capability of Graph Neural Networks: A Circuit Complexity Bound Perspective. CoRR Xiaoyu Li, Yingyu Liang, Zhenmei Shi, Zhao Song, Wei Wang, Jiahao Zhang
2025	J	`jnl`	Only Large Weights (And Not Skip Connections) Can Prevent the Perils of Rank Collapse. CoRR Josh Alman, Zhao Song
2025	J	`jnl`	Provable Failure of Language Models in Learning Majority Boolean Logic via Gradient Descent. CoRR Bo Chen, Zhenmei Shi, Zhao Song, Jiahao Zhang
2025	J	`jnl`	RichSpace: Enriching Text-to-Video Prompt Space via Text Embedding Interpolation. CoRR Yuefan Cao, Chengyue Gong, Xiaoyu Li, Yingyu Liang, Zhizhou Sha, Zhenmei Shi, Zhao Song
2025	J	`jnl`	Scaling Law Phenomena Across Regression Paradigms: Multiple and Kernel Approaches. CoRR Yifang Chen, Xuyang Guo, Xiaoyu Li, Yingyu Liang, Zhenmei Shi, Zhao Song
2025	—	`conf`	Streaming Kernel PCA Algorithm With Small Space. CPAL Yichuan Deng, Jiangxuan Long, Zhao Song, Zifan Wang, Han Zhang
2025	J	`jnl`	Sublinear Time Quantum Sensitivity Sampling. CoRR Zhao Song, David P. Woodruff, Lichen Zhang
2025	J	`jnl`	T2VPhysBench: A First-Principles Benchmark for Physical Consistency in Text-to-Video Generation. CoRR Xuyang Guo, Jiayan Huo, Zhenmei Shi, Zhao Song, Jiahao Zhang, Jiale Zhao
2025	J	`jnl`	T2VTextBench: A Human Evaluation Benchmark for Textual Control in Video Generation Models. CoRR Xuyang Guo, Jiayan Huo, Zhenmei Shi, Zhao Song, Jiahao Zhang, Jiale Zhao
2025	J	`jnl`	T2VWorldBench: A Benchmark for Evaluating World Knowledge in Text-to-Video Generation. CoRR Yubin Chen, Xuyang Guo, Zhenmei Shi, Zhao Song, Jiahao Zhang
2025	J	`jnl`	Text-to-Edit: Controllable End-to-End Video Ad Creation via Multimodal LLMs. CoRR Dabing Cheng, Haosen Zhan, Xingchen Zhao, Guisheng Liu, Zemin Li, Jinghui Xie, Zhao Song, Weiguo Feng, Bingyue Peng
2025	J	`jnl`	Text-to-Image Diffusion Models Cannot Count, and Prompt Refinement Cannot Help. CoRR Yuefan Cao, Xuyang Guo, Jiayan Huo, Yingyu Liang, Zhenmei Shi, Zhao Song, Jiahao Zhang, Zhen Zhuang
2025	—	`conf`	The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexity. CPAL Yifang Chen, Xiaoyu Li, Yingyu Liang, Zhenmei Shi, Zhao Song
2025	—	`conf`	The Expressibility of Polynomial based Attention Scheme. KDD (2) Zhao Song, Chongxi Wang, Guangyi Xu, Junze Yin
2025	J	`jnl`	Theoretical Foundation of Flow-Based Time Series Generation: Provable Approximation, Generalization, and Efficiency. CoRR Jiangxuan Long, Zhao Song, Chiwun Yang
2025	J	`jnl`	Theoretical Guarantees for High Order Trajectory Refinement in Generative Flows. CoRR Chengyue Gong, Xiaoyu Li, Yingyu Liang, Jiangxuan Long, Zhenmei Shi, Zhao Song, Yu Tian
2025	J	`jnl`	Thinking Isn't an Illusion: Overcoming the Limitations of Reasoning Models via Tool Augmentations. CoRR Zhao Song, Song Yue, Jiahao Zhang
2025	J	`jnl`	Time and Memory Trade-off of KV-Cache Compression in Tensor Transformer Decoding. CoRR Yifang Chen, Xiaoyu Li, Yingyu Liang, Zhenmei Shi, Zhao Song, Yu Tian
2025	J	`jnl`	Too Easily Fooled? Prompt Injection Breaks LLMs on Frustratingly Simple Multiple-Choice Questions. CoRR Xuyang Guo, Zekai Huang, Zhao Song, Jiahao Zhang
2025	J	`jnl`	Towards High-Order Mean Flow Generative Models: Feasibility, Expressivity, and Provably Efficient Criteria. CoRR Yang Cao, Yubin Chen, Zhao Song, Jiahao Zhang
2025	A*	`conf`	Towards Infinite-Long Prefix in Transformer. EMNLP Yingyu Liang, Zhenmei Shi, Zhao Song, Chiwun Yang
2025	J	`jnl`	Towards Sampling Data Structures for Tensor Products in Turnstile Streams. CoRR Zhao Song, Shenghao Xie, Samson Zhou
2025	J	`jnl`	Universal Approximation of Visual Autoregressive Transformers. CoRR Yifang Chen, Xiaoyu Li, Yingyu Liang, Zhenmei Shi, Zhao Song
2025	—	`conf`	Unlock the Theory behind Scaling 1-bit Neural Networks. CPAL Majid Daliri, Zhao Song, Chiwun Yang
2025	J	`jnl`	Video Latent Flow Matching: Optimal Polynomial Projections for Video Interpolation and Extrapolation. CoRR Yang Cao, Zhao Song, Chiwun Yang
2025	A	`conf`	When Can We Solve the Weighted Low Rank Approximation Problem in Truly Subquadratic Time? AISTATS Chenyang Li, Yingyu Liang, Zhenmei Shi, Zhao Song
2025	J	`jnl`	When Can We Solve the Weighted Low Rank Approximation Problem in Truly Subquadratic Time? CoRR Chenyang Li, Yingyu Liang, Zhenmei Shi, Zhao Song
2025	J	`jnl`	When a Paper Has 1000 Authors: Rethinking Citation Metrics in the Era of LLMs. CoRR Weihang Guo, Zhao Song, Jiahao Zhang
2025	J	`jnl`	Which Coauthor Should I Nominate in My 99 ICLR Submissions? A Mathematical Analysis of the ICLR 2026 Reciprocal Reviewer Nomination Policy. CoRR Zhao Song, Song Yue, Jiahao Zhang
2025	B	`conf`	Why Softmax Attention Outperforms Linear Attention. IEEE Big Data Yichuan Deng, Zhao Song, Kaijun Yuan, Tianyi Zhou
2025	J	`jnl`	Your Vision-Language Model Can't Even Count to 20: Exposing the Failures of VLMs in Compositional Counting. CoRR Xuyang Guo, Zekai Huang, Zhenmei Shi, Zhao Song, Jiahao Zhang
2024	A	`conf`	A General Algorithm for Solving Rank-one Matrix Sensing. AISTATS Lianke Qin, Zhao Song, Ruizhe Zhang
2024	A*	`conf`	A Sublinear Adversarial Training Algorithm. ICLR Yeqi Gao, Lianke Qin, Zhao Song, Yitan Wang
2024	J	`jnl`	A Tighter Complexity Analysis of SparseGPT. CoRR Xiaoyu Li, Yingyu Liang, Zhenmei Shi, Zhao Song
2024	J	`jnl`	Advancing the Understanding of Fixed Point Iterations in Deep Neural Networks: A Detailed Analytical Study. CoRR Yekun Ke, Xiaoyu Li, Yingyu Liang, Zhenmei Shi, Zhao Song
2024	A*	`conf`	Algorithm and Hardness for Dynamic Attention Maintenance in Large Language Models. ICML Jan van den Brand, Zhao Song, Tianyi Zhou
2024	J	`jnl`	Attention is Naturally Sparse with Gaussian Distributed Input. CoRR Yichuan Deng, Zhao Song, Chiwun Yang
2024	J	`jnl`	Beyond Linear Approximations: A Novel Pruning Approach for Attention Matrix. CoRR Yingyu Liang, Jiangxuan Long, Zhenmei Shi, Zhao Song, Yufa Zhou
2024	J	`jnl`	Binary Hypothesis Testing for Softmax Models and Leverage Score Models. CoRR Yeqi Gao, Yuzhou Gu, Zhao Song
2024	J	`jnl`	Bypassing the Exponential Dependency: Looped Transformers Efficiently Learn In-context by Multi-step Gradient Descent. CoRR Bo Chen, Xiaoyu Li, Yingyu Liang, Zhenmei Shi, Zhao Song
2024	J	`jnl`	Circuit Complexity Bounds for RoPE-based Transformer Architecture. CoRR Bo Chen, Xiaoyu Li, Yingyu Liang, Jiangxuan Long, Zhenmei Shi, Zhao Song
2024	J	`jnl`	Computational Limits of Low-Rank Adaptation (LoRA) for Transformer-Based Models. CoRR Jerry Yao-Chieh Hu, Maojiang Su, En-Jui Kuo, Zhao Song, Han Liu
2024	J	`jnl`	Conv-Basis: A New Paradigm for Efficient Attention Inference and Gradient Computation in Transformers. CoRR Jiuxiang Gu, Yingyu Liang, Heshan Liu, Zhenmei Shi, Zhao Song, Junze Yin
2024	A*	`conf`	Convex Minimization with Integer Minima in SODA Haotian Jiang, Yin Tat Lee, Zhao Song, Lichen Zhang
2024	J	`jnl`	Curse of Attention: A Kernel-Based Perspective for Why Transformers Fail to Generalize on Time Series Forecasting and Beyond. CoRR Yekun Ke, Yingyu Liang, Zhenmei Shi, Zhao Song, Chiwun Yang
2024	J	`jnl`	Differential Privacy Mechanisms in Neural Tangent Kernel Regression. CoRR Jiuxiang Gu, Yingyu Liang, Zhizhou Sha, Zhenmei Shi, Zhao Song
2024	J	`jnl`	Differential Privacy of Cross-Attention with Provable Guarantee. CoRR Jiuxiang Gu, Yingyu Liang, Zhenmei Shi, Zhao Song, Yufa Zhou
2024	J	`jnl`	Differentially Private Kernel Density Estimation. CoRR Erzhi Liu, Jerry Yao-Chieh Hu, Alex Daniel Reneau, Zhao Song, Han Liu
2024	B	`conf`	Efficient SGD Neural Network Training via Sublinear Activated Neuron Identification. IEEE Big Data Lianke Qin, Zhao Song, Yuanyuan Yang
2024	J	`jnl`	Enhancing Stochastic Gradient Descent: A Unified Framework and Novel Acceleration Methods for Faster Convergence. CoRR Yichuan Deng, Zhao Song, Chiwun Yang
2024	J	`jnl`	Exploring the Frontiers of Softmax: Provable Optimization, Applications in Diffusion Model, and Beyond. CoRR Jiuxiang Gu, Chenyang Li, Yingyu Liang, Zhenmei Shi, Zhao Song
2024	A	`conf`	Fast Dynamic Sampling for Determinantal Point Processes. AISTATS Zhao Song, Junze Yin, Lichen Zhang, Ruizhe Zhang
2024	J	`jnl`	Fast Gradient Computation for RoPE Attention in Almost Linear Time. CoRR Yifang Chen, Jiayan Huo, Xiaoyu Li, Yingyu Liang, Zhenmei Shi, Zhao Song
2024	J	`jnl`	Fast John Ellipsoid Computation with Differential Privacy Optimization. CoRR Jiuxiang Gu, Xiaoyu Li, Yingyu Liang, Zhenmei Shi, Zhao Song, Junwei Yu
2024	B	`conf`	Fast Second-order Method for Neural Networks under Small Treewidth Setting. IEEE Big Data Xiaoyu Li, Jiangxuan Long, Zhao Song, Tianyi Zhou
2024	B	`conf`	Faster Sampling Algorithms for Polytopes with Small Treewidth. IEEE Big Data Yekun Ke, Xiaoyu Li, Zhao Song, Tianyi Zhou
2024	J	`jnl`	Fine-grained Attention I/O Complexity: Comprehensive Analysis for Backward Passes. CoRR Xiaoyu Li, Yingyu Liang, Zhenmei Shi, Zhao Song, Yufa Zhou
2024	J	`jnl`	Fourier Circuits in Neural Networks: Unlocking the Potential of Large Language Models in Mathematical Reasoning and Modular Arithmetic. CoRR Jiuxiang Gu, Chenyang Li, Yingyu Liang, Zhenmei Shi, Zhao Song, Tianyi Zhou
2024	J	`jnl`	Fundamental Limits of Prompt Tuning Transformers: Universality, Capacity and Efficiency. CoRR Jerry Yao-Chieh Hu, Wei-Po Wang, Ammar Gilani, Chenyang Li, Zhao Song, Han Liu
2024	J	`jnl`	Grams: Gradient Descent with Adaptive Momentum Scaling. CoRR Yang Cao, Xiaoyu Li, Zhao Song
2024	J	`jnl`	HSR-Enhanced Sparse Attention Acceleration. CoRR Bo Chen, Yingyu Liang, Zhizhou Sha, Zhenmei Shi, Zhao Song
2024	A*	`conf`	How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computation. ICLR Josh Alman, Zhao Song
2024	J	`jnl`	How to Inverting the Leverage Score Distribution? CoRR Zhihang Li, Zhao Song, Weixin Wang, Junze Yin, Zheng Yu
2024	A*	`conf`	How to Protect Copyright Data in Optimization of Large Language Models? AAAI Timothy Chu, Zhao Song, Chiwun Yang
2024	J	`jnl`	Inverting the Leverage Score Gradient: An Efficient Approximate Newton Method. CoRR Chenyang Li, Zhao Song, Zhaoxing Xu, Junze Yin
2024	J	`jnl`	LazyDiT: Lazy Learning for the Acceleration of Diffusion Transformers. CoRR Xuan Shen, Zhao Song, Yufa Zhou, Bo Chen, Yanyu Li, Yifan Gong, Kai Zhang, Hao Tan, Jason Kuen, Henghui Ding, Zhihao Shu, Wei Niu, Pu Zhao, Yanzhi Wang, Jiuxiang Gu
2024	A*	`conf`	Log-concave Sampling from a Convex Body with a Barrier: a Robust and Unified Dikin Walk. NeurIPS Yuzhou Gu, Nikki Lijing Kuang, Yian Ma, Zhao Song, Lichen Zhang
2024	J	`jnl`	Log-concave Sampling over a Convex Body with a Barrier: a Robust and Unified Dikin Walk. CoRR Yuzhou Gu, Nikki Lijing Kuang, Yi-An Ma, Zhao Song, Lichen Zhang
2024	J	`jnl`	Looped ReLU MLPs May Be All You Need as Practical Programmable Computers. CoRR Yingyu Liang, Zhizhou Sha, Zhenmei Shi, Zhao Song, Yufa Zhou
2024	A*	`conf`	Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time. ICLR Yuzhou Gu, Zhao Song, Junze Yin, Lichen Zhang
2024	A*	`conf`	Metric Transforms and Low Rank Representations of Kernels for Fast Attention. NeurIPS Timothy Chu, Josh Alman, Gary L. Miller, Shyam Narayanan, Mark Sellke, Zhao Song
2024	J	`jnl`	Multi-Layer Transformers Gradient Can be Approximated in Almost Linear Time. CoRR Yingyu Liang, Zhizhou Sha, Zhenmei Shi, Zhao Song, Yufa Zhou
2024	J	`jnl`	Numerical Pruning for Efficient Autoregressive Models. CoRR Xuan Shen, Zhao Song, Yufa Zhou, Bo Chen, Jing Liu, Ruiyi Zhang, Ryan A. Rossi, Hao Tan, Tong Yu, Xiang Chen, Yufan Zhou, Tong Sun, Pu Zhao, Yanzhi Wang, Jiuxiang Gu
2024	A*	`conf`	On Computational Limits of Modern Hopfield Models: A Fine-Grained Complexity Analysis. ICML Jerry Yao-Chieh Hu, Thomas Lin, Zhao Song, Han Liu
2024	J	`jnl`	On Computational Limits of Modern Hopfield Models: A Fine-Grained Complexity Analysis. CoRR Jerry Yao-Chieh Hu, Thomas Lin, Zhao Song, Han Liu
2024	A	`conf`	On Convergence of Federated Averaging Langevin Dynamics. UAI Wei Deng, Qian Zhang, Yian Ma, Zhao Song, Guang Lin
2024	J	`jnl`	On Differentially Private String Distances. CoRR Jerry Yao-Chieh Hu, Erzhi Liu, Han Liu, Zhao Song, Lichen Zhang
2024	A*	`conf`	On Socially Fair Low-Rank Approximation and Column Subset Selection. NeurIPS Zhao Song, Ali Vakilian, David P. Woodruff, Samson Zhou
2024	J	`jnl`	On Socially Fair Low-Rank Approximation and Column Subset Selection. CoRR Zhao Song, Ali Vakilian, David P. Woodruff, Samson Zhou
2024	A*	`conf`	On Statistical Rates and Provably Efficient Criteria of Latent Diffusion Transformers (DiTs). NeurIPS Jerry Yao-Chieh Hu, Weimin Wu, Zhuoru Li, Sophia Pi, Zhao Song, Han Liu
2024	J	`jnl`	On Statistical Rates and Provably Efficient Criteria of Latent Diffusion Transformers (DiTs). CoRR Jerry Yao-Chieh Hu, Weimin Wu, Zhuoru Li, Zhao Song, Han Liu
2024	J	`jnl`	On the Expressive Power of Modern Hopfield Networks. CoRR Xiaoyu Li, Yuanpeng Li, Yingyu Liang, Zhenmei Shi, Zhao Song
2024	J	`jnl`	Quantum Speedup for Spectral Approximation of Kronecker Products. CoRR Yeqi Gao, Zhao Song, Ruizhe Zhang
2024	J	`jnl`	Quantum Speedups for Approximating the John Ellipsoid. CoRR Xiaoyu Li, Zhao Song, Junwei Yu
2024	A	`conf`	Solving Attention Kernel Regression Problem via Pre-conditioner. AISTATS Zhao Song, Junze Yin, Lichen Zhang
2024	J	`jnl`	Tensor Attention Training: Provably Efficient Learning of Higher-order Transformers. CoRR Jiuxiang Gu, Yingyu Liang, Zhenmei Shi, Zhao Song, Yufa Zhou
2024	A*	`conf`	The Closeness of In-Context Learning and Weight Shifting for Softmax Regression. NeurIPS Shuai Li, Zhao Song, Yu Xia, Tong Yu, Tianyi Zhou
2024	J	`jnl`	The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexity. CoRR Yifang Chen, Xiaoyu Li, Yingyu Liang, Zhenmei Shi, Zhao Song
2024	A*	`conf`	The Fine-Grained Complexity of Gradient Computation for Training Large Language Models. NeurIPS Josh Alman, Zhao Song
2024	J	`jnl`	The Fine-Grained Complexity of Gradient Computation for Training Large Language Models. CoRR Josh Alman, Zhao Song
2024	J	`jnl`	Theoretical Constraints on the Expressive Power of RoPE-based Tensor Attention Transformers. CoRR Xiaoyu Li, Yingyu Liang, Zhenmei Shi, Zhao Song, Mingda Wan
2024	J	`jnl`	Toward Infinite-Long Prefix in Transformer. CoRR Jiuxiang Gu, Yingyu Liang, Zhenmei Shi, Zhao Song, Chiwun Yang
2024	A	`conf`	Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Time. ITCS Zhao Song, Lichen Zhang, Ruizhe Zhang
2024	J	`jnl`	Transformers are Deep Optimizers: Provable In-Context Learning for Deep Model Training. CoRR Weimin Wu, Maojiang Su, Jerry Yao-Chieh Hu, Zhao Song, Han Liu
2024	J	`jnl`	Unlocking the Theory Behind Scaling 1-Bit Neural Networks. CoRR Majid Daliri, Zhao Song, Chiwun Yang
2024	J	`jnl`	Unraveling the Smoothness Properties of Diffusion Models: A Gaussian Mixture Perspective. CoRR Jiuxiang Gu, Yingyu Liang, Zhenmei Shi, Zhao Song, Yufa Zhou
2024	B	`conf`	Zero-th Order Algorithm for Softmax Attention Optimization. IEEE Big Data Yichuan Deng, Zhihang Li, Sridhar Mahadevan, Zhao Song
2023	J	`jnl`	A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Time. CoRR Yeqi Gao, Zhao Song, Weixin Wang, Junze Yin
2023	J	`jnl`	A General Algorithm for Solving Rank-one Matrix Sensing. CoRR Lianke Qin, Zhao Song, Ruizhe Zhang
2023	J	`jnl`	A Mathematical Abstraction for Balancing the Trade-off Between Creativity and Reality in Large Language Models. CoRR Ritwik Sinha, Zhao Song, Tianyi Zhou
2023	J	`jnl`	A Nearly-Linear Time Algorithm for Structured Support Vector Machines. CoRR Yuzhou Gu, Zhao Song, Lichen Zhang
2023	A*	`conf`	A Nearly-Optimal Bound for Fast Regression with ℓ ICML Zhao Song, Mingquan Ye, Junze Yin, Lichen Zhang
2023	J	`jnl`	A Nearly-Optimal Bound for Fast Regression with 𝓁 CoRR Zhao Song, Mingquan Ye, Junze Yin, Lichen Zhang
2023	A	`conf`	A Tale of Two Efficient Value Iteration Algorithms for Solving Linear MDPs with Large Action Space. AISTATS Zhaozhuo Xu, Zhao Song, Anshumali Shrivastava
2023	J	`jnl`	A Theoretical Analysis Of Nearest Neighbor Search On Approximate Near Neighbor Graph. CoRR Anshumali Shrivastava, Zhao Song, Zhaozhuo Xu
2023	J	`jnl`	A Theoretical Insight into Attack and Defense of Gradient Leakage in Transformer. CoRR Chenyang Li, Zhao Song, Weixin Wang, Chiwun Yang
2023	J	`jnl`	A Unified Scheme of ResNet and Softmax. CoRR Zhao Song, Weixin Wang, Junze Yin
2023	J	`jnl`	Algorithm and Hardness for Dynamic Attention Maintenance in Large Language Models. CoRR Jan van den Brand, Zhao Song, Tianyi Zhou
2023	J	`jnl`	An Automatic Learning Rate Schedule Algorithm for Achieving Faster Convergence and Steeper Descent. CoRR Zhao Song, Chiwun Yang
2023	J	`jnl`	An Improved Sample Complexity for Rank-1 Matrix Sensing. CoRR Yichuan Deng, Zhihang Li, Zhao Song
2023	J	`jnl`	An Iterative Algorithm for Rescaled Hyperbolic Functions Regression. CoRR Yeqi Gao, Zhao Song, Junze Yin
2023	A	`conf`	An Online and Unified Algorithm for Projection Matrix Vector Multiplication with Application to Empirical Risk Minimization. AISTATS Lianke Qin, Zhao Song, Lichen Zhang, Danyang Zhuo
2023	J	`jnl`	An Over-parameterized Exponential Regression. CoRR Yeqi Gao, Sridhar Mahadevan, Zhao Song
2023	J	`jnl`	Attention Scheme Inspired Softmax Regression. CoRR Yichuan Deng, Zhihang Li, Zhao Song
2023	A*	`conf`	Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessing. NeurIPS Josh Alman, Jiehao Liang, Zhao Song, Ruizhe Zhang, Danyang Zhuo
2023	J	`jnl`	Clustered Linear Contextual Bandits with Knapsacks. CoRR Yichuan Deng, Michalis Mamakos, Zhao Song
2023	J	`jnl`	Convergence of Two-Layer Regression with Nonlinear Units. CoRR Yichuan Deng, Zhao Song, Shenghao Xie
2023	J	`jnl`	Convex Minimization with Integer Minima in Õ(n CoRR Haotian Jiang, Yin Tat Lee, Zhao Song, Lichen Zhang
2023	A*	`conf`	Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Time. ICML Zichang Liu, Jue Wang, Tri Dao, Tianyi Zhou, Binhang Yuan, Zhao Song, Anshumali Shrivastava, Ce Zhang, Yuandong Tian, Christopher Ré, Beidi Chen
2023	J	`jnl`	Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Time. CoRR Zichang Liu, Jue Wang, Tri Dao, Tianyi Zhou, Binhang Yuan, Zhao Song, Anshumali Shrivastava, Ce Zhang, Yuandong Tian, Christopher Ré, Beidi Chen
2023	J	`jnl`	Differentially Private Attention Computation. CoRR Yeqi Gao, Zhao Song, Xin Yang
2023	J	`jnl`	Efficient Algorithm for Solving Hyperbolic Programs. CoRR Yichuan Deng, Zhao Song, Lichen Zhang, Ruizhe Zhang
2023	J	`jnl`	Efficient Alternating Minimization with Applications to Weighted Low Rank Approximation. CoRR Zhao Song, Mingquan Ye, Junze Yin, Lichen Zhang
2023	J	`jnl`	Efficient Asynchronize Stochastic Gradient Algorithm with Structured Data. CoRR Zhao Song, Mingquan Ye
2023	J	`jnl`	Efficient SGD Neural Network Training via Sublinear Activated Neuron Identification. CoRR Lianke Qin, Zhao Song, Yuanyuan Yang
2023	A*	`conf`	Exact Representation of Sparse Networks with Symmetric Nonnegative Embeddings. NeurIPS Sudhanshu Chanpuriya, Ryan A. Rossi, Anup B. Rao, Tung Mai, Nedim Lipka, Zhao Song, Cameron Musco
2023	A*	`conf`	Fast Attention Requires Bounded Entries. NeurIPS Josh Alman, Zhao Song
2023	J	`jnl`	Fast Attention Requires Bounded Entries. CoRR Josh Alman, Zhao Song
2023	B	`conf`	Fast Heavy Inner Product Identification Between Weights and Inputs in Neural Network Training. IEEE Big Data Lianke Qin, Saayan Mitra, Zhao Song, Yuanyuan Yang, Tianyi Zhou
2023	J	`jnl`	Fast Heavy Inner Product Identification Between Weights and Inputs in Neural Network Training. CoRR Lianke Qin, Saayan Mitra, Zhao Song, Yuanyuan Yang, Tianyi Zhou
2023	J	`jnl`	Fast Quantum Algorithm for Attention Computation. CoRR Yeqi Gao, Zhao Song, Xin Yang, Ruizhe Zhang
2023	J	`jnl`	Fast Submodular Function Maximization. CoRR Lianke Qin, Zhao Song, Yitan Wang
2023	J	`jnl`	Fast and Efficient Matching Algorithm with Deadline Instances. CoRR Zhao Song, Weixin Wang, Chenbo Yin
2023	J	`jnl`	Faster Robust Tensor Power Method for Arbitrary Order. CoRR Yichuan Deng, Zhao Song, Junze Yin
2023	J	`jnl`	Faster Sinkhorn's Algorithm with Small Treewidth. CoRR Zhao Song, Tianyi Zhou
2023	A*	`conf`	Federated Adversarial Learning: A Framework with Convergence Analysis. ICML Xiaoxiao Li, Zhao Song, Jiaming Yang
2023	J	`jnl`	Federated Empirical Risk Minimization via Second-Order Method. CoRR Song Bian, Zhao Song, Junze Yin
2023	J	`jnl`	Fine-tune Language Models to Approximate Unbiased In-context Learning. CoRR Timothy Chu, Zhao Song, Chiwun Yang
2023	J	`jnl`	GradientCoin: A Peer-to-Peer Decentralized Large Language Models. CoRR Yeqi Gao, Zhao Song, Junze Yin
2023	J	`jnl`	H CoRR Zhenyu Zhang, Ying Sheng, Tianyi Zhou, Tianlong Chen, Lianmin Zheng, Ruisi Cai, Zhao Song, Yuandong Tian, Christopher Ré, Clark W. Barrett, Zhangyang Wang, Beidi Chen
2023	A*	`conf`	H2O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Models. NeurIPS Zhenyu Zhang, Ying Sheng, Tianyi Zhou, Tianlong Chen, Lianmin Zheng, Ruisi Cai, Zhao Song, Yuandong Tian, Christopher Ré, Clark W. Barrett, Zhangyang Wang, Beidi Chen
2023	J	`jnl`	How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computation. CoRR Josh Alman, Zhao Song
2023	J	`jnl`	How to Protect Copyright Data in Optimization of Large Language Models? CoRR Timothy Chu, Zhao Song, Chiwun Yang
2023	J	`jnl`	In-Context Learning for Attention Scheme: from Single Softmax Regression to Multiple Softmax Regression via a Tensor Trick. CoRR Yeqi Gao, Zhao Song, Shenghao Xie
2023	A*	`conf`	InfoPrompt: Information-Theoretic Soft Prompt Tuning for Natural Language Understanding. NeurIPS Junda Wu, Tong Yu, Rui Wang, Zhao Song, Ruiyi Zhang, Handong Zhao, Chaochao Lu, Shuai Li, Ricardo Henao
2023	J	`jnl`	InfoPrompt: Information-Theoretic Soft Prompt Tuning for Natural Language Understanding. CoRR Junda Wu, Tong Yu, Rui Wang, Zhao Song, Ruiyi Zhang, Handong Zhao, Chaochao Lu, Shuai Li, Ricardo Henao
2023	J	`jnl`	Is Solving Graph Neural Tangent Kernel Equivalent to Training Graph Neural Network? CoRR Lianke Qin, Zhao Song, Baocheng Sun
2023	J	`jnl`	Local Convergence of Approximate Newton Method for Two Layer Nonlinear Regression. CoRR Zhihang Li, Zhao Song, Zifan Wang, Junze Yin
2023	J	`jnl`	Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time. CoRR Yuzhou Gu, Zhao Song, Junze Yin, Lichen Zhang
2023	J	`jnl`	One Pass Streaming Algorithm for Super Long Token Attention Approximation in Sublinear Space. CoRR Raghav Addanki, Chenyang Li, Zhao Song, Chiwun Yang
2023	B	`conf`	Online Adaptive Mahalanobis Distance Estimation. IEEE Big Data Lianke Qin, Aravind Reddy, Zhao Song
2023	J	`jnl`	Online Adaptive Mahalanobis Distance Estimation. CoRR Lianke Qin, Aravind Reddy, Zhao Song
2023	A*	`conf`	Quartic Samples Suffice for Fourier Interpolation. FOCS Zhao Song, Baocheng Sun, Omri Weinstein, Ruizhe Zhang
2023	J	`jnl`	Query Complexity of Active Learning for Function Family With Nearly Orthogonal Basis. CoRR Xiang Chen, Zhao Song, Baocheng Sun, Junze Yin, Danyang Zhuo
2023	J	`jnl`	Randomized and Deterministic Attention Sparsification Algorithms for Over-parameterized Feature Dimension. CoRR Yichuan Deng, Sridhar Mahadevan, Zhao Song
2023	J	`jnl`	Revisiting Quantum Algorithms for Linear Regressions: Quadratic Speedups without Data-Dependent Parameters. CoRR Zhao Song, Junze Yin, Ruizhe Zhang
2023	A*	`conf`	Sketching Meets Differential Privacy: Fast Algorithm for Dynamic Kronecker Projection Maintenance. ICML Zhao Song, Xin Yang, Yuanyuan Yang, Lichen Zhang
2023	A*	`conf`	Sketching for First Order Method: Efficient Algorithm for Low-Bandwidth Channel and Vulnerability. ICML Zhao Song, Yitan Wang, Zheng Yu, Lichen Zhang
2023	A*	`conf`	Smoothed Online Combinatorial Optimization Using Imperfect Predictions. AAAI Kai Wang, Zhao Song, Georgios Theocharous, Sridhar Mahadevan
2023	J	`jnl`	Solving Attention Kernel Regression Problem via Pre-conditioner. CoRR Zhao Song, Junze Yin, Lichen Zhang
2023	J	`jnl`	Solving Regularized Exp, Cosh and Sinh Regression Problems. CoRR Zhihang Li, Zhao Song, Tianyi Zhou
2023	B	`conf`	Solving Tensor Low Cycle Rank Approximation. IEEE Big Data Yichuan Deng, Yeqi Gao, Zhao Song
2023	J	`jnl`	Solving Tensor Low Cycle Rank Approximation. CoRR Yichuan Deng, Yeqi Gao, Zhao Song
2023	A*	`conf`	Space-Efficient Interior Point Method, with Applications to Linear Programming and Maximum Weight Bipartite Matching. ICALP S. Cliff Liu, Zhao Song, Hengjie Zhang, Lichen Zhang, Tianyi Zhou
2023	J	`jnl`	Sparse Convolution for Approximate Sparse Instance. CoRR Xiaoxiao Li, Zhao Song, Guangyi Zhang
2023	J	`jnl`	Streaming Kernel PCA Algorithm With Small Space. CoRR Yichuan Deng, Zhao Song, Zifan Wang, Han Zhang
2023	J	`jnl`	Streaming Semidefinite Programs: O(√n) Passes, Small Space and Fast Runtime. CoRR Zhao Song, Mingquan Ye, Lichen Zhang
2023	A*	`conf`	Super-resolution and Robust Sparse Continuous Fourier Transform in Any Constant Dimension: Nearly Linear Time and Sample Complexity. SODA Yaonan Jin, Daogao Liu, Zhao Song
2023	J	`jnl`	Superiority of Softmax: Unveiling the Performance Edge Over Linear Attention. CoRR Yichuan Deng, Zhao Song, Tianyi Zhou
2023	J	`jnl`	The Closeness of In-Context Learning and Weight Shifting for Softmax Regression. CoRR Shuai Li, Zhao Song, Yu Xia, Tong Yu, Tianyi Zhou
2023	J	`jnl`	The Expressibility of Polynomial based Attention Scheme. CoRR Zhao Song, Guangyi Xu, Junze Yin
2023	A*	`conf`	Towards Multi-Pass Streaming Lower Bounds for Optimal Approximation of Max-Cut. SODA Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena, Zhao Song, Huacheng Yu
2023	J	`jnl`	Unmasking Transformers: A Theoretical Approach to Data Recovery via Attention Weights. CoRR Yichuan Deng, Zhao Song, Shenghao Xie, Chiwun Yang
2023	J	`jnl`	Zero-th Order Algorithm for Softmax Attention Optimization. CoRR Yichuan Deng, Zhihang Li, Sridhar Mahadevan, Zhao Song
2022	B	`conf`	A Convergence Theory for Federated Average: Beyond Smoothness. IEEE Big Data Xiaoxiao Li, Zhao Song, Runzhou Tao, Guangyi Zhang
2022	J	`jnl`	A Convergence Theory for Federated Average: Beyond Smoothness. CoRR Xiaoxiao Li, Zhao Song, Runzhou Tao, Guangyi Zhang
2022	J	`jnl`	A Dynamic Fast Gaussian Transform. CoRR Baihe Huang, Zhao Song, Omri Weinstein, Hengjie Zhang, Ruizhe Zhang
2022	J	`jnl`	A Faster Small Treewidth SDP Solver. CoRR Yuzhou Gu, Zhao Song
2022	J	`jnl`	A Faster k-means++ Algorithm. CoRR Jiehao Liang, Somdeb Sarkhel, Zhao Song, Chenbo Yin, Danyang Zhuo
2022	J	`jnl`	A Nearly Optimal Size Coreset Algorithm with Nearly Linear Time. CoRR Yichuan Deng, Zhao Song, Yitan Wang, Yuanyuan Yang
2022	J	`jnl`	A Sublinear Adversarial Training Algorithm. CoRR Yeqi Gao, Lianke Qin, Zhao Song, Yitan Wang
2022	J	`jnl`	Accelerating Frank-Wolfe Algorithm using Low-Dimensional and Adaptive Data Structures. CoRR Zhao Song, Zhaozhuo Xu, Yuanyuan Yang, Lichen Zhang
2022	B	`conf`	Adaptive and Dynamic Multi-Resolution Hashing for Pairwise Summations. IEEE Big Data Lianke Qin, Aravind Reddy, Zhao Song, Zhaozhuo Xu, Danyang Zhuo
2022	J	`jnl`	Adaptive and Dynamic Multi-Resolution Hashing for Pairwise Summations. CoRR Lianke Qin, Aravind Reddy, Zhao Song, Zhaozhuo Xu, Danyang Zhuo
2022	J	`jnl`	Adore: Differentially Oblivious Relational Database Operators. CoRR Lianke Qin, Rajesh Jayaram, Elaine Shi, Zhao Song, Danyang Zhuo, Shumo Chu
2022	J	`jnl`	An O(k log n) Time Fourier Set Query Algorithm. CoRR Yeqi Gao, Zhao Song, Baocheng Sun
2022	J	`jnl`	An improved quantum-inspired algorithm for linear regression. Quantum András Gilyén, Zhao Song, Ewin Tang
2022	J	`jnl`	Bounding the Width of Neural Networks via Coupled Initialization - A Worst Case Analysis. CoRR Alexander Munteanu, Simon Omlor, Zhao Song, David P. Woodruff
2022	A*	`conf`	Bounding the Width of Neural Networks via Coupled Initialization A Worst Case Analysis. ICML Alexander Munteanu, Simon Omlor, Zhao Song, David P. Woodruff
2022	J	`jnl`	Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessing. CoRR Josh Alman, Jiehao Liang, Zhao Song, Ruizhe Zhang, Danyang Zhuo
2022	J	`jnl`	Differentially Oblivious Relational Database Operators. Proc. VLDB Endow. Lianke Qin, Rajesh Jayaram, Elaine Shi, Zhao Song, Danyang Zhuo, Shumo Chu
2022	J	`jnl`	Discrepancy Minimization in Input-Sparsity Time. CoRR Yichuan Deng, Zhao Song, Omri Weinstein
2022	J	`jnl`	Dynamic Kernel Sparsifiers. CoRR Yichuan Deng, Wenyu Jin, Zhao Song, Xiaorui Sun, Omri Weinstein
2022	J	`jnl`	Dynamic Maintenance of Kernel Density Estimation Data Structure: From Practice to Theory. CoRR Jiehao Liang, Zhao Song, Zhaozhuo Xu, Danyang Zhuo
2022	A*	`conf`	Dynamic Tensor Product Regression. NeurIPS Aravind Reddy, Zhao Song, Lichen Zhang
2022	J	`jnl`	Dynamic Tensor Product Regression. CoRR Aravind Reddy, Zhao Song, Lichen Zhang
2022	A*	`conf`	Fast Distance Oracles for Any Symmetric Norm. NeurIPS Yichuan Deng, Zhao Song, Omri Weinstein, Ruizhe Zhang
2022	J	`jnl`	Fast Distance Oracles for Any Symmetric Norm. CoRR Yichuan Deng, Zhao Song, Omri Weinstein, Ruizhe Zhang
2022	A*	`conf`	Fast Graph Neural Tangent Kernel via Kronecker Sketching. AAAI Shunhua Jiang, Yunze Man, Zhao Song, Zheng Yu, Danyang Zhuo
2022	J	`jnl`	Faster Algorithm for Structured John Ellipsoid Computation. CoRR Zhao Song, Xin Yang, Yuanyuan Yang, Tianyi Zhou
2022	J	`jnl`	Federated Adversarial Learning: A Framework with Convergence Analysis. CoRR Xiaoxiao Li, Zhao Song, Jiaming Yang
2022	A	`conf`	Hyperbolic Concentration, Anti-Concentration, and Discrepancy. APPROX/RANDOM Zhao Song, Ruizhe Zhang
2022	A*	`conf`	One-Pass Algorithms for MAP Inference of Nonsymmetric Determinantal Point Processes. ICML Aravind Reddy, Ryan A. Rossi, Zhao Song, Anup B. Rao, Tung Mai, Nedim Lipka, Gang Wu, Eunyee Koh, Nesreen K. Ahmed
2022	A*	`conf`	Perfectly Balanced: Improving Transfer and Robustness of Supervised Contrastive Learning. ICML Mayee F. Chen, Daniel Y. Fu, Avanika Narayan, Michael Zhang, Zhao Song, Kayvon Fatahalian, Christopher Ré
2022	J	`jnl`	Perfectly Balanced: Improving Transfer and Robustness of Supervised Contrastive Learning. CoRR Mayee F. Chen, Daniel Y. Fu, Avanika Narayan, Michael Zhang, Zhao Song, Kayvon Fatahalian, Christopher Ré
2022	A*	`conf`	Pixelated Butterfly: Simple and Efficient Sparse training for Neural Network Models. ICLR Beidi Chen, Tri Dao, Kaizhao Liang, Jiaming Yang, Zhao Song, Atri Rudra, Christopher Ré
2022	J	`jnl`	Quartic Samples Suffice for Fourier Interpolation. CoRR Zhao Song, Baocheng Sun, Omri Weinstein, Ruizhe Zhang
2022	J	`jnl`	Sketching Meets Differential Privacy: Fast Algorithm for Dynamic Kronecker Projection Maintenance. CoRR Zhao Song, Xin Yang, Yuanyuan Yang, Lichen Zhang
2022	J	`jnl`	Sketching for First Order Method: Efficient Algorithm for Low-Bandwidth Channel and Vulnerability. CoRR Zhao Song, Yitan Wang, Zheng Yu, Lichen Zhang
2022	J	`jnl`	Smoothed Online Combinatorial Optimization Using Imperfect Predictions. CoRR Kai Wang, Zhao Song, Georgios Theocharous, Sridhar Mahadevan
2022	A*	`conf`	Solving SDP Faster: A Robust IPM Framework and Efficient Implementation. FOCS Baihe Huang, Shunhua Jiang, Zhao Song, Runzhou Tao, Ruizhe Zhang
2022	J	`jnl`	Sparse Fourier Transform over Lattices: A Unified Approach to Signal Reconstruction. CoRR Zhao Song, Baocheng Sun, Omri Weinstein, Ruizhe Zhang
2022	J	`jnl`	Speeding Up Sparsification using Inner Product Search Data Structures. CoRR Zhao Song, Zhaozhuo Xu, Lichen Zhang
2022	J	`jnl`	Sublinear Time Algorithm for Online Weighted Bipartite Matching. CoRR Hang Hu, Zhao Song, Runzhou Tao, Zhaozhuo Xu, Danyang Zhuo
2022	A	`conf`	Symmetric Sparse Boolean Matrix Factorization and Applications. ITCS Sitan Chen, Zhao Song, Runzhou Tao, Ruizhe Zhang
2022	J	`jnl`	Towards Multi-Pass Streaming Lower Bounds for Optimal Approximation of Max-Cut. Electron. Colloquium Comput. Complex. Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Zhao Song, Huacheng Yu
2022	J	`jnl`	Training Overparametrized Neural Networks in Sublinear Time. CoRR Hang Hu, Zhao Song, Omri Weinstein, Danyang Zhuo
2021	A*	`conf`	A faster algorithm for solving general LPs. STOC Shunhua Jiang, Zhao Song, Omri Weinstein, Hengjie Zhang
2021	J	`jnl`	Almost Optimal Super-Constant-Pass Streaming Lower Bounds for Reachability. Electron. Colloquium Comput. Complex. Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Zhao Song, Huacheng Yu
2021	A*	`conf`	Almost optimal super-constant-pass streaming lower bounds for reachability. STOC Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena, Zhao Song, Huacheng Yu
2021	J	`jnl`	An Interpretable Graph Generative Model with Heterophily. CoRR Sudhanshu Chanpuriya, Ryan A. Rossi, Anup B. Rao, Tung Mai, Nedim Lipka, Zhao Song, Cameron Musco
2021	J	`jnl`	Approximation Algorithms for LCS and LIS with Truly Improved Running Times. CoRR Aviad Rubinstein, Saeed Seddighin, Zhao Song, Xiaorui Sun
2021	A*	`conf`	Breaking the Linear Iteration Cost Barrier for Some Well-known Conditional Gradient Methods Using MaxIP Data-structures. NeurIPS Zhaozhuo Xu, Zhao Song, Anshumali Shrivastava
2021	J	`jnl`	Breaking the Linear Iteration Cost Barrier for Some Well-known Conditional Gradient Methods Using MaxIP Data-structures. CoRR Anshumali Shrivastava, Zhao Song, Zhaozhuo Xu
2021	A*	`conf`	Does Preprocessing Help Training Over-parameterized Neural Networks? NeurIPS Zhao Song, Shuo Yang, Ruizhe Zhang
2021	J	`jnl`	Does Preprocessing Help Training Over-parameterized Neural Networks? CoRR Zhao Song, Shuo Yang, Ruizhe Zhang
2021	A*	`conf`	Evaluating Gradient Inversion Attacks and Defenses in Federated Learning. NeurIPS Yangsibo Huang, Samyak Gupta, Zhao Song, Kai Li, Sanjeev Arora
2021	J	`jnl`	Evaluating Gradient Inversion Attacks and Defenses in Federated Learning. CoRR Yangsibo Huang, Samyak Gupta, Zhao Song, Kai Li, Sanjeev Arora
2021	A*	`conf`	FL-NTK: A Neural Tangent Kernel-based Framework for Federated Learning Analysis. ICML Baihe Huang, Xiaoxiao Li, Zhao Song, Xin Yang
2021	J	`jnl`	FL-NTK: A Neural Tangent Kernel-based Framework for Federated Learning Convergence Analysis. CoRR Baihe Huang, Xiaoxiao Li, Zhao Song, Xin Yang
2021	J	`jnl`	Fast Graph Neural Tangent Kernel via Kronecker Sketching. CoRR Shunhua Jiang, Yunze Man, Zhao Song, Zheng Yu, Danyang Zhuo
2021	A*	`conf`	Fast Sketching of Polynomial Kernels of Polynomial Degree. ICML Zhao Song, David P. Woodruff, Zheng Yu, Lichen Zhang
2021	J	`jnl`	Fast Sketching of Polynomial Kernels of Polynomial Degree. CoRR Zhao Song, David P. Woodruff, Zheng Yu, Lichen Zhang
2021	A*	`conf`	MONGOOSE: A Learnable LSH Framework for Efficient Neural Network Training. ICLR Beidi Chen, Zichang Liu, Binghui Peng, Zhaozhuo Xu, Jonathan Lingjie Li, Tri Dao, Zhao Song, Anshumali Shrivastava, Christopher Ré
2021	J	`jnl`	Minimum Cost Flows, MDPs, and 𝓁 CoRR Jan van den Brand, Yin Tat Lee, Yang P. Liu, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, Di Wang
2021	A*	`conf`	Minimum cost flows, MDPs, and ℓ STOC Jan van den Brand, Yin Tat Lee, Yang P. Liu, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, Di Wang
2021	A*	`conf`	Near-Optimal Two-Pass Streaming Algorithm for Sampling Random Walks over Directed Graphs. ICALP Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena, Zhao Song, Huacheng Yu
2021	J	`jnl`	Near-Optimal Two-Pass Streaming Algorithm for Sampling Random Walks over Directed Graphs. CoRR Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Zhao Song, Huacheng Yu
2021	A*	`conf`	Oblivious Sketching-based Central Path Method for Linear Programming. ICML Zhao Song, Zheng Yu
2021	J	`jnl`	On Convergence of Federated Averaging Langevin Dynamics. CoRR Wei Deng, Yi-An Ma, Zhao Song, Qian Zhang, Guang Lin
2021	A*	`conf`	On InstaHide, Phase Retrieval, and Sparse Matrix Factorization. ICLR Sitan Chen, Xiaoxiao Li, Zhao Song, Danyang Zhuo
2021	J	`jnl`	Online MAP Inference and Learning for Nonsymmetric Determinantal Point Processes. CoRR Aravind Reddy, Ryan A. Rossi, Zhao Song, Anup B. Rao, Tung Mai, Nedim Lipka, Gang Wu, Eunyee Koh, Nesreen K. Ahmed
2021	J	`jnl`	Pixelated Butterfly: Simple and Efficient Sparse training for Neural Network Models. CoRR Beidi Chen, Tri Dao, Kaizhao Liang, Jiaming Yang, Zhao Song, Atri Rudra, Christopher Ré
2021	J	`jnl`	Scatterbrain: Unifying Sparse and Low-rank Attention Approximation. CoRR Beidi Chen, Tri Dao, Eric Winsor, Zhao Song, Atri Rudra, Christopher Ré
2021	A*	`conf`	Scatterbrain: Unifying Sparse and Low-rank Attention. NeurIPS Beidi Chen, Tri Dao, Eric Winsor, Zhao Song, Atri Rudra, Christopher Ré
2021	J	`jnl`	Solving Linear Programs in the Current Matrix Multiplication Time. J. ACM Michael B. Cohen, Yin Tat Lee, Zhao Song
2021	J	`jnl`	Solving Tall Dense SDPs in the Current Matrix Multiplication Time. CoRR Baihe Huang, Shunhua Jiang, Zhao Song, Runzhou Tao
2021	J	`jnl`	Sublinear Least-Squares Value Iteration via Locality Sensitive Hashing. CoRR Anshumali Shrivastava, Zhao Song, Zhaozhuo Xu
2021	J	`jnl`	Symmetric Boolean Factor Analysis with Applications to InstaHide. CoRR Sitan Chen, Zhao Song, Runzhou Tao, Ruizhe Zhang
2021	A	`conf`	Training (Overparametrized) Neural Networks in Near-Linear Time. ITCS Jan van den Brand, Binghui Peng, Zhao Song, Omri Weinstein
2021	J	`jnl`	Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Time. CoRR Zhao Song, Lichen Zhang, Ruizhe Zhang
2021	A	`conf`	When is particle filtering efficient for planning in partially observed linear dynamical systems? UAI Simon S. Du, Wei Hu, Zhiyuan Li, Ruoqi Shen, Zhao Song, Jiajun Wu
2020	A*	`conf`	A Faster Interior Point Method for Semidefinite Programming. FOCS Haotian Jiang, Tarun Kathuria, Yin Tat Lee, Swati Padmanabhan, Zhao Song
2020	J	`jnl`	A Faster Interior Point Method for Semidefinite Programming. CoRR Haotian Jiang, Tarun Kathuria, Yin Tat Lee, Swati Padmanabhan, Zhao Song
2020	J	`jnl`	A robust multi-dimensional sparse Fourier transform in the continuous setting. CoRR Yaonan Jin, Daogao Liu, Zhao Song
2020	A*	`conf`	Algorithms and Hardness for Linear Algebra on Geometric Graphs. FOCS Josh Alman, Timothy Chu, Aaron Schild, Zhao Song
2020	J	`jnl`	Algorithms and Hardness for Linear Algebra on Geometric Graphs. CoRR Josh Alman, Timothy Chu, Aaron Schild, Zhao Song
2020	J	`jnl`	An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applications. CoRR Haotian Jiang, Yin Tat Lee, Zhao Song, Sam Chiu-wai Wong
2020	A*	`conf`	An improved cutting plane method for convex optimization, convex-concave games, and its applications. STOC Haotian Jiang, Yin Tat Lee, Zhao Song, Sam Chiu-wai Wong
2020	J	`jnl`	An improved quantum-inspired algorithm for linear regression. CoRR András Gilyén, Zhao Song, Ewin Tang
2020	J	`jnl`	Average Case Column Subset Selection for Entrywise 𝓁 CoRR Zhao Song, David P. Woodruff, Peilin Zhong
2020	A*	`conf`	Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs. FOCS Jan van den Brand, Yin Tat Lee, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, Di Wang
2020	J	`jnl`	Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs. CoRR Jan van den Brand, Yin Tat Lee, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, Di Wang
2020	J	`jnl`	Faster Dynamic Matrix Inverse for Faster LPs. CoRR Shunhua Jiang, Zhao Song, Omri Weinstein, Hengjie Zhang
2020	A*	`conf`	Generalized Leverage Score Sampling for Neural Networks. NeurIPS Jason D. Lee, Ruoqi Shen, Zhao Song, Mengdi Wang, Zheng Yu
2020	J	`jnl`	Generalized Leverage Score Sampling for Neural Networks. CoRR Jason D. Lee, Ruoqi Shen, Zhao Song, Mengdi Wang, Zheng Yu
2020	J	`jnl`	Hyperbolic Polynomials I : Concentration and Discrepancy. CoRR Zhao Song, Ruizhe Zhang
2020	J	`jnl`	InstaHide's Sample Complexity When Mixing Two Private Images. CoRR Baihe Huang, Zhao Song, Runzhou Tao, Ruizhe Zhang, Danyang Zhuo
2020	A*	`conf`	InstaHide: Instance-hiding Schemes for Private Distributed Learning. ICML Yangsibo Huang, Zhao Song, Kai Li, Sanjeev Arora
2020	J	`jnl`	InstaHide: Instance-hiding Schemes for Private Distributed Learning. CoRR Yangsibo Huang, Zhao Song, Kai Li, Sanjeev Arora
2020	A*	`conf`	Learning mixtures of linear regressions in subexponential time via Fourier moments. STOC Sitan Chen, Jerry Li, Zhao Song
2020	A*	`conf`	Meta-learning for Mixed Linear Regression. ICML Weihao Kong, Raghav Somani, Zhao Song, Sham M. Kakade, Sewoong Oh
2020	J	`jnl`	Meta-learning for mixed linear regression. CoRR Weihao Kong, Raghav Somani, Zhao Song, Sham M. Kakade, Sewoong Oh
2020	J	`jnl`	MixCon: Adjusting the Separability of Data Representations for Harder Data Recovery. CoRR Xiaoxiao Li, Yangsibo Huang, Binghui Peng, Zhao Song, Kai Li
2020	J	`jnl`	On InstaHide, Phase Retrieval, and Sparse Matrix Factorization. CoRR Sitan Chen, Zhao Song, Danyang Zhuo
2020	A*	`conf`	Over-parameterized Adversarial Training: An Analysis Overcoming the Curse of Dimensionality. NeurIPS Yi Zhang, Orestis Plevrakis, Simon S. Du, Xingguo Li, Zhao Song, Sanjeev Arora
2020	J	`jnl`	Over-parameterized Adversarial Training: An Analysis Overcoming the Curse of Dimensionality. CoRR Yi Zhang, Orestis Plevrakis, Simon S. Du, Xingguo Li, Zhao Song, Sanjeev Arora
2020	J	`jnl`	Privacy-preserving Learning via Deep Net Pruning. CoRR Yangsibo Huang, Yushan Su, Sachin Ravi, Zhao Song, Sanjeev Arora, Kai Li
2020	A*	`conf`	Reducing approximate Longest Common Subsequence to approximate Edit Distance. SODA Aviad Rubinstein, Zhao Song
2020	A	`conf`	Sketching Transformed Matrices with Applications to Natural Language Processing. AISTATS Yingyu Liang, Zhao Song, Mengdi Wang, Lin Yang, Xin Yang
2020	J	`jnl`	Sketching Transformed Matrices with Applications to Natural Language Processing. CoRR Yingyu Liang, Zhao Song, Mengdi Wang, Lin F. Yang, Xin Yang
2020	J	`jnl`	Solving Tall Dense Linear Programs in Nearly Linear Time. CoRR Jan van den Brand, Yin Tat Lee, Aaron Sidford, Zhao Song
2020	A*	`conf`	Solving tall dense linear programs in nearly linear time. STOC Jan van den Brand, Yin Tat Lee, Aaron Sidford, Zhao Song
2020	J	`jnl`	Space-Efficient Interior Point Method, with applications to Linear Programming and Maximum Weight Bipartite Matching. CoRR S. Cliff Liu, Zhao Song, Hengjie Zhang, Lichen Zhang, Tianyi Zhou
2020	—	`conf`	TextHide: Tackling Data Privacy for Language Understanding Tasks. EMNLP (Findings) Yangsibo Huang, Zhao Song, Danqi Chen, Kai Li, Sanjeev Arora
2020	J	`jnl`	TextHide: Tackling Data Privacy in Language Understanding Tasks. CoRR Yangsibo Huang, Zhao Song, Danqi Chen, Kai Li, Sanjeev Arora
2020	J	`jnl`	Training (Overparametrized) Neural Networks in Near-Linear Time. CoRR Jan van den Brand, Binghui Peng, Zhao Song, Omri Weinstein
2020	J	`jnl`	When is Particle Filtering Efficient for POMDP Sequential Planning? CoRR Simon S. Du, Wei Hu, Zhiyuan Li, Ruoqi Shen, Zhao Song, Jiajun Wu
2019	A*	`conf`	(Nearly) Sample-Optimal Sparse Fourier Transform in Any Dimension; RIPless and Filterless. FOCS Vasileios Nakos, Zhao Song, Zhengyu Wang
2019	J	`jnl`	(Nearly) Sample-Optimal Sparse Fourier Transform in Any Dimension; RIPless and Filterless. CoRR Vasileios Nakos, Zhao Song, Zhengyu Wang
2019	A*	`conf`	A Convergence Theory for Deep Learning via Over-Parameterization. ICML Zeyuan Allen-Zhu, Yuanzhi Li, Zhao Song
2019	A*	`conf`	Approximation Algorithms for LCS and LIS with Truly Improved Running Times. FOCS Aviad Rubinstein, Saeed Seddighin, Zhao Song, Xiaorui Sun
2019	A*	`conf`	Average Case Column Subset Selection for Entrywise 퓁 NeurIPS Zhao Song, David P. Woodruff, Peilin Zhong
2019	J	`jnl`	Efficient Model-free Reinforcement Learning in Metric Spaces. CoRR Zhao Song, Wen Sun
2019	A*	`conf`	Efficient Symmetric Norm Regression via Linear Sketching. NeurIPS Zhao Song, Ruosong Wang, Lin F. Yang, Hongyang Zhang, Peilin Zhong
2019	J	`jnl`	Efficient Symmetric Norm Regression via Linear Sketching. CoRR Zhao Song, Ruosong Wang, Lin F. Yang, Hongyang Zhang, Peilin Zhong
2019	J	`jnl`	Four Deviations Suffice for Rank 1 Matrices. CoRR Rasmus Kyng, Kyle Luh, Zhao Song
2019	J	`jnl`	Learning Mixtures of Linear Regressions in Subexponential Time via Fourier Moments. CoRR Sitan Chen, Jerry Li, Zhao Song
2019	J	`jnl`	Non-Convex Matrix Completion and Related Problems via Strong Duality. J. Mach. Learn. Res. Maria-Florina Balcan, Yingyu Liang, Zhao Song, David P. Woodruff, Hongyang Zhang
2019	A*	`conf`	On the Convergence Rate of Training Recurrent Neural Networks. NeurIPS Zeyuan Allen-Zhu, Yuanzhi Li, Zhao Song
2019	A*	`conf`	Optimal Sketching for Kronecker Product Regression and Low Rank Approximation. NeurIPS Huaian Diao, Rajesh Jayaram, Zhao Song, Wen Sun, David P. Woodruff
2019	J	`jnl`	Optimal Sketching for Kronecker Product Regression and Low Rank Approximation. CoRR Huaian Diao, Rajesh Jayaram, Zhao Song, Wen Sun, David P. Woodruff
2019	A*	`conf`	Provable Non-linear Inductive Matrix Completion. NeurIPS Kai Zhong, Zhao Song, Prateek Jain, Inderjit S. Dhillon
2019	J	`jnl`	Quadratic Suffices for Over-parametrization via Matrix Chernoff Bound. CoRR Zhao Song, Xin Yang
2019	J	`jnl`	Reducing approximate Longest Common Subsequence to approximate Edit Distance. CoRR Aviad Rubinstein, Zhao Song
2019	A*	`conf`	Relative Error Tensor Low Rank Approximation. SODA Zhao Song, David P. Woodruff, Peilin Zhong
2019	A*	`conf`	Solving Empirical Risk Minimization in the Current Matrix Multiplication Time. COLT Yin Tat Lee, Zhao Song, Qiuyi Zhang
2019	J	`jnl`	Solving Empirical Risk Minimization in the Current Matrix Multiplication Time. CoRR Yin Tat Lee, Zhao Song, Qiuyi Zhang
2019	A*	`conf`	Solving linear programs in the current matrix multiplication time. STOC Michael B. Cohen, Yin Tat Lee, Zhao Song
2019	J	`jnl`	Stronger L2/L2 Compressed Sensing; Without Iterating. CoRR Vasileios Nakos, Zhao Song
2019	A*	`conf`	Stronger l STOC Vasileios Nakos, Zhao Song
2019	—	`conf`	The Limitations of Adversarial Training and the Blind-Spot Attack. ICLR (Poster) Huan Zhang, Hongge Chen, Zhao Song, Duane S. Boning, Inderjit S. Dhillon, Cho-Jui Hsieh
2019	J	`jnl`	The Limitations of Adversarial Training and the Blind-Spot Attack. CoRR Huan Zhang, Hongge Chen, Zhao Song, Duane S. Boning, Inderjit S. Dhillon, Cho-Jui Hsieh
2019	A*	`conf`	Total Least Squares Regression in Input Sparsity Time. NeurIPS Huaian Diao, Zhao Song, David P. Woodruff, Xin Yang
2019	J	`jnl`	Total Least Squares Regression in Input Sparsity Time. CoRR Huaian Diao, Zhao Song, David P. Woodruff, Xin Yang
2019	A	`conf`	Towards a Theoretical Understanding of Hashing-Based Neural Nets. AISTATS Yibo Lin, Zhao Song, Lin F. Yang
2019	A*	`conf`	Towards a Zero-One Law for Column Subset Selection. NeurIPS Zhao Song, David P. Woodruff, Peilin Zhong
2018	J	`jnl`	A Convergence Theory for Deep Learning via Over-Parameterization. CoRR Zeyuan Allen-Zhu, Yuanzhi Li, Zhao Song
2018	A*	`conf`	A Matrix Chernoff Bound for Strongly Rayleigh Distributions and Spectral Sparsifiers from a few Random Spanning Trees. FOCS Rasmus Kyng, Zhao Song
2018	J	`jnl`	A Matrix Chernoff Bound for Strongly Rayleigh Distributions and Spectral Sparsifiers from a few Random Spanning Trees. CoRR Rasmus Kyng, Zhao Song
2018	A*	`conf`	A matrix expander Chernoff bound. STOC Ankit Garg, Yin Tat Lee, Zhao Song, Nikhil Srivastava
2018	J	`jnl`	Algorithmic Theory of ODEs and Sampling from Well-conditioned Logconcave Densities. CoRR Yin Tat Lee, Zhao Song, Santosh S. Vempala
2018	A*	`conf`	Learning Long Term Dependencies via Fourier Recurrent Units. ICML Jiong Zhang, Yibo Lin, Zhao Song, Inderjit S. Dhillon
2018	J	`jnl`	Learning Long Term Dependencies via Fourier Recurrent Units. CoRR Jiong Zhang, Yibo Lin, Zhao Song, Inderjit S. Dhillon
2018	J	`jnl`	Nonlinear Inductive Matrix Completion based on One-layer Neural Networks. CoRR Kai Zhong, Zhao Song, Prateek Jain, Inderjit S. Dhillon
2018	J	`jnl`	On the Convergence Rate of Training Recurrent Neural Networks. CoRR Zeyuan Allen-Zhu, Yuanzhi Li, Zhao Song
2018	J	`jnl`	Optimizing squares covering a set of points. Theor. Comput. Sci. Sergey Bereg, Binay Bhattacharya, Sandip Das, Tsunehiko Kameda, Priya Ranjan Sinha Mahapatra, Zhao Song
2018	A*	`conf`	Parallel Graph Connectivity in Log Diameter Rounds. FOCS Alexandr Andoni, Zhao Song, Clifford Stein, Zhengyu Wang, Peilin Zhong
2018	J	`jnl`	Parallel Graph Connectivity in Log Diameter Rounds. CoRR Alexandr Andoni, Clifford Stein, Zhao Song, Zhengyu Wang, Peilin Zhong
2018	J	`jnl`	Relative Error Tensor Low Rank Approximation. Electron. Colloquium Comput. Complex. Zhao Song, David P. Woodruff, Peilin Zhong
2018	J	`jnl`	Sensitivity Sampling Over Dynamic Geometric Data Streams with Applications to k-Clustering. CoRR Zhao Song, Lin F. Yang, Peilin Zhong
2018	A	`conf`	Sketching for Kronecker Product Regression and P-splines. AISTATS Huaian Diao, Zhao Song, Wen Sun, David P. Woodruff
2018	J	`jnl`	Solving Linear Programs in the Current Matrix Multiplication Time. CoRR Michael B. Cohen, Yin Tat Lee, Zhao Song
2018	A	`conf`	Stochastic Multi-armed Bandits in Constant Space. AISTATS David Liau, Zhao Song, Eric Price, Ger Yang
2018	—	`ch.`	Topic Modeling in Online Social Media, User Features and Social Networks for. Encyclopedia of Social Network Analysis and Mining. 2nd Ed. Bo Hu, Zhao Song, Martin Ester
2018	A*	`conf`	Towards Fast Computation of Certified Robustness for ReLU Networks. ICML Tsui-Wei Weng, Huan Zhang, Hongge Chen, Zhao Song, Cho-Jui Hsieh, Luca Daniel, Duane S. Boning, Inderjit S. Dhillon
2018	J	`jnl`	Towards Fast Computation of Certified Robustness for ReLU Networks. CoRR Tsui-Wei Weng, Huan Zhang, Hongge Chen, Zhao Song, Cho-Jui Hsieh, Duane S. Boning, Inderjit S. Dhillon, Luca Daniel
2018	J	`jnl`	Towards a Theoretical Understanding of Hashing-Based Neural Nets. CoRR Yibo Lin, Zhao Song, Lin F. Yang
2018	J	`jnl`	Towards a Zero-One Law for Entrywise Low Rank Approximation. CoRR Zhao Song, David P. Woodruff, Peilin Zhong
2017	J	`jnl`	Fast Regression with an $\ell_\infty$ Guarantee. CoRR Eric Price, Zhao Song, David P. Woodruff
2017	A*	`conf`	Fast Regression with an $ell_infty$ Guarantee. ICALP Eric Price, Zhao Song, David P. Woodruff
2017	J	`jnl`	Learning Non-overlapping Convolutional Neural Networks with Multiple Kernels. CoRR Kai Zhong, Zhao Song, Inderjit S. Dhillon
2017	A*	`conf`	Low rank approximation with entrywise l STOC Zhao Song, David P. Woodruff, Peilin Zhong
2017	A*	`conf`	Recovery Guarantees for One-hidden-layer Neural Networks. ICML Kai Zhong, Zhao Song, Prateek Jain, Peter L. Bartlett, Inderjit S. Dhillon
2017	J	`jnl`	Recovery Guarantees for One-hidden-layer Neural Networks. CoRR Kai Zhong, Zhao Song, Prateek Jain, Peter L. Bartlett, Inderjit S. Dhillon
2017	J	`jnl`	Relative Error Tensor Low Rank Approximation. CoRR Zhao Song, David P. Woodruff, Peilin Zhong
2017	J	`jnl`	Sketching for Kronecker Product Regression and P-splines. CoRR Huaian Diao, Zhao Song, Wen Sun, David P. Woodruff
2017	J	`jnl`	Stochastic Multi-armed Bandits in Constant Space. CoRR David Liau, Eric Price, Zhao Song, Ger Yang
2016	J	`jnl`	A Robust Sparse Fourier Transform in the Continuous Setting. CoRR Eric Price, Zhao Song
2016	J	`jnl`	Batch Codes Through Dense Graphs Without Short Cycles. IEEE Trans. Inf. Theory Ankit Singh Rawat, Zhao Song, Alexandros G. Dimakis, Anna Gál
2016	A*	`conf`	Fourier-Sparse Interpolation without a Frequency Gap. FOCS Xue Chen, Daniel M. Kane, Eric Price, Zhao Song
2016	J	`jnl`	Fourier-sparse interpolation without a frequency gap. CoRR Xue Chen, Daniel M. Kane, Eric Price, Zhao Song
2016	J	`jnl`	Low Rank Approximation with Entrywise ℓ CoRR Zhao Song, David P. Woodruff, Peilin Zhong
2016	A*	`conf`	Maximum Sustainable Yield Problem for Robot Foraging and Construction System. IJCAI Ruohan Zhang, Zhao Song
2016	—	`conf`	Sublinear Time Orthogonal Tensor Decomposition. NIPS Zhao Song, David P. Woodruff, Huan Zhang
2016	J	`jnl`	The $p$-Center Problem in Tree Networks Revisited. CoRR Aritra Banik, Binay K. Bhattacharya, Sandip Das, Tsunehiko Kameda, Zhao Song
2016	—	`conf`	The p-Center Problem in Tree Networks Revisited. SWAT Aritra Banik, Binay K. Bhattacharya, Sandip Das, Tsunehiko Kameda, Zhao Song
2016	A*	`conf`	Weighted low rank approximations with provable guarantees. STOC Ilya P. Razenshteyn, Zhao Song, David P. Woodruff
2015	A*	`conf`	A Robust Sparse Fourier Transform in the Continuous Setting. FOCS Eric Price, Zhao Song
2015	B	`conf`	Batch codes through dense graphs without short cycles. ISIT Ankit Singh Rawat, Zhao Song, Alexandros G. Dimakis, Anna Gál
2015	A*	`conf`	Global Policy Construction in Modular Reinforcement Learning. AAAI Ruohan Zhang, Zhao Song, Dana H. Ballard
2015	J	`jnl`	Minmax regret 1-center algorithms for path/tree/unicycle/cactus networks. Discret. Appl. Math. Binay Bhattacharya, Tsunehiko Kameda, Zhao Song
2015	A*	`conf`	Novel power grid reduction method based on L1 regularization. DAC Ye Wang, Meng Li, Xinyang Yi, Zhao Song, Michael Orshansky, Constantine Caramanis
2014	J	`jnl`	A Linear Time Algorithm for Computing Minmax Regret 1-Median on a Tree Network. Algorithmica Binay K. Bhattacharya, Tsunehiko Kameda, Zhao Song
2014	Misc	`conf`	Back-Up 2-Center on a Path/Tree/Cycle/Unicycle. COCOON Binay K. Bhattacharya, Minati De, Tsunehiko Kameda, Sasanka Roy, Vladyslav Sokol, Zhao Song
2014	J	`jnl`	Batch Codes through Dense Graphs without Short Cycles. CoRR Alexandros G. Dimakis, Anna Gál, Ankit Singh Rawat, Zhao Song
2014	J	`jnl`	Batch Codes through Dense Graphs without Short Cycles. Electron. Colloquium Comput. Complex. Alexandros G. Dimakis, Anna Gál, Ankit Singh Rawat, Zhao Song
2014	B	`conf`	Improved Minmax Regret 1-Center Algorithms for Cactus Networks with c Cycles. LATIN Binay K. Bhattacharya, Tsunehiko Kameda, Zhao Song
2014	C	`conf`	Optimizing Squares Covering a Set of Points. COCOA Binay K. Bhattacharya, Sandip Das, Tsunehiko Kameda, Priya Ranjan Sinha Mahapatra, Zhao Song
2014	A	`conf`	Probabilistic recharging model in uncertain environments. AAMAS Zhao Song, Wen Sun
2014	—	`ch.`	Topic Modeling in Online Social Media, User Features, and Social Networks for. Encyclopedia of Social Network Analysis and Mining Bo Hu, Zhao Song, Martin Ester
2013	A*	`conf`	Graphical Model-Based Learning in High Dimensional Feature Spaces. AAAI Zhao Song, Yuke Zhu
2013	A	`conf`	Sustainable robot foraging: Adaptive fine-grained multi-robot task allocation for maximum sustainable yield of biological resources. IROS Zhao Song, Richard T. Vaughan
2012	B	`conf`	Computing Minmax Regret 1-Median on a Tree Network with Positive/Negative Vertex Weights. ISAAC Binay K. Bhattacharya, Tsunehiko Kameda, Zhao Song
2012	A	`conf`	MO-LOST: adaptive ant trail untangling in multi-objective multi-colony robot foraging. AAMAS Zhao Song, Seyed Abbas Sadat, Richard T. Vaughan
2012	B	`conf`	User Features and Social Networks for Topic Modeling in Online Social Media. ASONAM Bo Hu, Zhao Song, Martin Ester