Daniel M. Kane

261 papers A* 79A 8B 2Misc 1Journal 167Unranked 3

Year	Rank	Type	Title / Venue / Authors
2026	J	`jnl`	High-Dimensional Gaussian Mean Estimation under Realizable Contamination. CoRR Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas
2026	A	`conf`	Quantum Advantage from Sampling Shallow Circuits: Beyond Hardness of Marginals. ITCS Daniel Grier, Daniel M. Kane, Jackson Morris, Anthony Ostuni, Kewen Wu
2026	J	`jnl`	Rigorous Implications of the Low-Degree Heuristic. CoRR Jun-Ting Hsieh, Daniel M. Kane, Pravesh K. Kothari, Jerry Li, Sidhanth Mohanty, Stefan Tiegel
2026	J	`jnl`	Sample Complexity Bounds for Robust Mean Estimation with Mean-Shift Contamination. CoRR Ilias Diakonikolas, Giannis Iakovidis, Daniel M. Kane, Sihan Liu
2026	J	`jnl`	Statistical Query Lower Bounds for Smoothed Agnostic Learning. CoRR Ilias Diakonikolas, Daniel M. Kane
2026	J	`jnl`	Testable Learning of General Halfspaces under Massart Noise. CoRR Ilias Diakonikolas, Giannis Iakovidis, Daniel M. Kane, Sihan Liu
2025	J	`jnl`	Active Learning of General Halfspaces: Label Queries vs Membership Queries. CoRR Ilias Diakonikolas, Daniel M. Kane, Mingchen Ma
2025	J	`jnl`	Agnostic Product Mixed State Tomography via Robust Statistics. CoRR Alvan Arulandu, Ilias Diakonikolas, Daniel M. Kane, Jerry Zheng Li
2025	J	`jnl`	Algorithms and SQ Lower Bounds for Robustly Learning Real-valued Multi-index Models. CoRR Ilias Diakonikolas, Giannis Iakovidis, Daniel M. Kane, Lisheng Ren
2025	J	`jnl`	Batch List-Decodable Linear Regression via Higher Moments. CoRR Ilias Diakonikolas, Daniel M. Kane, Sushrut Karmalkar, Sihan Liu, Thanasis Pittas
2025	A*	`conf`	Clustering Mixtures of Bounded Covariance Distributions Under Optimal Separation. SODA Ilias Diakonikolas, Daniel M. Kane, Jasper C. H. Lee, Thanasis Pittas
2025	B	`conf`	Do PAC-Learners Learn the Marginal Distribution? ALT Max Hopkins, Daniel M. Kane, Shachar Lovett, Gaurav Mahajan
2025	J	`jnl`	Efficient Multivariate Robust Mean Estimation Under Mean-Shift Contamination. CoRR Ilias Diakonikolas, Giannis Iakovidis, Daniel M. Kane, Thanasis Pittas
2025	A*	`conf`	Entangled Mean Estimation in High Dimensions. STOC Ilias Diakonikolas, Daniel M. Kane, Sihan Liu, Thanasis Pittas
2025	J	`jnl`	Entangled Mean Estimation in High-Dimensions. CoRR Ilias Diakonikolas, Daniel M. Kane, Sihan Liu, Thanasis Pittas
2025	A*	`conf`	Faster Algorithms for Agnostically Learning Disjunctions and their Implications. COLT Ilias Diakonikolas, Daniel M. Kane, Lisheng Ren
2025	J	`jnl`	Faster Algorithms for Agnostically Learning Disjunctions and their Implications. CoRR Ilias Diakonikolas, Daniel M. Kane, Lisheng Ren
2025	A*	`conf`	Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Models. FOCS Ilias Diakonikolas, Daniel M. Kane
2025	J	`jnl`	Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination. CoRR Ilias Diakonikolas, Chao Gao, Daniel M. Kane, John Lafferty, Ankit Pensia
2025	J	`jnl`	Linear Regression under Missing or Corrupted Coordinates. CoRR Ilias Diakonikolas, Jelena Diakonikolas, Daniel M. Kane, Jasper C. H. Lee, Thanasis Pittas
2025	A*	`conf`	Locally Sampleable Uniform Symmetric Distributions. STOC Daniel M. Kane, Anthony Ostuni, Kewen Wu
2025	J	`jnl`	On Fine-Grained Distinct Element Estimation. CoRR Ilias Diakonikolas, Daniel M. Kane, Jasper C. H. Lee, Thanasis Pittas, David P. Woodruff, Samson Zhou
2025	J	`jnl`	On Learning Parallel Pancakes with Mostly Uniform Weights. CoRR Ilias Diakonikolas, Daniel M. Kane, Sushrut Karmalkar, Jasper C. H. Lee, Thanasis Pittas
2025	A*	`conf`	PTF Testing Lower Bounds for Non-Gaussian Component Analysis. FOCS Ilias Diakonikolas, Daniel M. Kane, Sihan Liu, Thanasis Pittas
2025	J	`jnl`	PTF Testing Lower Bounds for Non-Gaussian Component Analysis. CoRR Ilias Diakonikolas, Daniel M. Kane, Sihan Liu, Thanasis Pittas
2025	J	`jnl`	Quantum Advantage from Sampling Shallow Circuits: Beyond Hardness of Marginals. CoRR Daniel Grier, Daniel M. Kane, Jackson Morris, Anthony Ostuni, Kewen Wu
2025	J	`jnl`	Replicable Distribution Testing. CoRR Ilias Diakonikolas, Jingyi Gao, Daniel M. Kane, Sihan Liu, Christopher Ye
2025	A*	`conf`	Robust Learning of Multi-index Models via Iterative Subspace Approximation. FOCS Ilias Diakonikolas, Giannis Iakovidis, Daniel M. Kane, Nikos Zarifis
2025	J	`jnl`	Robust Learning of Multi-index Models via Iterative Subspace Approximation. CoRR Ilias Diakonikolas, Giannis Iakovidis, Daniel M. Kane, Nikos Zarifis
2025	J	`jnl`	Symmetric Distributions from Shallow Circuits. CoRR Daniel M. Kane, Anthony Ostuni, Kewen Wu
2024	A*	`conf`	Active Learning of General Halfspaces: Label Queries vs Membership Queries. NeurIPS Ilias Diakonikolas, Daniel M. Kane, Mingchen Ma
2024	A*	`conf`	Agnostically Learning Multi-Index Models with Queries. FOCS Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis
2024	J	`jnl`	Efficient Testable Learning of General Halfspaces with Adversarial Label Noise. CoRR Ilias Diakonikolas, Daniel M. Kane, Sihan Liu, Nikos Zarifis
2024	A*	`conf`	Efficiently Learning One-Hidden-Layer ReLU Networks via SchurPolynomials. COLT Ilias Diakonikolas, Daniel M. Kane
2024	J	`jnl`	Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Models. CoRR Ilias Diakonikolas, Daniel M. Kane
2024	A*	`conf`	Locality Bounds for Sampling Hamming Slices. STOC Daniel M. Kane, Anthony Ostuni, Kewen Wu
2024	J	`jnl`	Locality Bounds for Sampling Hamming Slices. CoRR Daniel M. Kane, Anthony Ostuni, Kewen Wu
2024	J	`jnl`	Locality Bounds for Sampling Hamming Slices. Electron. Colloquium Comput. Complex. Daniel M. Kane, Anthony Ostuni, Kewen Wu
2024	J	`jnl`	Locally Sampleable Uniform Symmetric Distributions. CoRR Daniel M. Kane, Anthony Ostuni, Kewen Wu
2024	A*	`conf`	New Lower Bounds for Testing Monotonicity and Log Concavity of Distributions. COLT Yuqian Cheng, Daniel M. Kane, Zhicheng Zheng
2024	A*	`conf`	Online Robust Mean Estimation. SODA Daniel M. Kane, Ilias Diakonikolas, Hanshen Xiao, Sihan Liu
2024	J	`jnl`	Realizable Learning is All You Need. TheoretiCS Max Hopkins, Daniel M. Kane, Shachar Lovett, Gaurav Mahajan
2024	A*	`conf`	Replicability in High Dimensional Statistics. FOCS Max Hopkins, Russell Impagliazzo, Daniel M. Kane, Sihan Liu, Christopher Ye
2024	J	`jnl`	Robust Sparse Estimation for Gaussians with Optimal Error under Huber Contamination. CoRR Ilias Diakonikolas, Daniel M. Kane, Sushrut Karmalkar, Ankit Pensia, Thanasis Pittas
2024	A*	`conf`	Statistical Query Lower Bounds for Learning Truncated Gaussians. COLT Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas, Nikos Zarifis
2024	J	`jnl`	Statistical Query Lower Bounds for Learning Truncated Gaussians. CoRR Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas, Nikos Zarifis
2024	A*	`conf`	Super Non-singular Decompositions of Polynomials and Their Application to Robustly Learning Low-Degree PTFs. STOC Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Sihan Liu, Nikos Zarifis
2024	J	`jnl`	Super Non-singular Decompositions of Polynomials and their Application to Robustly Learning Low-degree PTFs. CoRR Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Sihan Liu, Nikos Zarifis
2024	A*	`conf`	Testable Learning of General Halfspaces with Adversarial Label Noise. COLT Ilias Diakonikolas, Daniel M. Kane, Sihan Liu, Nikos Zarifis
2024	A*	`conf`	Testing Closeness of Multivariate Distributions via Ramsey Theory. STOC Ilias Diakonikolas, Daniel M. Kane, Sihan Liu
2023	J	`jnl`	A Spectral Algorithm for List-Decodable Covariance Estimation in Relative Frobenius Norm. CoRR Ilias Diakonikolas, Daniel M. Kane, Jasper C. H. Lee, Ankit Pensia, Thanasis Pittas
2023	A*	`conf`	A Strongly Polynomial Algorithm for Approximate Forster Transforms and Its Application to Halfspace Learning. STOC Ilias Diakonikolas, Christos Tzamos, Daniel M. Kane
2023	J	`jnl`	Agnostically Learning Multi-index Models with Queries. CoRR Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis
2023	J	`jnl`	Clustering Mixtures of Bounded Covariance Distributions Under Optimal Separation. CoRR Ilias Diakonikolas, Daniel M. Kane, Jasper C. H. Lee, Thanasis Pittas
2023	J	`jnl`	Do PAC-Learners Learn the Marginal Distribution? CoRR Max Hopkins, Daniel M. Kane, Shachar Lovett, Gaurav Mahajan
2023	J	`jnl`	Efficient Testable Learning of Halfspaces with Adversarial Label Noise. CoRR Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Sihan Liu, Nikos Zarifis
2023	J	`jnl`	Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials. CoRR Ilias Diakonikolas, Daniel M. Kane
2023	—	`conf`	Gaussian Mean Testing Made Simple. SOSA Ilias Diakonikolas, Daniel M. Kane, Ankit Pensia
2023	A*	`conf`	Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise. COLT Ilias Diakonikolas, Jelena Diakonikolas, Daniel M. Kane, Puqian Wang, Nikos Zarifis
2023	J	`jnl`	Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise. CoRR Ilias Diakonikolas, Jelena Diakonikolas, Daniel M. Kane, Puqian Wang, Nikos Zarifis
2023	J	`jnl`	Near-Optimal Algorithms for Gaussians with Huber Contamination: Mean Estimation and Linear Regression. CoRR Ilias Diakonikolas, Daniel M. Kane, Ankit Pensia, Thanasis Pittas
2023	J	`jnl`	Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise. CoRR Ilias Diakonikolas, Jelena Diakonikolas, Daniel M. Kane, Puqian Wang, Nikos Zarifis
2023	J	`jnl`	Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginals. CoRR Ilias Diakonikolas, Daniel M. Kane, Lisheng Ren
2023	J	`jnl`	Nearly-Linear Time and Streaming Algorithms for Outlier-Robust PCA. CoRR Ilias Diakonikolas, Daniel M. Kane, Ankit Pensia, Thanasis Pittas
2023	J	`jnl`	New Lower Bounds for Testing Monotonicity and Log Concavity of Distributions. CoRR Yuqian Cheng, Daniel M. Kane, Zhicheng Zheng
2023	J	`jnl`	Online Robust Mean Estimation. CoRR Daniel M. Kane, Ilias Diakonikolas, Hanshen Xiao, Sihan Liu
2023	J	`jnl`	SQ Lower Bounds for Learning Bounded Covariance GMMs. CoRR Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas, Nikos Zarifis
2023	J	`jnl`	SQ Lower Bounds for Learning Mixtures of Linear Classifiers. CoRR Ilias Diakonikolas, Daniel M. Kane, Yuxin Sun
2023	A*	`conf`	SQ Lower Bounds for Learning Mixtures of Separated and Bounded Covariance Gaussians. COLT Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas, Nikos Zarifis
2023	A*	`conf`	Statistical and Computational Limits for Tensor-on-Tensor Association Detection. COLT Ilias Diakonikolas, Daniel M. Kane, Yuetian Luo, Anru Zhang
2023	J	`jnl`	Testing Closeness of Multivariate Distributions via Ramsey Theory. CoRR Ilias Diakonikolas, Daniel M. Kane, Sihan Liu
2022	J	`jnl`	A Nearly Tight Bound for Fitting an Ellipsoid to Gaussian Random Points. CoRR Daniel M. Kane, Ilias Diakonikolas
2022	J	`jnl`	A Strongly Polynomial Algorithm for Approximate Forster Transforms and its Application to Halfspace Learning. CoRR Ilias Diakonikolas, Christos Tzamos, Daniel M. Kane
2022	A*	`conf`	Clustering mixture models in almost-linear time via list-decodable mean estimation. STOC Ilias Diakonikolas, Daniel M. Kane, Daniel Kongsgaard, Jerry Li, Kevin Tian
2022	A	`conf`	Coresets for Data Discretization and Sine Wave Fitting. AISTATS Alaa Maalouf, Murad Tukan, Eric Price, Daniel M. Kane, Dan Feldman
2022	J	`jnl`	Cryptographic Hardness of Learning Halfspaces with Massart Noise. CoRR Ilias Diakonikolas, Daniel M. Kane, Pasin Manurangsi, Lisheng Ren
2022	J	`jnl`	Gaussian Mean Testing Made Simple. CoRR Ilias Diakonikolas, Daniel M. Kane, Ankit Pensia
2022	A*	`conf`	Learning general halfspaces with general Massart noise under the Gaussian distribution. STOC Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis
2022	J	`jnl`	List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filtering. CoRR Ilias Diakonikolas, Daniel M. Kane, Sushrut Karmalkar, Ankit Pensia, Thanasis Pittas
2022	J	`jnl`	Near-Optimal Bounds for Testing Histogram Distributions. CoRR Clément L. Canonne, Ilias Diakonikolas, Daniel M. Kane, Sihan Liu
2022	A*	`conf`	Optimal SQ Lower Bounds for Robustly Learning Discrete Product Distributions and Ising Models. COLT Ilias Diakonikolas, Daniel M. Kane, Yuxin Sun
2022	J	`jnl`	Optimal SQ Lower Bounds for Robustly Learning Discrete Product Distributions and Ising Models. CoRR Ilias Diakonikolas, Daniel M. Kane, Yuxin Sun
2022	J	`jnl`	Outlier-Robust Sparse Mean Estimation for Heavy-Tailed Distributions. CoRR Ilias Diakonikolas, Daniel M. Kane, Jasper C. H. Lee, Ankit Pensia
2022	A*	`conf`	Realizable Learning is All You Need. COLT Max Hopkins, Daniel M. Kane, Shachar Lovett, Gaurav Mahajan
2022	A*	`conf`	Robust Sparse Mean Estimation via Sum of Squares. COLT Ilias Diakonikolas, Daniel M. Kane, Sushrut Karmalkar, Ankit Pensia, Thanasis Pittas
2022	J	`jnl`	Robust Sparse Mean Estimation via Sum of Squares. CoRR Ilias Diakonikolas, Daniel M. Kane, Sushrut Karmalkar, Ankit Pensia, Thanasis Pittas
2022	A*	`conf`	Robustly learning mixtures of STOC Ainesh Bakshi, Ilias Diakonikolas, He Jia, Daniel M. Kane, Pravesh K. Kothari, Santosh S. Vempala
2022	J	`jnl`	SQ Lower Bounds for Learning Single Neurons with Massart Noise. CoRR Ilias Diakonikolas, Daniel M. Kane, Lisheng Ren, Yuxin Sun
2022	A*	`conf`	Streaming Algorithms for High-Dimensional Robust Statistics. ICML Ilias Diakonikolas, Daniel M. Kane, Ankit Pensia, Thanasis Pittas
2022	J	`jnl`	Streaming Algorithms for High-Dimensional Robust Statistics. CoRR Ilias Diakonikolas, Daniel M. Kane, Ankit Pensia, Thanasis Pittas
2021	A*	`conf`	Agnostic Proper Learning of Halfspaces under Gaussian Marginals. COLT Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis
2021	J	`jnl`	Agnostic Proper Learning of Halfspaces under Gaussian Marginals. CoRR Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis
2021	A*	`conf`	Boosting in the Presence of Massart Noise. COLT Ilias Diakonikolas, Russell Impagliazzo, Daniel M. Kane, Rex Lei, Jessica Sorrell, Christos Tzamos
2021	J	`jnl`	Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation. CoRR Ilias Diakonikolas, Daniel M. Kane, Daniel Kongsgaard, Jerry Li, Kevin Tian
2021	A*	`conf`	Efficiently learning halfspaces with Tsybakov noise. STOC Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis
2021	J	`jnl`	Forster Decomposition and Learning Halfspaces with Noise. CoRR Ilias Diakonikolas, Daniel M. Kane, Christos Tzamos
2021	J	`jnl`	Non-Gaussian Component Analysis via Lattice Basis Reduction. CoRR Ilias Diakonikolas, Daniel M. Kane
2021	A*	`conf`	Optimal testing of discrete distributions with high probability. STOC Ilias Diakonikolas, Themis Gouleakis, Daniel M. Kane, John Peebles, Eric Price
2021	A*	`conf`	Outlier-Robust Learning of Ising Models Under Dobrushin's Condition. COLT Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart, Yuxin Sun
2021	J	`jnl`	Outlier-Robust Learning of Ising Models Under Dobrushin's Condition. CoRR Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart, Yuxin Sun
2021	J	`jnl`	Outlier-Robust Sparse Estimation via Non-Convex Optimization. CoRR Yu Cheng, Ilias Diakonikolas, Daniel M. Kane, Rong Ge, Shivam Gupta, Mahdi Soltanolkotabi
2021	J	`jnl`	Prisoners, Rooms, and Light Switches. Electron. J. Comb. Daniel M. Kane, Scott Duke Kominers
2021	J	`jnl`	Quantum Money from Quaternion Algebras. CoRR Daniel M. Kane, Shahed Sharif, Alice Silverberg
2021	J	`jnl`	Quantum Money from Quaternion Algebras. IACR Cryptol. ePrint Arch. Daniel M. Kane, Shahed Sharif, Alice Silverberg
2021	J	`jnl`	Realizable Learning is All You Need. CoRR Max Hopkins, Daniel M. Kane, Shachar Lovett, Gaurav Mahajan
2021	A*	`conf`	Robust Learning of Mixtures of Gaussians. SODA Daniel M. Kane
2021	J	`jnl`	Robustness meets algorithms. Commun. ACM Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, Alistair Stewart
2021	J	`jnl`	Statistical Query Lower Bounds for List-Decodable Linear Regression. CoRR Ilias Diakonikolas, Daniel M. Kane, Ankit Pensia, Thanasis Pittas, Alistair Stewart
2021	A*	`conf`	The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals in the SQ Model. COLT Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas, Nikos Zarifis
2021	J	`jnl`	The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals. CoRR Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas, Nikos Zarifis
2021	A*	`conf`	The Sample Complexity of Robust Covariance Testing. COLT Ilias Diakonikolas, Daniel M. Kane
2021	J	`jnl`	Threshold Phenomena in Learning Halfspaces with Massart Noise. CoRR Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis
2020	J	`jnl`	A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise. CoRR Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis
2020	A*	`conf`	Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks. COLT Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Nikos Zarifis
2020	J	`jnl`	Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks. CoRR Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Nikos Zarifis
2020	J	`jnl`	Hardness of Learning Halfspaces with Massart Noise. CoRR Ilias Diakonikolas, Daniel M. Kane
2020	J	`jnl`	List-Decodable Mean Estimation in Nearly-PCA Time. CoRR Ilias Diakonikolas, Daniel M. Kane, Daniel Kongsgaard, Jerry Li, Kevin Tian
2020	J	`jnl`	List-Decodable Mean Estimation via Iterative Multi-Filtering. CoRR Ilias Diakonikolas, Daniel M. Kane, Daniel Kongsgaard
2020	J	`jnl`	Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals. CoRR Ilias Diakonikolas, Daniel M. Kane, Nikos Zarifis
2020	J	`jnl`	Optimal Testing of Discrete Distributions with High Probability. CoRR Ilias Diakonikolas, Themis Gouleakis, Daniel M. Kane, John Peebles, Eric Price
2020	A*	`conf`	Outlier Robust Mean Estimation with Subgaussian Rates via Stability. NeurIPS Ilias Diakonikolas, Daniel M. Kane, Ankit Pensia
2020	J	`jnl`	Outlier Robust Mean Estimation with Subgaussian Rates via Stability. CoRR Ilias Diakonikolas, Daniel M. Kane, Ankit Pensia
2020	J	`jnl`	Point Location and Active Learning: Learning Halfspaces Almost Optimally. CoRR Max Hopkins, Daniel M. Kane, Shachar Lovett, Gaurav Mahajan
2020	J	`jnl`	Prisoners, Rooms, and Lightswitches. CoRR Daniel M. Kane, Scott Duke Kominers
2020	—	`ch.`	Robust High-Dimensional Statistics. Beyond the Worst-Case Analysis of Algorithms Ilias Diakonikolas, Daniel M. Kane
2020	J	`jnl`	Robust Learning of Mixtures of Gaussians. CoRR Daniel M. Kane
2020	J	`jnl`	Robustly Learning Mixtures of k Arbitrary Gaussians. CoRR Ainesh Bakshi, Ilias Diakonikolas, He Jia, Daniel M. Kane, Pravesh K. Kothari, Santosh S. Vempala
2020	A*	`conf`	Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models. FOCS Ilias Diakonikolas, Daniel M. Kane
2020	J	`jnl`	Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models. CoRR Ilias Diakonikolas, Daniel M. Kane
2020	J	`jnl`	Testing Bayesian Networks. IEEE Trans. Inf. Theory Clément L. Canonne, Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart
2020	A*	`conf`	The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise. NeurIPS Ilias Diakonikolas, Daniel M. Kane, Pasin Manurangsi
2020	J	`jnl`	The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise. CoRR Ilias Diakonikolas, Daniel M. Kane, Pasin Manurangsi
2020	J	`jnl`	The Sample Complexity of Robust Covariance Testing. CoRR Ilias Diakonikolas, Daniel M. Kane
2019	A*	`conf`	Communication and Memory Efficient Testing of Discrete Distributions. COLT Ilias Diakonikolas, Themis Gouleakis, Daniel M. Kane, Sankeerth Rao
2019	J	`jnl`	Communication and Memory Efficient Testing of Discrete Distributions. CoRR Ilias Diakonikolas, Themis Gouleakis, Daniel M. Kane, Sankeerth Rao
2019	A*	`conf`	Degree-푑 chow parameters robustly determine degree-푑 PTFs (and algorithmic applications). STOC Ilias Diakonikolas, Daniel M. Kane
2019	A*	`conf`	Learning Ising Models with Independent Failures. COLT Surbhi Goel, Daniel M. Kane, Adam R. Klivans
2019	J	`jnl`	Learning Ising Models with Independent Failures. CoRR Surbhi Goel, Daniel M. Kane, Adam R. Klivans
2019	J	`jnl`	Near-optimal Linear Decision Trees for k-SUM and Related Problems. J. ACM Daniel M. Kane, Shachar Lovett, Shay Moran
2019	J	`jnl`	Nearly Tight Bounds for Robust Proper Learning of Halfspaces with a Margin. CoRR Ilias Diakonikolas, Daniel M. Kane, Pasin Manurangsi
2019	J	`jnl`	Recent Advances in Algorithmic High-Dimensional Robust Statistics. CoRR Ilias Diakonikolas, Daniel M. Kane
2019	A*	`conf`	Testing Identity of Multidimensional Histograms. COLT Ilias Diakonikolas, Daniel M. Kane, John Peebles
2019	A	`conf`	The Orthogonal Vectors Conjecture for Branching Programs and Formulas. ITCS Daniel M. Kane, Richard Ryan Williams
2019	J	`jnl`	The Power of Comparisons for Actively Learning Linear Classifiers. CoRR Max Hopkins, Daniel M. Kane, Shachar Lovett
2019	J	`jnl`	Waring's Theorem for Binary Powers. Comb. Daniel M. Kane, Carlo Sanna, Jeffrey O. Shallit
2018	J	`jnl`	Degree-d Chow Parameters Robustly Determine Degree-d PTFs (and Algorithmic Applications). CoRR Ilias Diakonikolas, Daniel M. Kane
2018	A*	`conf`	Generalized Comparison Trees for Point-Location Problems. ICALP Daniel M. Kane, Shachar Lovett, Shay Moran
2018	J	`jnl`	Generalized comparison trees for point-location problems. CoRR Daniel M. Kane, Shachar Lovett, Shay Moran
2018	J	`jnl`	Generalized comparison trees for point-location problems. Electron. Colloquium Comput. Complex. Daniel M. Kane, Shachar Lovett, Shay Moran
2018	A*	`conf`	Learning geometric concepts with nasty noise. STOC Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart
2018	A*	`conf`	List-decodable robust mean estimation and learning mixtures of spherical gaussians. STOC Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart
2018	A*	`conf`	Near-optimal linear decision trees for k-SUM and related problems. STOC Daniel M. Kane, Shachar Lovett, Shay Moran
2018	J	`jnl`	Pseudorandomness via the Discrete Fourier Transform. SIAM J. Comput. Parikshit Gopalan, Daniel M. Kane, Raghu Meka
2018	J	`jnl`	Quantum Money from Modular Forms. CoRR Daniel M. Kane
2018	A*	`conf`	Robustly Learning a Gaussian: Getting Optimal Error, Efficiently. SODA Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, Alistair Stewart
2018	J	`jnl`	Sever: A Robust Meta-Algorithm for Stochastic Optimization. CoRR Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Jacob Steinhardt, Alistair Stewart
2018	A*	`conf`	Sharp Bounds for Generalized Uniformity Testing. NeurIPS Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart
2018	Misc	`conf`	Testing Conditional Independence of Discrete Distributions. ITA Clément L. Canonne, Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart
2018	J	`jnl`	Testing Identity of Multidimensional Histograms. CoRR Ilias Diakonikolas, Daniel M. Kane, John Peebles
2018	A*	`conf`	Testing conditional independence of discrete distributions. STOC Clément L. Canonne, Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart
2018	J	`jnl`	Waring's Theorem for Binary Powers. CoRR Daniel M. Kane, Carlo Sanna, Jeffrey O. Shallit
2017	J	`jnl`	A Polynomial Restriction Lemma with Applications. Electron. Colloquium Comput. Complex. Valentine Kabanets, Daniel M. Kane, Zhenjian Lu
2017	A*	`conf`	A polynomial restriction lemma with applications. STOC Valentine Kabanets, Daniel M. Kane, Zhenjian Lu
2017	A*	`conf`	Active Classification with Comparison Queries. FOCS Daniel M. Kane, Shachar Lovett, Shay Moran, Jiapeng Zhang
2017	J	`jnl`	Active classification with comparison queries. CoRR Daniel M. Kane, Shachar Lovett, Shay Moran, Jiapeng Zhang
2017	J	`jnl`	Active classification with comparison queries. Electron. Colloquium Comput. Complex. Daniel M. Kane, Shachar Lovett, Shay Moran, Jiapeng Zhang
2017	A*	`conf`	Being Robust (in High Dimensions) Can Be Practical. ICML Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, Alistair Stewart
2017	J	`jnl`	Being Robust (in High Dimensions) Can Be Practical. CoRR Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, Alistair Stewart
2017	J	`jnl`	Labeling the complete bipartite graph with no zero cycles. CoRR Daniel M. Kane, Shachar Lovett, Sankeerth Rao
2017	J	`jnl`	Labeling the complete bipartite graph with no zero cycles. Electron. Colloquium Comput. Complex. Daniel M. Kane, Shachar Lovett, Sankeerth Rao
2017	J	`jnl`	Learning Geometric Concepts with Nasty Noise. CoRR Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart
2017	A*	`conf`	Learning Multivariate Log-concave Distributions. COLT Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart
2017	J	`jnl`	List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussians. CoRR Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart
2017	A*	`conf`	Near-Optimal Closeness Testing of Discrete Histogram Distributions. ICALP Ilias Diakonikolas, Daniel M. Kane, Vladimir Nikishkin
2017	J	`jnl`	Near-Optimal Closeness Testing of Discrete Histogram Distributions. CoRR Ilias Diakonikolas, Daniel M. Kane, Vladimir Nikishkin
2017	J	`jnl`	Near-optimal linear decision trees for k-SUM and related problems. CoRR Daniel M. Kane, Shachar Lovett, Shay Moran
2017	J	`jnl`	Near-optimal linear decision trees for k-SUM and related problems. Electron. Colloquium Comput. Complex. Daniel M. Kane, Shachar Lovett, Shay Moran
2017	J	`jnl`	On Communication Complexity of Classification Problems. CoRR Daniel M. Kane, Roi Livni, Shay Moran, Amir Yehudayoff
2017	J	`jnl`	On Communication Complexity of Classification Problems. Electron. Colloquium Comput. Complex. Daniel M. Kane, Roi Livni, Shay Moran, Amir Yehudayoff
2017	J	`jnl`	Robust polynomial regression up to the information theoretic limit. CoRR Daniel M. Kane, Sushrut Karmalkar, Eric Price
2017	J	`jnl`	Robustly Learning a Gaussian: Getting Optimal Error, Efficiently. CoRR Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, Alistair Stewart
2017	J	`jnl`	Sharp Bounds for Generalized Uniformity Testing. CoRR Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart
2017	J	`jnl`	Sharp Bounds for Generalized Uniformity Testing. Electron. Colloquium Comput. Complex. Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart
2017	A*	`conf`	Statistical Query Lower Bounds for Robust Estimation of High-Dimensional Gaussians and Gaussian Mixtures. FOCS Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart
2017	A*	`conf`	Testing Bayesian Networks. COLT Clément L. Canonne, Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart
2017	J	`jnl`	Testing Conditional Independence of Discrete Distributions. CoRR Clément L. Canonne, Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart
2017	J	`jnl`	The Orthogonal Vectors Conjecture for Branching Programs and Formulas. CoRR Daniel M. Kane, R. Ryan Williams
2016	A*	`conf`	A New Approach for Testing Properties of Discrete Distributions. FOCS Ilias Diakonikolas, Daniel M. Kane
2016	J	`jnl`	A New Approach for Testing Properties of Discrete Distributions. CoRR Ilias Diakonikolas, Daniel M. Kane
2016	J	`jnl`	A New Approach for Testing Properties of Discrete Distributions. Electron. Colloquium Comput. Complex. Ilias Diakonikolas, Daniel M. Kane
2016	J	`jnl`	Efficient Robust Proper Learning of Log-concave Distributions. CoRR Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart
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`	Learning Multivariate Log-concave Distributions. CoRR Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart
2016	A*	`conf`	Optimal Learning via the Fourier Transform for Sums of Independent Integer Random Variables. COLT Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart
2016	A*	`conf`	Properly Learning Poisson Binomial Distributions in Almost Polynomial Time. COLT Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart
2016	A*	`conf`	Robust Estimators in High Dimensions without the Computational Intractability. FOCS Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, Alistair Stewart
2016	J	`jnl`	Robust Estimators in High Dimensions without the Computational Intractability. CoRR Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Zheng Li, Ankur Moitra, Alistair Stewart
2016	J	`jnl`	Robust Learning of Fixed-Structure Bayesian Networks. CoRR Yu Cheng, Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart
2016	J	`jnl`	Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures. CoRR Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart
2016	J	`jnl`	Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures. Electron. Colloquium Comput. Complex. Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart
2016	A*	`conf`	Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits. STOC Daniel M. Kane, Ryan Williams
2016	J	`jnl`	Testing Bayesian Networks. CoRR Clément L. Canonne, Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart
2016	A*	`conf`	The fourier transform of poisson multinomial distributions and its algorithmic applications. STOC Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart
2015	A	`conf`	A Polylogarithmic PRG for Degree 2 Threshold Functions in the Gaussian Setting. CCC Daniel M. Kane
2015	J	`jnl`	Central limit theorems for some set partition statistics. Adv. Appl. Math. Bobbie Chern, Persi Diaconis, Daniel M. Kane, Robert C. Rhoades
2015	J	`jnl`	Nearly Optimal Learning and Sparse Covers for Sums of Independent Integer Random Variables. CoRR Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart
2015	A*	`conf`	Optimal Algorithms and Lower Bounds for Testing Closeness of Structured Distributions. FOCS Ilias Diakonikolas, Daniel M. Kane, Vladimir Nikishkin
2015	J	`jnl`	Optimal Algorithms and Lower Bounds for Testing Closeness of Structured Distributions. CoRR Ilias Diakonikolas, Daniel M. Kane, Vladimir Nikishkin
2015	J	`jnl`	Properly Learning Poisson Binomial Distributions in Almost Polynomial Time. CoRR Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart
2015	A*	`conf`	Pseudorandomness via the Discrete Fourier Transform. FOCS Parikshit Gopalan, Daniel M. Kane, Raghu Meka
2015	J	`jnl`	Pseudorandomness via the discrete Fourier transform. CoRR Parikshit Gopalan, Daniel M. Kane, Raghu Meka
2015	J	`jnl`	Super-Linear Gate and Super-Quadratic Wire Lower Bounds for Depth-Two and Depth-Three Threshold Circuits. CoRR Daniel M. Kane, Ryan Williams
2015	J	`jnl`	Super-Linear Gate and Super-Quadratic Wire Lower Bounds for Depth-Two and Depth-Three Threshold Circuits. Electron. Colloquium Comput. Complex. Daniel M. Kane, Ryan Williams
2015	A*	`conf`	Testing Identity of Structured Distributions. SODA Ilias Diakonikolas, Daniel M. Kane, Vladimir Nikishkin
2015	J	`jnl`	The Fourier Transform of Poisson Multinomial Distributions and its Algorithmic Applications. CoRR Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart
2014	J	`jnl`	A Polylogarithmic PRG for Degree $2$ Threshold Functions in the Gaussian Setting. CoRR Daniel M. Kane
2014	A	`conf`	A Pseudorandom Generator for Polynomial Threshold Functions of Gaussian with Subpolynomial Seed Length. CCC Daniel M. Kane
2014	B	`conf`	A Short Implicant of a CNF Formula with Many Satisfying Assignments. ISAAC Daniel M. Kane, Osamu Watanabe
2014	J	`jnl`	Pseudorandomness for concentration bounds and signed majorities. CoRR Parikshit Gopalan, Daniel M. Kane, Raghu Meka
2014	J	`jnl`	Sparser Johnson-Lindenstrauss Transforms. J. ACM Daniel M. Kane, Jelani Nelson
2014	J	`jnl`	Testing Identity of Structured Distributions. CoRR Ilias Diakonikolas, Daniel M. Kane, Vladimir Nikishkin
2014	A*	`conf`	The average sensitivity of an intersection of half spaces. STOC Daniel M. Kane
2014	J	`jnl`	The correct exponent for the Gotsman-Linial Conjecture. Comput. Complex. Daniel M. Kane
2013	J	`jnl`	A Monotone Function Given By a Low-Depth Decision Tree That Is Not an Approximate Junta. Theory Comput. Daniel M. Kane
2013	A*	`conf`	A PRG for lipschitz functions of polynomials with applications to sparsest cut. STOC Daniel M. Kane, Raghu Meka
2013	J	`jnl`	A Short Implicant of CNFs with Relatively Many Satisfying Assignments. Electron. Colloquium Comput. Complex. Daniel M. Kane, Osamu Watanabe
2013	A*	`conf`	Learning Halfspaces Under Log-Concave Densities: Polynomial Approximations and Moment Matching. COLT Daniel M. Kane, Adam R. Klivans, Raghu Meka
2013	J	`jnl`	The Average Sensitivity of an Intersection of Half Spaces. CoRR Daniel M. Kane
2013	A	`conf`	The Correct Exponent for the Gotsman-Linial Conjecture. CCC Daniel M. Kane
2012	J	`jnl`	A Low-Depth Monotone Function that is not an Approximate Junta CoRR Daniel M. Kane
2012	J	`jnl`	A PRG for Lipschitz Functions of Polynomials with Applications to Sparsest Cut CoRR Daniel M. Kane, Raghu Meka
2012	J	`jnl`	A Pseudorandom Generator for Polynomial Threshold Functions of Gaussian with Subpolynomial Seed Length CoRR Daniel M. Kane
2012	A*	`conf`	A Structure Theorem for Poorly Anticoncentrated Gaussian Chaoses and Applications to the Study of Polynomial Threshold Functions. FOCS Daniel M. Kane
2012	J	`jnl`	A Structure Theorem for Poorly Poorly Anticoncentrated Gaussian Chaoses and Applications to the Study of Polynomial Threshold Functions. CoRR Daniel M. Kane
2012	—	`conf`	Counting Arbitrary Subgraphs in Data Streams. ICALP (2) Daniel M. Kane, Kurt Mehlhorn, Thomas Sauerwald, He Sun
2012	A*	`conf`	Sparser Johnson-Lindenstrauss transforms. SODA Daniel M. Kane, Jelani Nelson
2012	J	`jnl`	The Correct Exponent for the Gotsman-Linial Conjecture CoRR Daniel M. Kane
2012	—	`conf`	Tight Bounds for Testing k-Linearity. APPROX-RANDOM Eric Blais, Daniel M. Kane
2011	J	`jnl`	A Small PRG for Polynomial Threshold Functions of Gaussians CoRR Daniel M. Kane
2011	A*	`conf`	A Small PRG for Polynomial Threshold Functions of Gaussians. FOCS Daniel M. Kane
2011	A*	`conf`	Fast moment estimation in data streams in optimal space. STOC Daniel M. Kane, Jelani Nelson, Ely Porat, David P. Woodruff
2011	J	`jnl`	Quantum interpolation of polynomials. Quantum Inf. Comput. Daniel M. Kane, Samuel A. Kutin
2011	J	`jnl`	The Gaussian Surface Area and Noise Sensitivity of Degree- Comput. Complex. Daniel M. Kane
2011	A	`conf`	k-Independent Gaussians Fool Polynomial Threshold Functions. CCC Daniel M. Kane
2010	J	`jnl`	A Derandomized Sparse Johnson-Lindenstrauss Transform CoRR Daniel M. Kane, Jelani Nelson
2010	J	`jnl`	A Derandomized Sparse Johnson-Lindenstrauss Transform. Electron. Colloquium Comput. Complex. Daniel M. Kane, Jelani Nelson
2010	J	`jnl`	A Sparser Johnson-Lindenstrauss Transform CoRR Daniel M. Kane, Jelani Nelson
2010	A*	`conf`	An optimal algorithm for the distinct elements problem. PODS Daniel M. Kane, Jelani Nelson, David P. Woodruff
2010	A*	`conf`	Bounded Independence Fools Degree-2 Threshold Functions. FOCS Ilias Diakonikolas, Daniel M. Kane, Jelani Nelson
2010	J	`jnl`	Fast Moment Estimation in Data Streams in Optimal Space CoRR Daniel M. Kane, Jelani Nelson, Ely Porat, David P. Woodruff
2010	J	`jnl`	On Solving Games Constructed Using Both Short and Long Conjunctive Sums. Integers Daniel M. Kane
2010	A*	`conf`	On the Exact Space Complexity of Sketching and Streaming Small Norms. SODA Daniel M. Kane, Jelani Nelson, David P. Woodruff
2010	A	`conf`	The Gaussian Surface Area and Noise Sensitivity of Degree-d Polynomial Threshold Functions. CCC Daniel M. Kane
2010	J	`jnl`	Unary Subset-Sum is in Logspace CoRR Daniel M. Kane
2010	J	`jnl`	k-Independent Gaussians Fool Polynomial Threshold Functions CoRR Daniel M. Kane
2009	J	`jnl`	Bounded Independence Fools Degree-2 Threshold Functions CoRR Ilias Diakonikolas, Daniel M. Kane, Jelani Nelson
2009	J	`jnl`	Bounded Independence Fools Degree-2 Threshold Functions. Electron. Colloquium Comput. Complex. Ilias Diakonikolas, Daniel M. Kane, Jelani Nelson
2009	J	`jnl`	Quantum interpolation of polynomials CoRR Daniel M. Kane, Samuel A. Kutin
2009	J	`jnl`	The Gaussian Surface Area and Noise Sensitivity of Degree-$d$ Polynomials CoRR Daniel M. Kane
2008	J	`jnl`	Revisiting Norm Estimation in Data Streams CoRR Daniel M. Kane, Jelani Nelson, David P. Woodruff