Daniel Kane

Batch List-Decodable Linear Regression via Higher Moments ICML 2025 Do PAC-Learners Learn the Marginal Distribution? ALT 2025 Efficient Multivariate Robust Mean Estimation Under Mean-Shift Contamination ICML 2025 On Fine-Grained Distinct Element Estimation ICML 2025 On Learning Parallel Pancakes with Mostly Uniform Weights ICML 2025 New Lower Bounds for Testing Monotonicity and Log Concavity of Distributions COLT 2024 Robust Sparse Estimation for Gaussians with Optimal Error under Huber Contamination ICML 2024 Testable Learning of General Halfspaces with Adversarial Label Noise COLT 2024 A Nearly Tight Bound for Fitting an Ellipsoid to Gaussian Random Points COLT 2023 A Spectral Algorithm for List-Decodable Covariance Estimation in Relative Frobenius Norm NeurIPS 2023 Efficient Testable Learning of Halfspaces with Adversarial Label Noise NeurIPS 2023 Exponential Hardness of Reinforcement Learning with Linear Function Approximation COLT 2023 Nearly-Linear Time and Streaming Algorithms for Outlier-Robust PCA ICML 2023 Near-Optimal Algorithms for Gaussians with Huber Contamination: Mean Estimation and Linear Regression NeurIPS 2023 Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise NeurIPS 2023 Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginals ICML 2023 SQ Lower Bounds for Learning Mixtures of Linear Classifiers NeurIPS 2023 SQ Lower Bounds for Non-Gaussian Component Analysis with Weaker Assumptions NeurIPS 2023 Computational-Statistical Gap in Reinforcement Learning COLT 2022 Cryptographic Hardness of Learning Halfspaces with Massart Noise NeurIPS 2022 Hardness of Learning a Single Neuron with Adversarial Label Noise AISTATS 2022 List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filtering NeurIPS 2022 Nearly-Tight Bounds for Testing Histogram Distributions NeurIPS 2022 Near-Optimal Statistical Query Hardness of Learning Halfspaces with Massart Noise COLT 2022 Non-Gaussian Component Analysis via Lattice Basis Reduction COLT 2022 Outlier-Robust Sparse Estimation via Non-Convex Optimization NeurIPS 2022 Outlier-Robust Sparse Mean Estimation for Heavy-Tailed Distributions NeurIPS 2022 SQ Lower Bounds for Learning Single Neurons with Massart Noise NeurIPS 2022 Bounded Memory Active Learning through Enriched Queries COLT 2021 Forster Decomposition and Learning Halfspaces with Noise NeurIPS 2021 List-Decodable Mean Estimation in Nearly-PCA Time NeurIPS 2021 Statistical Query Lower Bounds for List-Decodable Linear Regression NeurIPS 2021 vqSGD: Vector Quantized Stochastic Gradient Descent AISTATS 2021 List-Decodable Mean Estimation via Iterative Multi-Filtering NeurIPS 2020 Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals NeurIPS 2020 Noise-tolerant, Reliable Active Classification with Comparison Queries COLT 2020 The Power of Comparisons for Actively Learning Linear Classifiers NeurIPS 2020 Nearly Tight Bounds for Robust Proper Learning of Halfspaces with a Margin NeurIPS 2019 On Communication Complexity of Classification Problems COLT 2019 Outlier-Robust High-Dimensional Sparse Estimation via Iterative Filtering NeurIPS 2019 Private Testing of Distributions via Sample Permutations NeurIPS 2019 Sever: A Robust Meta-Algorithm for Stochastic Optimization ICML 2019 The Optimal Approximation Factor in Density Estimation COLT 2019 Robust Learning of Fixed-Structure Bayesian Networks NeurIPS 2018 Learning Halfspaces Under Log-Concave Densities: Polynomial Approximations and Moment Matching COLT 2013