Daniel M. Kane

Publication Activity (10 Years)

Years Active: 2005-2023
Publications (10 Years): 164

Top Venues

CoRR

COLT

STOC

Electron. Colloquium Comput. Complex.

Publications

Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis
Agnostically Learning Multi-index Models with Queries. CoRR (2023)
Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Sihan Liu, Nikos Zarifis
Efficient Testable Learning of Halfspaces with Adversarial Label Noise. CoRR (2023)
Ilias Diakonikolas, Daniel M. Kane
Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials. CoRR (2023)
Max Hopkins, Daniel M. Kane, Shachar Lovett, Gaurav Mahajan
Do PAC-Learners Learn the Marginal Distribution? CoRR (2023)
Ilias Diakonikolas, Christos Tzamos, Daniel M. Kane
A Strongly Polynomial Algorithm for Approximate Forster Transforms and Its Application to Halfspace Learning. STOC (2023)
Ilias Diakonikolas, Daniel M. Kane, Sihan Liu
Testing Closeness of Multivariate Distributions via Ramsey Theory. CoRR (2023)
Ilias Diakonikolas, Daniel M. Kane, Yuxin Sun
SQ Lower Bounds for Learning Mixtures of Linear Classifiers. CoRR (2023)
Ilias Diakonikolas, Daniel M. Kane, Ankit Pensia, Thanasis Pittas
Nearly-Linear Time and Streaming Algorithms for Outlier-Robust PCA. CoRR (2023)
Ilias Diakonikolas, Jelena Diakonikolas, Daniel M. Kane, Puqian Wang, Nikos Zarifis
Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise. COLT (2023)
Ilias Diakonikolas, Daniel M. Kane, Lisheng Ren
Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginals. CoRR (2023)
Ilias Diakonikolas, Daniel M. Kane, Yuetian Luo, Anru Zhang
Statistical and Computational Limits for Tensor-on-Tensor Association Detection. COLT (2023)
Ilias Diakonikolas, Daniel M. Kane, Jasper C. H. Lee, Ankit Pensia, Thanasis Pittas
A Spectral Algorithm for List-Decodable Covariance Estimation in Relative Frobenius Norm. CoRR (2023)
Daniel M. Kane, Ilias Diakonikolas, Hanshen Xiao, Sihan Liu
Online Robust Mean Estimation. CoRR (2023)
Ilias Diakonikolas, Jelena Diakonikolas, Daniel M. Kane, Puqian Wang, Nikos Zarifis
Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise. CoRR (2023)
Ilias Diakonikolas, Daniel M. Kane, Ankit Pensia
Gaussian Mean Testing Made Simple. SOSA (2023)
Yuqian Cheng, Daniel M. Kane, Zhicheng Zheng
New Lower Bounds for Testing Monotonicity and Log Concavity of Distributions. CoRR (2023)
Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas, Nikos Zarifis
SQ Lower Bounds for Learning Mixtures of Separated and Bounded Covariance Gaussians. COLT (2023)
Ilias Diakonikolas, Daniel M. Kane, Jasper C. H. Lee, Thanasis Pittas
Clustering Mixtures of Bounded Covariance Distributions Under Optimal Separation. CoRR (2023)
Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas, Nikos Zarifis
SQ Lower Bounds for Learning Bounded Covariance GMMs. CoRR (2023)
Ilias Diakonikolas, Jelena Diakonikolas, Daniel M. Kane, Puqian Wang, Nikos Zarifis
Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise. CoRR (2023)
Ilias Diakonikolas, Daniel M. Kane, Ankit Pensia, Thanasis Pittas
Near-Optimal Algorithms for Gaussians with Huber Contamination: Mean Estimation and Linear Regression. CoRR (2023)
Ilias Diakonikolas, Daniel M. Kane, Sushrut Karmalkar, Ankit Pensia, Thanasis Pittas
Robust Sparse Mean Estimation via Sum of Squares. CoRR (2022)
Ilias Diakonikolas, Christos Tzamos, Daniel M. Kane
A Strongly Polynomial Algorithm for Approximate Forster Transforms and its Application to Halfspace Learning. CoRR (2022)
Ilias Diakonikolas, Daniel M. Kane, Pasin Manurangsi, Lisheng Ren
Cryptographic Hardness of Learning Halfspaces with Massart Noise. CoRR (2022)
Ilias Diakonikolas, Daniel M. Kane, Sushrut Karmalkar, Ankit Pensia, Thanasis Pittas
List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filtering. CoRR (2022)
Ilias Diakonikolas, Daniel M. Kane, Ankit Pensia, Thanasis Pittas
Streaming Algorithms for High-Dimensional Robust Statistics. ICML (2022)
Ilias Diakonikolas, Daniel M. Kane, Ankit Pensia
Gaussian Mean Testing Made Simple. CoRR (2022)
Ilias Diakonikolas, Daniel M. Kane, Lisheng Ren, Yuxin Sun
SQ Lower Bounds for Learning Single Neurons with Massart Noise. CoRR (2022)
Ilias Diakonikolas, Daniel M. Kane, Jasper C. H. Lee, Ankit Pensia
Outlier-Robust Sparse Mean Estimation for Heavy-Tailed Distributions. CoRR (2022)
Alaa Maalouf, Murad Tukan, Eric Price, Daniel M. Kane, Dan Feldman
Coresets for Data Discretization and Sine Wave Fitting. AISTATS (2022)
Ilias Diakonikolas, Daniel M. Kane, Yuxin Sun
Optimal SQ Lower Bounds for Robustly Learning Discrete Product Distributions and Ising Models. COLT (2022)
Ainesh Bakshi, Ilias Diakonikolas, He Jia, Daniel M. Kane, Pravesh K. Kothari, Santosh S. Vempala
arbitrary Gaussians. STOC (2022)
Ilias Diakonikolas, Daniel M. Kane, Sushrut Karmalkar, Ankit Pensia, Thanasis Pittas
Robust Sparse Mean Estimation via Sum of Squares. COLT (2022)
Clément L. Canonne, Ilias Diakonikolas, Daniel M. Kane, Sihan Liu
Near-Optimal Bounds for Testing Histogram Distributions. CoRR (2022)
Ilias Diakonikolas, Daniel M. Kane, Yuxin Sun
Optimal SQ Lower Bounds for Robustly Learning Discrete Product Distributions and Ising Models. CoRR (2022)
Ilias Diakonikolas, Daniel M. Kane, Ankit Pensia, Thanasis Pittas
Streaming Algorithms for High-Dimensional Robust Statistics. CoRR (2022)
Daniel M. Kane, Ilias Diakonikolas
A Nearly Tight Bound for Fitting an Ellipsoid to Gaussian Random Points. CoRR (2022)
Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis
Learning general halfspaces with general Massart noise under the Gaussian distribution. STOC (2022)
Max Hopkins, Daniel M. Kane, Shachar Lovett, Gaurav Mahajan
Realizable Learning is All You Need. COLT (2022)
Ilias Diakonikolas, Daniel M. Kane, Daniel Kongsgaard, Jerry Li, Kevin Tian
Clustering mixture models in almost-linear time via list-decodable mean estimation. STOC (2022)
Ilias Diakonikolas, Daniel M. Kane
The Sample Complexity of Robust Covariance Testing. COLT (2021)
Ilias Diakonikolas, Russell Impagliazzo, Daniel M. Kane, Rex Lei, Jessica Sorrell, Christos Tzamos
Boosting in the Presence of Massart Noise. COLT (2021)
Ilias Diakonikolas, Daniel M. Kane
Non-Gaussian Component Analysis via Lattice Basis Reduction. CoRR (2021)
Yu Cheng, Ilias Diakonikolas, Daniel M. Kane, Rong Ge, Shivam Gupta, Mahdi Soltanolkotabi
Outlier-Robust Sparse Estimation via Non-Convex Optimization. CoRR (2021)
Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas, Nikos Zarifis
The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals. CoRR (2021)
Daniel M. Kane
Robust Learning of Mixtures of Gaussians. SODA (2021)
Daniel M. Kane, Scott Duke Kominers
Prisoners, Rooms, and Light Switches. Electron. J. Comb. 28 (1) (2021)
Ilias Diakonikolas, Themis Gouleakis, Daniel M. Kane, John Peebles, Eric Price
Optimal testing of discrete distributions with high probability. STOC (2021)
Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis
Agnostic Proper Learning of Halfspaces under Gaussian Marginals. CoRR (2021)
Ilias Diakonikolas, Daniel M. Kane, Daniel Kongsgaard, Jerry Li, Kevin Tian
Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation. CoRR (2021)
Ilias Diakonikolas, Daniel M. Kane, Christos Tzamos
Forster Decomposition and Learning Halfspaces with Noise. CoRR (2021)
Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas, Nikos Zarifis
The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals in the SQ Model. COLT (2021)
Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart, Yuxin Sun
Outlier-Robust Learning of Ising Models Under Dobrushin's Condition. CoRR (2021)
Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis
Agnostic Proper Learning of Halfspaces under Gaussian Marginals. COLT (2021)
Daniel M. Kane, Shahed Sharif, Alice Silverberg
Quantum Money from Quaternion Algebras. IACR Cryptol. ePrint Arch. 2021 (2021)
Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, Alistair Stewart
Robustness meets algorithms. Commun. ACM 64 (5) (2021)
Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis
Threshold Phenomena in Learning Halfspaces with Massart Noise. CoRR (2021)
Ilias Diakonikolas, Daniel M. Kane, Ankit Pensia, Thanasis Pittas, Alistair Stewart
Statistical Query Lower Bounds for List-Decodable Linear Regression. CoRR (2021)
Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart, Yuxin Sun
Outlier-Robust Learning of Ising Models Under Dobrushin's Condition. COLT (2021)
Daniel M. Kane, Shahed Sharif, Alice Silverberg
Quantum Money from Quaternion Algebras. CoRR (2021)
Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis
Efficiently learning halfspaces with Tsybakov noise. STOC (2021)
Ilias Diakonikolas, Daniel M. Kane
Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models. CoRR (2020)
Ilias Diakonikolas, Daniel M. Kane
Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models. FOCS (2020)
Max Hopkins, Daniel M. Kane, Shachar Lovett, Gaurav Mahajan
Point Location and Active Learning: Learning Halfspaces Almost Optimally. CoRR (2020)
Ilias Diakonikolas, Daniel M. Kane, Pasin Manurangsi
The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise. CoRR (2020)
Ilias Diakonikolas, Themis Gouleakis, Daniel M. Kane, John Peebles, Eric Price
Optimal Testing of Discrete Distributions with High Probability. CoRR (2020)
Ilias Diakonikolas, Daniel M. Kane, Daniel Kongsgaard, Jerry Li, Kevin Tian
List-Decodable Mean Estimation in Nearly-PCA Time. CoRR (2020)
Ilias Diakonikolas, Daniel M. Kane, Pasin Manurangsi
The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise. NeurIPS (2020)
Ilias Diakonikolas, Daniel M. Kane
Hardness of Learning Halfspaces with Massart Noise. CoRR (2020)
Ilias Diakonikolas, Daniel M. Kane, Nikos Zarifis
Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals. CoRR (2020)
Clément L. Canonne, Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart
Testing Bayesian Networks. IEEE Trans. Inf. Theory 66 (5) (2020)
Ilias Diakonikolas, Daniel M. Kane, Daniel Kongsgaard
List-Decodable Mean Estimation via Iterative Multi-Filtering. CoRR (2020)
Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Nikos Zarifis
Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks. COLT (2020)
Ilias Diakonikolas, Daniel M. Kane, Ankit Pensia
Outlier Robust Mean Estimation with Subgaussian Rates via Stability. NeurIPS (2020)
Daniel M. Kane
Robust Learning of Mixtures of Gaussians. CoRR (2020)
Ainesh Bakshi, Ilias Diakonikolas, He Jia, Daniel M. Kane, Pravesh K. Kothari, Santosh S. Vempala
Robustly Learning Mixtures of k Arbitrary Gaussians. CoRR (2020)
Ilias Diakonikolas, Daniel M. Kane, Ankit Pensia
Outlier Robust Mean Estimation with Subgaussian Rates via Stability. CoRR (2020)
Ilias Diakonikolas, Daniel M. Kane
The Sample Complexity of Robust Covariance Testing. CoRR (2020)
Daniel M. Kane, Scott Duke Kominers
Prisoners, Rooms, and Lightswitches. CoRR (2020)
Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Nikos Zarifis
Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks. CoRR (2020)
Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis
A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise. CoRR (2020)
Max Hopkins, Daniel M. Kane, Shachar Lovett
The Power of Comparisons for Actively Learning Linear Classifiers. CoRR (2019)
Ilias Diakonikolas, Themis Gouleakis, Daniel M. Kane, Sankeerth Rao
Communication and Memory Efficient Testing of Discrete Distributions. CoRR (2019)
Ilias Diakonikolas, Daniel M. Kane
Degree-푑 chow parameters robustly determine degree-푑 PTFs (and algorithmic applications). STOC (2019)
Daniel M. Kane, Shachar Lovett, Shay Moran
Near-optimal Linear Decision Trees for k-SUM and Related Problems. J. ACM 66 (3) (2019)
Surbhi Goel, Daniel M. Kane, Adam R. Klivans
Learning Ising Models with Independent Failures. COLT (2019)
Ilias Diakonikolas, Themis Gouleakis, Daniel M. Kane, Sankeerth Rao
Communication and Memory Efficient Testing of Discrete Distributions. COLT (2019)
Ilias Diakonikolas, Daniel M. Kane
Recent Advances in Algorithmic High-Dimensional Robust Statistics. CoRR (2019)
Daniel M. Kane, Carlo Sanna, Jeffrey O. Shallit
Waring's Theorem for Binary Powers. Comb. 39 (6) (2019)
Ilias Diakonikolas, Daniel M. Kane, Pasin Manurangsi
Nearly Tight Bounds for Robust Proper Learning of Halfspaces with a Margin. CoRR (2019)
Daniel M. Kane, Richard Ryan Williams
The Orthogonal Vectors Conjecture for Branching Programs and Formulas. ITCS (2019)
Surbhi Goel, Daniel M. Kane, Adam R. Klivans
Learning Ising Models with Independent Failures. CoRR (2019)
Ilias Diakonikolas, Daniel M. Kane, John Peebles
Testing Identity of Multidimensional Histograms. COLT (2019)
Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, Alistair Stewart
Robustly Learning a Gaussian: Getting Optimal Error, Efficiently. SODA (2018)
Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart
Sharp Bounds for Generalized Uniformity Testing. NeurIPS (2018)
Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart
List-decodable robust mean estimation and learning mixtures of spherical gaussians. STOC (2018)
Clément L. Canonne, Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart
Testing Conditional Independence of Discrete Distributions. ITA (2018)
Clément L. Canonne, Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart
Testing conditional independence of discrete distributions. STOC (2018)
Daniel M. Kane
Quantum Money from Modular Forms. CoRR (2018)
Daniel M. Kane, Shachar Lovett, Shay Moran
Generalized comparison trees for point-location problems. CoRR (2018)

Daniel M. Kane.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Daniel M. Kane