Daniel M. Kane
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Daniel M. Kane has a total of 18 co-authors. Here are the top co-authors by number of shared publications:
- Ilias Diakonikolas
University of Wisconsin-Madison, Madison, USA
4 shared publications - Sihan Liu
University of California San Diego, San Diego, USA
3 shared publications - Anthony Ostuni
University of California at San Diego, La Jolla, USA
2 shared publications - Jerry Li
University of Washington, Seattle, USA
2 shared publications - Pravesh K. Kothari
Princeton University, Princeton, USA
2 shared publications - Ainesh Bakshi
Massachusetts Institute of Technology, Cambridge, USA
1 shared publication
Latest Publications
- Open Access
- 17 June 2026
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 73 (3) , 1-100
Robustly Learning Mixtures of k Arbitrary Gaussians
We give a polynomial-time algorithm for the problem of robustly estimating a mixture of k arbitrary Gaussians in ℝ d , for any fixed k , in the presence of a constant fraction of arbitrary corruptions. This resolves the main open problem in several previous works on algorithmic robust statistics, which addressed the special cases of robustly estimating (a) a single Gaussian, (b) a mixture of TV-distance separated Gaussians, and (c) a uniform mixture of two Gaussians. Our main tools are an efficient partial clustering algorithm that relies on the sum-of-squares method, and a novel tensor decomposition algorithm that allows errors in both Frobenius norm and low-rank terms.
- 17 June 2026
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 73 (3) , 1-100
Open AccessRobustly Learning Mixtures of k Arbitrary Gaussians
We give a polynomial-time algorithm for the problem of robustly estimating a mixture of k arbitrary Gaussians in ℝ d , for any fixed k , in the presence of a constant fraction of arbitrary corruptions. This resolves the main open problem in several previous works on algorithmic robust statistics, which addressed the special cases of robustly estimating (a) a single Gaussian, (b) a mixture of TV-distance separated Gaussians, and (c) a uniform mixture of two Gaussians. Our main tools are an efficient partial clustering algorithm that relies on the sum-of-squares method, and a novel tensor decomposition algorithm that allows errors in both Frobenius norm and low-rank terms.
- Open Access
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 1763-1770
Rigorous Implications of the Low-Degree Heuristic
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 1763-1770
Open AccessRigorous Implications of the Low-Degree Heuristic
- Open Access
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 767-776
High-Accuracy List-Decodable Mean Estimation
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 767-776
Open AccessHigh-Accuracy List-Decodable Mean Estimation
- Open Access
- 15 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 1680-1688
Entangled Mean Estimation in High Dimensions
- 15 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 1680-1688
Open AccessEntangled Mean Estimation in High Dimensions
- Open Access
- 15 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 1807-1816
Locally Sampleable Uniform Symmetric Distributions
- 15 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 1807-1816
Open AccessLocally Sampleable Uniform Symmetric Distributions
- Open Access
- 10 June 2024
- Published by Association for Computing Machinery (ACM)
- p. 340-347
Testing Closeness of Multivariate Distributions via Ramsey Theory
We investigate the statistical task of closeness (or equivalence) testing for multidimensional distributions. Specifically, given sample access to two unknown distributions p, q on d, we want to distinguish between the case that p=q versus ||p−q||Ak > є, where ||p−q||Ak denotes the generalized Ak distance between p and q — measuring the maximum discrepancy between the distributions over any collection of k disjoint, axis-aligned rectangles. Our main result is the first closeness tester for this problem with sub-learning sample complexity in any fixed dimension and a nearly-matching sample complexity lower bound. In more detail, we provide a computationally efficient closeness tester with sample complexity O((k6/7/ polyd(є)) logd(k)). On the lower bound side, we establish a qualitatively matching sample complexity lower bound of Ω(k6/7/poly(є)), even for d=2. These sample complexity bounds are surprising because the sample complexity of the problem in the univariate setting is Θ(k4/5/poly(є)). This has the interesting consequence that the jump from one to two dimensions leads to a substantial increase in sample complexity, while increases beyond that do not. As a corollary of our general Ak tester, we obtain dTV-closeness testers for pairs of k-histograms on d over a common unknown partition, and pairs of uniform distributions supported on the union of k unknown disjoint axis-aligned rectangles. Both our algorithm and our lower bound make essential use of tools from Ramsey theory.
- 10 June 2024
- Published by Association for Computing Machinery (ACM)
- p. 340-347
Open AccessTesting Closeness of Multivariate Distributions via Ramsey Theory
We investigate the statistical task of closeness (or equivalence) testing for multidimensional distributions. Specifically, given sample access to two unknown distributions p, q on d, we want to distinguish between the case that p=q versus ||p−q||Ak > є, where ||p−q||Ak denotes the generalized Ak distance between p and q — measuring the maximum discrepancy between the distributions over any collection of k disjoint, axis-aligned rectangles. Our main result is the first closeness tester for this problem with sub-learning sample complexity in any fixed dimension and a nearly-matching sample complexity lower bound. In more detail, we provide a computationally efficient closeness tester with sample complexity O((k6/7/ polyd(є)) logd(k)). On the lower bound side, we establish a qualitatively matching sample complexity lower bound of Ω(k6/7/poly(є)), even for d=2. These sample complexity bounds are surprising because the sample complexity of the problem in the univariate setting is Θ(k4/5/poly(є)). This has the interesting consequence that the jump from one to two dimensions leads to a substantial increase in sample complexity, while increases beyond that do not. As a corollary of our general Ak tester, we obtain dTV-closeness testers for pairs of k-histograms on d over a common unknown partition, and pairs of uniform distributions supported on the union of k unknown disjoint axis-aligned rectangles. Both our algorithm and our lower bound make essential use of tools from Ramsey theory.
- Open Access
- 10 June 2024
- Published by Association for Computing Machinery (ACM)
- p. 152-159
Super Non-singular Decompositions of Polynomials and Their Application to Robustly Learning Low-Degree PTFs
We study the efficient learnability of low-degree polynomial threshold functions (PTFs) in the presence of a constant fraction of adversarial corruptions. Our main algorithmic result is a polynomial-time PAC learning algorithm for this concept class in the strong contamination model under the Gaussian distribution with error guarantee Od, c(opt1−c), for any desired constant c>0, where opt is the fraction of corruptions. In the strong contamination model, an omniscient adversary can arbitrarily corrupt an opt-fraction of the data points and their labels. This model generalizes the malicious noise model and the adversarial label noise model. Prior to our work, known polynomial-time algorithms in this corruption model (or even in the weaker adversarial label noise model) achieved error Õd(opt1/(d+1)), which deteriorates significantly as a function of the degree d. Our algorithm employs an iterative approach inspired by localization techniques previously used in the context of learning linear threshold functions. Specifically, we use a robust perceptron algorithm to compute a good partial classifier and then iterate on the unclassified points. In order to achieve this, we need to take a set defined by a number of polynomial inequalities and partition it into several well-behaved subsets. To this end, we develop new polynomial decomposition techniques that may be of independent interest.
- 10 June 2024
- Published by Association for Computing Machinery (ACM)
- p. 152-159
Open AccessSuper Non-singular Decompositions of Polynomials and Their Application to Robustly Learning Low-Degree PTFs
We study the efficient learnability of low-degree polynomial threshold functions (PTFs) in the presence of a constant fraction of adversarial corruptions. Our main algorithmic result is a polynomial-time PAC learning algorithm for this concept class in the strong contamination model under the Gaussian distribution with error guarantee Od, c(opt1−c), for any desired constant c>0, where opt is the fraction of corruptions. In the strong contamination model, an omniscient adversary can arbitrarily corrupt an opt-fraction of the data points and their labels. This model generalizes the malicious noise model and the adversarial label noise model. Prior to our work, known polynomial-time algorithms in this corruption model (or even in the weaker adversarial label noise model) achieved error Õd(opt1/(d+1)), which deteriorates significantly as a function of the degree d. Our algorithm employs an iterative approach inspired by localization techniques previously used in the context of learning linear threshold functions. Specifically, we use a robust perceptron algorithm to compute a good partial classifier and then iterate on the unclassified points. In order to achieve this, we need to take a set defined by a number of polynomial inequalities and partition it into several well-behaved subsets. To this end, we develop new polynomial decomposition techniques that may be of independent interest.
- Open Access
- 10 June 2024
- Published by Association for Computing Machinery (ACM)
- p. 1279-1286
Locality Bounds for Sampling Hamming Slices
Spurred by the influential work of Viola (Journal of Computing 2012), the past decade has witnessed an active line of research into the complexity of (approximately) sampling distributions, in contrast to the traditional focus on the complexity of computing functions. We build upon and make explicit earlier implicit results of Viola to provide superconstant lower bounds on the locality of Boolean functions approximately sampling the uniform distribution over binary strings of particular Hamming weights, both exactly and modulo an integer, answering questions of Viola (Journal of Computing 2012) and Filmus, Leigh, Riazanov, and Sokolov (RANDOM 2023). Applications to data structure lower bounds and quantum-classical separations are discussed. This is an extended The full paper can be found at https://arxiv.org/abs/2402.14278.
- 10 June 2024
- Published by Association for Computing Machinery (ACM)
- p. 1279-1286
Open AccessLocality Bounds for Sampling Hamming Slices
Spurred by the influential work of Viola (Journal of Computing 2012), the past decade has witnessed an active line of research into the complexity of (approximately) sampling distributions, in contrast to the traditional focus on the complexity of computing functions. We build upon and make explicit earlier implicit results of Viola to provide superconstant lower bounds on the locality of Boolean functions approximately sampling the uniform distribution over binary strings of particular Hamming weights, both exactly and modulo an integer, answering questions of Viola (Journal of Computing 2012) and Filmus, Leigh, Riazanov, and Sokolov (RANDOM 2023). Applications to data structure lower bounds and quantum-classical separations are discussed. This is an extended The full paper can be found at https://arxiv.org/abs/2402.14278.