Daniel Kane

Publication Activity (10 Years)

Years Active: 2010-2024
Publications (10 Years): 71

Top Topics

Linear Classifiers

Top Venues

Electron. Colloquium Comput. Complex.

Publications

Daniel Kane, Anthony Ostuni, Kewen Wu
Locality Bounds for Sampling Hamming Slices. Electron. Colloquium Comput. Complex. (2024)
Ilias Diakonikolas, Daniel Kane, Vasilis Kontonis, Sihan Liu, Nikos Zarifis
Efficient Testable Learning of Halfspaces with Adversarial Label Noise. NeurIPS (2023)
Ilias Diakonikolas, Daniel Kane, Ankit Pensia, Thanasis Pittas
Nearly-Linear Time and Streaming Algorithms for Outlier-Robust PCA. ICML (2023)
Daniel Beaglehole, Max Hopkins, Daniel Kane, Sihan Liu, Shachar Lovett
Sampling Equilibria: Fast No-Regret Learning in Structured Games. SODA (2023)
Ilias Diakonikolas, Daniel Kane, Lisheng Ren
Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginals. ICML (2023)
Ilias Diakonikolas, Daniel Kane, Yuxin Sun
SQ Lower Bounds for Learning Mixtures of Linear Classifiers. NeurIPS (2023)
Ilias Diakonikolas, Jelena Diakonikolas, Daniel Kane, Puqian Wang, Nikos Zarifis
Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise. NeurIPS (2023)
Ilias Diakonikolas, Daniel Kane, Lisheng Ren, Yuxin Sun
SQ Lower Bounds for Non-Gaussian Component Analysis with Weaker Assumptions. NeurIPS (2023)
Ilias Diakonikolas, Daniel Kane, Ankit Pensia, Thanasis Pittas
Near-Optimal Algorithms for Gaussians with Huber Contamination: Mean Estimation and Linear Regression. NeurIPS (2023)
Daniel Kane, Sihan Liu, Shachar Lovett, Gaurav Mahajan, Csaba Szepesvári, Gellért Weisz
Exponential Hardness of Reinforcement Learning with Linear Function Approximation. CoRR (2023)
Ilias Diakonikolas, Daniel Kane, Jasper C. H. Lee, Ankit Pensia, Thanasis Pittas
A Spectral Algorithm for List-Decodable Covariance Estimation in Relative Frobenius Norm. NeurIPS (2023)
Daniel Kane, Ilias Diakonikolas
A Nearly Tight Bound for Fitting an Ellipsoid to Gaussian Random Points. COLT (2023)
Sihan Liu, Gaurav Mahajan, Daniel Kane, Shachar Lovett, Gellért Weisz, Csaba Szepesvári
Exponential Hardness of Reinforcement Learning with Linear Function Approximation. COLT (2023)
Ilias Diakonikolas, Daniel Kane
Non-Gaussian Component Analysis via Lattice Basis Reduction. COLT (2022)
Yu Cheng, Ilias Diakonikolas, Rong Ge, Shivam Gupta, Daniel Kane, Mahdi Soltanolkotabi
Outlier-Robust Sparse Estimation via Non-Convex Optimization. NeurIPS (2022)
Daniel Kane, Sihan Liu, Shachar Lovett, Gaurav Mahajan
Computational-Statistical Gap in Reinforcement Learning. COLT (2022)
Daniel Kane, Sihan Liu, Shachar Lovett, Gaurav Mahajan
Computational-Statistical Gaps in Reinforcement Learning. CoRR (2022)
Clément L. Canonne, Ilias Diakonikolas, Daniel Kane, Sihan Liu
Nearly-Tight Bounds for Testing Histogram Distributions. NeurIPS (2022)
Ilias Diakonikolas, Daniel Kane, Sushrut Karmalkar, Ankit Pensia, Thanasis Pittas
List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filtering. NeurIPS (2022)
Venkata Gandikota, Daniel Kane, Raj Kumar Maity, Arya Mazumdar
vqSGD: Vector Quantized Stochastic Gradient Descent. IEEE Trans. Inf. Theory 68 (7) (2022)
Ilias Diakonikolas, Daniel Kane, Jasper C. H. Lee, Ankit Pensia
Outlier-Robust Sparse Mean Estimation for Heavy-Tailed Distributions. NeurIPS (2022)
Ilias Diakonikolas, Daniel Kane
Near-Optimal Statistical Query Hardness of Learning Halfspaces with Massart Noise. COLT (2022)
Ilias Diakonikolas, Daniel Kane, Pasin Manurangsi, Lisheng Ren
Hardness of Learning a Single Neuron with Adversarial Label Noise. AISTATS (2022)
Ilias Diakonikolas, Christos Tzamos, Daniel Kane
A Strongly Polynomial Algorithm for Approximate Forster Transforms and its Application to Halfspace Learning. Electron. Colloquium Comput. Complex. (2022)
Alaa Maalouf, Murad Tukan, Eric Price, Daniel Kane, Dan Feldman
Coresets for Data Discretization and Sine Wave Fitting. CoRR (2022)
Ilias Diakonikolas, Daniel Kane, Pasin Manurangsi, Lisheng Ren
Cryptographic Hardness of Learning Halfspaces with Massart Noise. NeurIPS (2022)
Ilias Diakonikolas, Daniel Kane, Lisheng Ren, Yuxin Sun
SQ Lower Bounds for Learning Single Neurons with Massart Noise. NeurIPS (2022)
Max Hopkins, Daniel Kane, Shachar Lovett, Gaurav Mahajan
Realizable Learning is All You Need. CoRR (2021)
Max Hopkins, Daniel Kane, Shachar Lovett, Michal Moshkovitz
Bounded Memory Active Learning through Enriched Queries. COLT (2021)
Ilias Diakonikolas, Daniel Kane, Christos Tzamos
Forster Decomposition and Learning Halfspaces with Noise. NeurIPS (2021)
Daniel Kane, Andreas Fackler, Adam Gagol, Damian Straszak
Highway: Efficient Consensus with Flexible Finality. CoRR (2021)
Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan, Daniel Kane
Fooling Gaussian PTFs via Local Hyperconcentration. CoRR (2021)
Max Hopkins, Daniel Kane, Shachar Lovett, Michal Moshkovitz
Bounded Memory Active Learning through Enriched Queries. CoRR (2021)
Venkata Gandikota, Daniel Kane, Raj Kumar Maity, Arya Mazumdar
vqSGD: Vector Quantized Stochastic Gradient Descent. AISTATS (2021)
Ilias Diakonikolas, Daniel Kane, Daniel Kongsgaard, Jerry Li, Kevin Tian
List-Decodable Mean Estimation in Nearly-PCA Time. NeurIPS (2021)
Yuval Dagan, Yuval Filmus, Daniel Kane, Shay Moran
The Entropy of Lies: Playing Twenty Questions with a Liar. ITCS (2021)
Ilias Diakonikolas, Russell Impagliazzo, Daniel Kane, Rex Lei, Jessica Sorrell, Christos Tzamos
Boosting in the Presence of Massart Noise. CoRR (2021)
Ilias Diakonikolas, Daniel Kane, Ankit Pensia, Thanasis Pittas, Alistair Stewart
Statistical Query Lower Bounds for List-Decodable Linear Regression. NeurIPS (2021)
Max Hopkins, Daniel Kane, Shachar Lovett, Gaurav Mahajan
Point Location and Active Learning: Learning Halfspaces Almost Optimally. FOCS (2020)
Ainesh Bakshi, Ilias Diakonikolas, Samuel B. Hopkins, Daniel Kane, Sushrut Karmalkar, Pravesh K. Kothari
Outlier-Robust Clustering of Gaussians and Other Non-Spherical Mixtures. FOCS (2020)
Max Hopkins, Daniel Kane, Shachar Lovett
The Power of Comparisons for Actively Learning Linear Classifiers. NeurIPS (2020)
Ilias Diakonikolas, Daniel Kane, Daniel Kongsgaard
List-Decodable Mean Estimation via Iterative Multi-Filtering. NeurIPS (2020)
Ilias Diakonikolas, Themis Gouleakis, Daniel Kane, John Peebles, Eric Price
Optimal Testing of Discrete Distributions with High Probability. Electron. Colloquium Comput. Complex. 27 (2020)
Ilias Diakonikolas, Daniel Kane, Nikos Zarifis
Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals. NeurIPS (2020)
Max Hopkins, Daniel Kane, Shachar Lovett, Gaurav Mahajan
Noise-tolerant, Reliable Active Classification with Comparison Queries. COLT (2020)
Max Hopkins, Daniel Kane, Shachar Lovett, Gaurav Mahajan
Noise-tolerant, Reliable Active Classification with Comparison Queries. CoRR (2020)
Ilias Diakonikolas, Samuel B. Hopkins, Daniel Kane, Sushrut Karmalkar
Robustly Learning any Clusterable Mixture of Gaussians. CoRR (2020)
Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Jacob Steinhardt, Alistair Stewart
Sever: A Robust Meta-Algorithm for Stochastic Optimization. ICML (2019)
Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Ankur Moitra, Alistair Stewart
Robust Estimators in High-Dimensions Without the Computational Intractability. SIAM J. Comput. 48 (2) (2019)
Daniel Kane, Roi Livni, Shay Moran, Amir Yehudayoff
On Communication Complexity of Classification Problems. COLT (2019)
Ilgweon Kang, Fang Qiao, Dongwon Park, Daniel Kane, Evangeline F. Y. Young, Chung-Kuan Cheng, Ronald L. Graham
Three-dimensional Floorplan Representations by Using Corner Links and Partial Order. ACM Trans. Design Autom. Electr. Syst. 24 (1) (2019)
Olivier Bousquet, Daniel Kane, Shay Moran
The Optimal Approximation Factor in Density Estimation. CoRR (2019)
Ilias Diakonikolas, Daniel Kane, Pasin Manurangsi
Nearly Tight Bounds for Robust Proper Learning of Halfspaces with a Margin. NeurIPS (2019)
Olivier Bousquet, Daniel Kane, Shay Moran
The Optimal Approximation Factor in Density Estimation. COLT (2019)
Ilias Diakonikolas, Sushrut Karmalkar, Daniel Kane, Eric Price, Alistair Stewart
Outlier-Robust High-Dimensional Sparse Estimation via Iterative Filtering. CoRR (2019)
Maryam Aliakbarpour, Ilias Diakonikolas, Daniel Kane, Ronitt Rubinfeld
Private Testing of Distributions via Sample Permutations. NeurIPS (2019)
Daniel Kane, Shachar Lovett, Sankeerth Rao
The Independence Number of the Birkhoff Polytope Graph, and Applications to Maximally Recoverable Codes. SIAM J. Comput. 48 (4) (2019)
Ilias Diakonikolas, Daniel Kane, Sushrut Karmalkar, Eric Price, Alistair Stewart
Outlier-Robust High-Dimensional Sparse Estimation via Iterative Filtering. NeurIPS (2019)
Daniel Kane, Sankeerth Rao
A PRG for Boolean PTF of Degree 2 with Seed Length Subpolynomial in epsilon and Logarithmic in n. Computational Complexity Conference (2018)
Yu Cheng, Ilias Diakonikolas, Daniel Kane, Alistair Stewart
Robust Learning of Fixed-Structure Bayesian Networks. NeurIPS (2018)
Ilias Diakonikolas, Daniel Kane
Degree-$d$ Chow Parameters Robustly Determine Degree-$d$ PTFs (and Algorithmic Applications). Electron. Colloquium Comput. Complex. 25 (2018)
Yuval Dagan, Yuval Filmus, Daniel Kane, Shay Moran
The entropy of lies: playing twenty questions with a liar. CoRR (2018)
Daniel Kane, Shachar Lovett, Sankeerth Rao
The Independence Number of the Birkhoff Polytope Graph, and Applications to Maximally Recoverable Codes. FOCS (2017)
Daniel Kane, Sushrut Karmalkar, Eric Price
Robust Polynomial Regression up to the Information Theoretic Limit. FOCS (2017)
Daniel Kane, Terence Tao
A Bound on Partitioning Clusters. Electron. J. Comb. 24 (2) (2017)
Mihir Bellare, Daniel Kane, Phillip Rogaway
Big-Key Symmetric Encryption: Resisting Key Exfiltration. CRYPTO (1) (2016)
Fang Qiao, Ilgweon Kang, Daniel Kane, Fung Yu Young, Chung-Kuan Cheng, Ronald L. Graham
3D floorplan representations: Corner links and partial order. 3DIC (2016)
Mihir Bellare, Daniel Kane, Phillip Rogaway
Big-Key Symmetric Encryption: Resisting Key Exfiltration. IACR Cryptol. ePrint Arch. 2016 (2016)
Daniel Kane, Osamu Watanabe
A Short Implicant of a CNF Formula with Many Satisfying Assignments. Algorithmica 76 (4) (2016)
Mihir Bellare, Joseph Jaeger, Daniel Kane
Mass-surveillance without the State: Strongly Undetectable Algorithm-Substitution Attacks. IACR Cryptol. ePrint Arch. 2015 (2015)
Mihir Bellare, Joseph Jaeger, Daniel Kane
Mass-surveillance without the State: Strongly Undetectable Algorithm-Substitution Attacks. CCS (2015)
Daniel Kane, Raghu Meka, Jelani Nelson
Almost Optimal Explicit Johnson-Lindenstrauss Transformations. Electron. Colloquium Comput. Complex. (2010)