![](https://dblp.uni-trier.de/img/logo.ua.320x120.png)
![](https://dblp.uni-trier.de/img/dropdown.dark.16x16.png)
![](https://dblp.uni-trier.de/img/peace.dark.16x16.png)
Остановите войну!
for scientists:
![search dblp search dblp](https://dblp.uni-trier.de/img/search.dark.16x16.png)
![search dblp](https://dblp.uni-trier.de/img/search.dark.16x16.png)
default search action
Daniel M. Kane
Person information
- affiliation: University of California, San Diego, Department of Computer Science and Engineering, La Jolla, CA, USA
- affiliation (2011-2014): Stanford University, Department of Mathematics, Stanford, CA, USA
- affiliation (PhD 2011): Harvard University, Department of Mathematics, Cambridge, MA, USA
- affiliation (former): Massachusetts Institute of Technology (MIT), Computer Science and Artificial Intelligence Laboratory (CSAIL), Cambridge, MA, USA
Other persons with the same name
- Daniel Kane 0002
— Utah State University, Logan, UT, USA
Refine list
![note](https://dblp.uni-trier.de/img/note-mark.dark.12x12.png)
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
Journal Articles
- 2024
- [j22]Max Hopkins, Daniel M. Kane, Shachar Lovett, Gaurav Mahajan:
Realizable Learning is All You Need. TheoretiCS 3 (2024) - 2022
- [j21]Venkata Gandikota
, Daniel Kane, Raj Kumar Maity
, Arya Mazumdar
:
vqSGD: Vector Quantized Stochastic Gradient Descent. IEEE Trans. Inf. Theory 68(7): 4573-4587 (2022) - 2021
- [j20]Ilias Diakonikolas, Gautam Kamath
, Daniel M. Kane, Jerry Li, Ankur Moitra, Alistair Stewart:
Robustness meets algorithms. Commun. ACM 64(5): 107-115 (2021) - [j19]Daniel M. Kane, Scott Duke Kominers:
Prisoners, Rooms, and Light Switches. Electron. J. Comb. 28(1): 1 (2021) - 2020
- [j18]Clément L. Canonne
, Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart:
Testing Bayesian Networks. IEEE Trans. Inf. Theory 66(5): 3132-3170 (2020) - 2019
- [j17]Daniel M. Kane, Carlo Sanna
, Jeffrey O. Shallit:
Waring's Theorem for Binary Powers. Comb. 39(6): 1335-1350 (2019) - [j16]Daniel M. Kane, Shachar Lovett
, Shay Moran:
Near-optimal Linear Decision Trees for k-SUM and Related Problems. J. ACM 66(3): 16:1-16:18 (2019) - [j15]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): 742-864 (2019) - [j14]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): 1425-1435 (2019) - [j13]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): 13:1-13:33 (2019) - 2018
- [j12]Parikshit Gopalan, Daniel M. Kane, Raghu Meka:
Pseudorandomness via the Discrete Fourier Transform. SIAM J. Comput. 47(6): 2451-2487 (2018) - 2017
- [j11]Daniel Kane, Terence Tao:
A Bound on Partitioning Clusters. Electron. J. Comb. 24(2): 2 (2017) - 2016
- [j10]Daniel Kane, Osamu Watanabe
:
A Short Implicant of a CNF Formula with Many Satisfying Assignments. Algorithmica 76(4): 1203-1223 (2016) - 2015
- [j9]Bobbie Chern, Persi Diaconis, Daniel M. Kane, Robert C. Rhoades:
Central limit theorems for some set partition statistics. Adv. Appl. Math. 70: 92-105 (2015) - 2014
- [j8]Daniel M. Kane:
The correct exponent for the Gotsman-Linial Conjecture. Comput. Complex. 23(2): 151-175 (2014) - [j7]Daniel M. Kane, Jelani Nelson:
Sparser Johnson-Lindenstrauss Transforms. J. ACM 61(1): 4:1-4:23 (2014) - 2013
- [j6]Daniel M. Kane:
A Monotone Function Given By a Low-Depth Decision Tree That Is Not an Approximate Junta. Theory Comput. 9: 587-592 (2013) - 2011
- [j5]Daniel M. Kane:
The Gaussian Surface Area and Noise Sensitivity of Degree-d Polynomial Threshold Functions. Comput. Complex. 20(2): 389-412 (2011) - [j4]Daniel M. Kane, Samuel A. Kutin:
Quantum interpolation of polynomials. Quantum Inf. Comput. 11(1&2): 95-103 (2011) - 2010
- [j3]Daniel M. Kane:
On Solving Games Constructed Using Both Short and Long Conjunctive Sums. Integers 10: G4 (2010) - 2009
- [j2]Timothy G. Abbott, Michael A. Burr
, Timothy M. Chan, Erik D. Demaine, Martin L. Demaine, John Hugg, Daniel Kane, Stefan Langerman
, Jelani Nelson, Eynat Rafalin, Kathryn Seyboth, Vincent Yeung:
Dynamic ham-sandwich cuts in the plane. Comput. Geom. 42(5): 419-428 (2009) - 2008
- [j1]Daniel Kane, Steven Sivek:
On the Sn-Modules Generated by Partitions of a Given Shape. Electron. J. Comb. 15(1) (2008)
Conference and Workshop Papers
- 2024
- [c132]Ilias Diakonikolas, Daniel M. Kane, Sihan Liu, Nikos Zarifis:
Testable Learning of General Halfspaces with Adversarial Label Noise. COLT 2024: 1308-1335 - [c131]Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas, Nikos Zarifis:
Statistical Query Lower Bounds for Learning Truncated Gaussians. COLT 2024: 1336-1363 - [c130]Ilias Diakonikolas, Daniel M. Kane:
Efficiently Learning One-Hidden-Layer ReLU Networks via SchurPolynomials. COLT 2024: 1364-1378 - [c129]Yuqian Cheng, Daniel M. Kane, Zhicheng Zheng:
New Lower Bounds for Testing Monotonicity and Log Concavity of Distributions. COLT 2024: 2768-2794 - [c128]Daniel M. Kane, Ilias Diakonikolas, Hanshen Xiao, Sihan Liu:
Online Robust Mean Estimation. SODA 2024: 3197-3235 - [c127]Ilias Diakonikolas
, Daniel M. Kane
, Vasilis Kontonis
, Sihan Liu
, Nikos Zarifis
:
Super Non-singular Decompositions of Polynomials and Their Application to Robustly Learning Low-Degree PTFs. STOC 2024: 152-159 - [c126]Ilias Diakonikolas
, Daniel M. Kane
, Sihan Liu
:
Testing Closeness of Multivariate Distributions via Ramsey Theory. STOC 2024: 340-347 - [c125]Daniel M. Kane
, Anthony Ostuni
, Kewen Wu
:
Locality Bounds for Sampling Hamming Slices. STOC 2024: 1279-1286 - 2023
- [c124]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: 1588-1617 - [c123]Ilias Diakonikolas, Jelena Diakonikolas, Daniel M. Kane, Puqian Wang, Nikos Zarifis:
Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise. COLT 2023: 2211-2239 - [c122]Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas, Nikos Zarifis:
SQ Lower Bounds for Learning Mixtures of Separated and Bounded Covariance Gaussians. COLT 2023: 2319-2349 - [c121]Daniel Kane, Ilias Diakonikolas:
A Nearly Tight Bound for Fitting an Ellipsoid to Gaussian Random Points. COLT 2023: 3014-3028 - [c120]Ilias Diakonikolas, Daniel M. Kane, Yuetian Luo, Anru Zhang:
Statistical and Computational Limits for Tensor-on-Tensor Association Detection. COLT 2023: 5260-5310 - [c119]Ilias Diakonikolas, Daniel Kane, Ankit Pensia, Thanasis Pittas:
Nearly-Linear Time and Streaming Algorithms for Outlier-Robust PCA. ICML 2023: 7886-7921 - [c118]Ilias Diakonikolas, Daniel Kane, Lisheng Ren:
Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginals. ICML 2023: 7922-7938 - [c117]Ilias Diakonikolas, Jelena Diakonikolas, Daniel Kane, Puqian Wang, Nikos Zarifis:
Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise. NeurIPS 2023 - [c116]Ilias Diakonikolas, Daniel Kane, Vasilis Kontonis, Sihan Liu, Nikos Zarifis:
Efficient Testable Learning of Halfspaces with Adversarial Label Noise. NeurIPS 2023 - [c115]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 - [c114]Ilias Diakonikolas, Daniel Kane, Ankit Pensia, Thanasis Pittas:
Near-Optimal Algorithms for Gaussians with Huber Contamination: Mean Estimation and Linear Regression. NeurIPS 2023 - [c113]Ilias Diakonikolas, Daniel Kane, Lisheng Ren, Yuxin Sun:
SQ Lower Bounds for Non-Gaussian Component Analysis with Weaker Assumptions. NeurIPS 2023 - [c112]Ilias Diakonikolas, Daniel Kane, Yuxin Sun:
SQ Lower Bounds for Learning Mixtures of Linear Classifiers. NeurIPS 2023 - [c111]Daniel Beaglehole, Max Hopkins, Daniel Kane, Sihan Liu, Shachar Lovett:
Sampling Equilibria: Fast No-Regret Learning in Structured Games. SODA 2023: 3817-3855 - [c110]Ilias Diakonikolas, Daniel M. Kane, Ankit Pensia:
Gaussian Mean Testing Made Simple. SOSA 2023: 348-352 - [c109]Ilias Diakonikolas, Christos Tzamos, Daniel M. Kane:
A Strongly Polynomial Algorithm for Approximate Forster Transforms and Its Application to Halfspace Learning. STOC 2023: 1741-1754 - 2022
- [c108]Ilias Diakonikolas, Daniel Kane, Pasin Manurangsi, Lisheng Ren:
Hardness of Learning a Single Neuron with Adversarial Label Noise. AISTATS 2022: 8199-8213 - [c107]Alaa Maalouf, Murad Tukan, Eric Price, Daniel M. Kane, Dan Feldman:
Coresets for Data Discretization and Sine Wave Fitting. AISTATS 2022: 10622-10639 - [c106]Daniel Kane, Sihan Liu, Shachar Lovett, Gaurav Mahajan:
Computational-Statistical Gap in Reinforcement Learning. COLT 2022: 1282-1302 - [c105]Max Hopkins, Daniel M. Kane, Shachar Lovett, Gaurav Mahajan:
Realizable Learning is All You Need. COLT 2022: 3015-3069 - [c104]Ilias Diakonikolas, Daniel M. Kane, Yuxin Sun:
Optimal SQ Lower Bounds for Robustly Learning Discrete Product Distributions and Ising Models. COLT 2022: 3936-3978 - [c103]Ilias Diakonikolas, Daniel Kane:
Near-Optimal Statistical Query Hardness of Learning Halfspaces with Massart Noise. COLT 2022: 4258-4282 - [c102]Ilias Diakonikolas, Daniel Kane:
Non-Gaussian Component Analysis via Lattice Basis Reduction. COLT 2022: 4535-4547 - [c101]Ilias Diakonikolas, Daniel M. Kane, Sushrut Karmalkar, Ankit Pensia, Thanasis Pittas:
Robust Sparse Mean Estimation via Sum of Squares. COLT 2022: 4703-4763 - [c100]Ilias Diakonikolas, Daniel M. Kane, Ankit Pensia, Thanasis Pittas:
Streaming Algorithms for High-Dimensional Robust Statistics. ICML 2022: 5061-5117 - [c99]Yu Cheng, Ilias Diakonikolas, Rong Ge, Shivam Gupta, Daniel Kane, Mahdi Soltanolkotabi:
Outlier-Robust Sparse Estimation via Non-Convex Optimization. NeurIPS 2022 - [c98]Clément L. Canonne, Ilias Diakonikolas, Daniel Kane, Sihan Liu:
Nearly-Tight Bounds for Testing Histogram Distributions. NeurIPS 2022 - [c97]Ilias Diakonikolas, Daniel Kane, Sushrut Karmalkar, Ankit Pensia, Thanasis Pittas:
List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filtering. NeurIPS 2022 - [c96]Ilias Diakonikolas, Daniel Kane, Jasper C. H. Lee, Ankit Pensia:
Outlier-Robust Sparse Mean Estimation for Heavy-Tailed Distributions. NeurIPS 2022 - [c95]Ilias Diakonikolas, Daniel Kane, Pasin Manurangsi, Lisheng Ren:
Cryptographic Hardness of Learning Halfspaces with Massart Noise. NeurIPS 2022 - [c94]Ilias Diakonikolas, Daniel Kane, Lisheng Ren, Yuxin Sun:
SQ Lower Bounds for Learning Single Neurons with Massart Noise. NeurIPS 2022 - [c93]Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis:
Learning general halfspaces with general Massart noise under the Gaussian distribution. STOC 2022: 874-885 - [c92]Ainesh Bakshi, Ilias Diakonikolas, He Jia, Daniel M. Kane, Pravesh K. Kothari, Santosh S. Vempala:
Robustly learning mixtures of k arbitrary Gaussians. STOC 2022: 1234-1247 - [c91]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: 1262-1275 - 2021
- [c90]Venkata Gandikota, Daniel Kane, Raj Kumar Maity, Arya Mazumdar:
vqSGD: Vector Quantized Stochastic Gradient Descent. AISTATS 2021: 2197-2205 - [c89]Ilias Diakonikolas, Daniel M. Kane:
The Sample Complexity of Robust Covariance Testing. COLT 2021: 1511-1521 - [c88]Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis:
Agnostic Proper Learning of Halfspaces under Gaussian Marginals. COLT 2021: 1522-1551 - [c87]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: 1552-1584 - [c86]Ilias Diakonikolas, Russell Impagliazzo, Daniel M. Kane, Rex Lei, Jessica Sorrell, Christos Tzamos:
Boosting in the Presence of Massart Noise. COLT 2021: 1585-1644 - [c85]Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart, Yuxin Sun:
Outlier-Robust Learning of Ising Models Under Dobrushin's Condition. COLT 2021: 1645-1682 - [c84]Max Hopkins, Daniel Kane, Shachar Lovett, Michal Moshkovitz:
Bounded Memory Active Learning through Enriched Queries. COLT 2021: 2358-2387 - [c83]Yuval Dagan, Yuval Filmus, Daniel Kane, Shay Moran:
The Entropy of Lies: Playing Twenty Questions with a Liar. ITCS 2021: 1:1-1:16 - [c82]Ilias Diakonikolas, Daniel Kane, Ankit Pensia, Thanasis Pittas, Alistair Stewart:
Statistical Query Lower Bounds for List-Decodable Linear Regression. NeurIPS 2021: 3191-3204 - [c81]Ilias Diakonikolas, Daniel Kane, Christos Tzamos:
Forster Decomposition and Learning Halfspaces with Noise. NeurIPS 2021: 7732-7744 - [c80]Ilias Diakonikolas, Daniel Kane, Daniel Kongsgaard, Jerry Li, Kevin Tian:
List-Decodable Mean Estimation in Nearly-PCA Time. NeurIPS 2021: 10195-10208 - [c79]Daniel M. Kane:
Robust Learning of Mixtures of Gaussians. SODA 2021: 1246-1258 - [c78]Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis:
Efficiently learning halfspaces with Tsybakov noise. STOC 2021: 88-101 - [c77]Ilias Diakonikolas, Themis Gouleakis, Daniel M. Kane, John Peebles, Eric Price:
Optimal testing of discrete distributions with high probability. STOC 2021: 542-555 - 2020
- [c76]Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Nikos Zarifis:
Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks. COLT 2020: 1514-1539 - [c75]Max Hopkins, Daniel Kane, Shachar Lovett, Gaurav Mahajan:
Noise-tolerant, Reliable Active Classification with Comparison Queries. COLT 2020: 1957-2006 - [c74]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: 149-159 - [c73]Ilias Diakonikolas, Daniel M. Kane:
Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models. FOCS 2020: 184-195 - [c72]Max Hopkins, Daniel Kane, Shachar Lovett, Gaurav Mahajan:
Point Location and Active Learning: Learning Halfspaces Almost Optimally. FOCS 2020: 1034-1044 - [c71]Ilias Diakonikolas, Daniel Kane, Daniel Kongsgaard:
List-Decodable Mean Estimation via Iterative Multi-Filtering. NeurIPS 2020 - [c70]Ilias Diakonikolas, Daniel M. Kane, Pasin Manurangsi:
The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise. NeurIPS 2020 - [c69]Ilias Diakonikolas, Daniel M. Kane, Ankit Pensia:
Outlier Robust Mean Estimation with Subgaussian Rates via Stability. NeurIPS 2020 - [c68]Ilias Diakonikolas, Daniel Kane, Nikos Zarifis:
Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals. NeurIPS 2020 - [c67]Max Hopkins, Daniel Kane, Shachar Lovett:
The Power of Comparisons for Actively Learning Linear Classifiers. NeurIPS 2020 - 2019
- [c66]Olivier Bousquet, Daniel Kane, Shay Moran:
The Optimal Approximation Factor in Density Estimation. COLT 2019: 318-341 - [c65]Ilias Diakonikolas, Themis Gouleakis, Daniel M. Kane, Sankeerth Rao:
Communication and Memory Efficient Testing of Discrete Distributions. COLT 2019: 1070-1106 - [c64]Ilias Diakonikolas, Daniel M. Kane, John Peebles:
Testing Identity of Multidimensional Histograms. COLT 2019: 1107-1131 - [c63]Surbhi Goel, Daniel M. Kane, Adam R. Klivans:
Learning Ising Models with Independent Failures. COLT 2019: 1449-1469 - [c62]Daniel Kane, Roi Livni, Shay Moran, Amir Yehudayoff:
On Communication Complexity of Classification Problems. COLT 2019: 1903-1943 - [c61]Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Jacob Steinhardt, Alistair Stewart:
Sever: A Robust Meta-Algorithm for Stochastic Optimization. ICML 2019: 1596-1606 - [c60]Daniel M. Kane, Richard Ryan Williams
:
The Orthogonal Vectors Conjecture for Branching Programs and Formulas. ITCS 2019: 48:1-48:15 - [c59]Ilias Diakonikolas, Daniel Kane, Pasin Manurangsi:
Nearly Tight Bounds for Robust Proper Learning of Halfspaces with a Margin. NeurIPS 2019: 10473-10484 - [c58]Ilias Diakonikolas, Daniel Kane, Sushrut Karmalkar, Eric Price, Alistair Stewart:
Outlier-Robust High-Dimensional Sparse Estimation via Iterative Filtering. NeurIPS 2019: 10688-10699 - [c57]Maryam Aliakbarpour, Ilias Diakonikolas, Daniel Kane, Ronitt Rubinfeld:
Private Testing of Distributions via Sample Permutations. NeurIPS 2019: 10877-10888 - [c56]Ilias Diakonikolas, Daniel M. Kane:
Degree-푑 chow parameters robustly determine degree-푑 PTFs (and algorithmic applications). STOC 2019: 804-815 - 2018
- [c55]Daniel Kane, Sankeerth Rao
:
A PRG for Boolean PTF of Degree 2 with Seed Length Subpolynomial in epsilon and Logarithmic in n. CCC 2018: 2:1-2:24 - [c54]Daniel M. Kane, Shachar Lovett
, Shay Moran:
Generalized Comparison Trees for Point-Location Problems. ICALP 2018: 82:1-82:13 - [c53]Clément L. Canonne, Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart:
Testing Conditional Independence of Discrete Distributions. ITA 2018: 1-57 - [c52]Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart:
Sharp Bounds for Generalized Uniformity Testing. NeurIPS 2018: 6204-6213 - [c51]Yu Cheng, Ilias Diakonikolas, Daniel Kane, Alistair Stewart:
Robust Learning of Fixed-Structure Bayesian Networks. NeurIPS 2018: 10304-10316 - [c50]Ilias Diakonikolas, Gautam Kamath
, Daniel M. Kane, Jerry Li, Ankur Moitra, Alistair Stewart:
Robustly Learning a Gaussian: Getting Optimal Error, Efficiently. SODA 2018: 2683-2702 - [c49]Daniel M. Kane, Shachar Lovett
, Shay Moran:
Near-optimal linear decision trees for k-SUM and related problems. STOC 2018: 554-563 - [c48]Clément L. Canonne, Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart:
Testing conditional independence of discrete distributions. STOC 2018: 735-748 - [c47]Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart:
List-decodable robust mean estimation and learning mixtures of spherical gaussians. STOC 2018: 1047-1060 - [c46]Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart:
Learning geometric concepts with nasty noise. STOC 2018: 1061-1073 - 2017
- [c45]Clément L. Canonne
, Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart:
Testing Bayesian Networks. COLT 2017: 370-448 - [c44]Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart:
Learning Multivariate Log-concave Distributions. COLT 2017: 711-727 - [c43]Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart:
Statistical Query Lower Bounds for Robust Estimation of High-Dimensional Gaussians and Gaussian Mixtures. FOCS 2017: 73-84 - [c42]Daniel Kane, Shachar Lovett
, Sankeerth Rao
:
The Independence Number of the Birkhoff Polytope Graph, and Applications to Maximally Recoverable Codes. FOCS 2017: 252-259 - [c41]Daniel M. Kane, Shachar Lovett
, Shay Moran, Jiapeng Zhang:
Active Classification with Comparison Queries. FOCS 2017: 355-366 - [c40]Daniel Kane, Sushrut Karmalkar, Eric Price:
Robust Polynomial Regression up to the Information Theoretic Limit. FOCS 2017: 391-402 - [c39]Ilias Diakonikolas, Daniel M. Kane, Vladimir Nikishkin:
Near-Optimal Closeness Testing of Discrete Histogram Distributions. ICALP 2017: 8:1-8:15 - [c38]Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, Alistair Stewart:
Being Robust (in High Dimensions) Can Be Practical. ICML 2017: 999-1008 - [c37]Valentine Kabanets, Daniel M. Kane, Zhenjian Lu:
A polynomial restriction lemma with applications. STOC 2017: 615-628 - 2016
- [c36]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: 1-5 - [c35]Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart:
Optimal Learning via the Fourier Transform for Sums of Independent Integer Random Variables. COLT 2016: 831-849 - [c34]Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart:
Properly Learning Poisson Binomial Distributions in Almost Polynomial Time. COLT 2016: 850-878 - [c33]Mihir Bellare, Daniel Kane, Phillip Rogaway:
Big-Key Symmetric Encryption: Resisting Key Exfiltration. CRYPTO (1) 2016: 373-402 - [c32]Ilias Diakonikolas, Gautam Kamath
, Daniel M. Kane, Jerry Li, Ankur Moitra, Alistair Stewart:
Robust Estimators in High Dimensions without the Computational Intractability. FOCS 2016: 655-664 - [c31]Ilias Diakonikolas, Daniel M. Kane:
A New Approach for Testing Properties of Discrete Distributions. FOCS 2016: 685-694 - [c30]Xue Chen, Daniel M. Kane, Eric Price, Zhao Song:
Fourier-Sparse Interpolation without a Frequency Gap. FOCS 2016: 741-750 - [c29]Daniel M. Kane, Ryan Williams
:
Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits. STOC 2016: 633-643 - [c28]Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart:
The fourier transform of poisson multinomial distributions and its algorithmic applications. STOC 2016: 1060-1073 - 2015
- [c27]Mihir Bellare, Joseph Jaeger
, Daniel Kane:
Mass-surveillance without the State: Strongly Undetectable Algorithm-Substitution Attacks. CCS 2015: 1431-1440 - [c26]Daniel M. Kane:
A Polylogarithmic PRG for Degree 2 Threshold Functions in the Gaussian Setting. CCC 2015: 567-581 - [c25]Parikshit Gopalan, Daniel M. Kane, Raghu Meka:
Pseudorandomness via the Discrete Fourier Transform. FOCS 2015: 903-922 - [c24]Ilias Diakonikolas, Daniel M. Kane, Vladimir Nikishkin
:
Optimal Algorithms and Lower Bounds for Testing Closeness of Structured Distributions. FOCS 2015: 1183-1202 - [c23]Ilias Diakonikolas, Daniel M. Kane, Vladimir Nikishkin
:
Testing Identity of Structured Distributions. SODA 2015: 1841-1854 - 2014
- [c22]Daniel M. Kane:
A Pseudorandom Generator for Polynomial Threshold Functions of Gaussian with Subpolynomial Seed Length. CCC 2014: 217-228 - [c21]Daniel M. Kane, Osamu Watanabe
:
A Short Implicant of a CNF Formula with Many Satisfying Assignments. ISAAC 2014: 273-284 - [c20]Daniel M. Kane:
The average sensitivity of an intersection of half spaces. STOC 2014: 437-440 - 2013
- [c19]Daniel M. Kane:
The Correct Exponent for the Gotsman-Linial Conjecture. CCC 2013: 56-64 - [c18]Daniel M. Kane, Adam R. Klivans, Raghu Meka:
Learning Halfspaces Under Log-Concave Densities: Polynomial Approximations and Moment Matching. COLT 2013: 522-545 - [c17]Daniel M. Kane, Raghu Meka:
A PRG for lipschitz functions of polynomials with applications to sparsest cut. STOC 2013: 1-10 - 2012
- [c16]Eric Blais, Daniel M. Kane:
Tight Bounds for Testing k-Linearity. APPROX-RANDOM 2012: 435-446 - [c15]Daniel M. Kane:
A Structure Theorem for Poorly Anticoncentrated Gaussian Chaoses and Applications to the Study of Polynomial Threshold Functions. FOCS 2012: 91-100 - [c14]Daniel M. Kane, Kurt Mehlhorn, Thomas Sauerwald, He Sun:
Counting Arbitrary Subgraphs in Data Streams. ICALP (2) 2012: 598-609 - [c13]Daniel M. Kane, Jelani Nelson:
Sparser Johnson-Lindenstrauss transforms. SODA 2012: 1195-1206 - 2011
- [c12]Daniel Kane, Raghu Meka, Jelani Nelson:
Almost Optimal Explicit Johnson-Lindenstrauss Families. APPROX-RANDOM 2011: 628-639 - [c11]Daniel M. Kane:
k-Independent Gaussians Fool Polynomial Threshold Functions. CCC 2011: 252-261 - [c10]Daniel M. Kane:
A Small PRG for Polynomial Threshold Functions of Gaussians. FOCS 2011: 257-266 - [c9]Daniel M. Kane, Jelani Nelson, Ely Porat, David P. Woodruff:
Fast moment estimation in data streams in optimal space. STOC 2011: 745-754 - 2010
- [c8]Daniel M. Kane:
The Gaussian Surface Area and Noise Sensitivity of Degree-d Polynomial Threshold Functions. CCC 2010: 205-210 - [c7]Ilias Diakonikolas, Daniel M. Kane, Jelani Nelson:
Bounded Independence Fools Degree-2 Threshold Functions. FOCS 2010: 11-20 - [c6]Daniel M. Kane, Jelani Nelson, David P. Woodruff:
An optimal algorithm for the distinct elements problem. PODS 2010: 41-52 - [c5]Daniel M. Kane, Jelani Nelson, David P. Woodruff:
On the Exact Space Complexity of Sketching and Streaming Small Norms. SODA 2010: 1161-1178 - 2009
- [c4]Erik D. Demaine, Dion Harmon, John Iacono, Daniel Kane, Mihai Patrascu:
The geometry of binary search trees. SODA 2009: 496-505 - [c3]Daniel Kane, Gregory N. Price, Erik D. Demaine:
A Pseudopolynomial Algorithm for Alexandrov's Theorem. WADS 2009: 435-446 - 2005
- [c2]Timothy G. Abbott, Erik D. Demaine, Martin L. Demaine, Daniel Kane, Stefan Langerman, Jelani Nelson, Vincent Yeung:
Dynamic Ham-Sandwich Cuts of Convex Polygons in the Plane. CCCG 2005: 61-64 - [c1]Timothy G. Abbott, Daniel Kane, Paul Valiant:
On the Complexity of Two-PlayerWin-Lose Games. FOCS 2005: 113-122
Parts in Books or Collections
- 2020
- [p1]Ilias Diakonikolas, Daniel M. Kane:
Robust High-Dimensional Statistics. Beyond the Worst-Case Analysis of Algorithms 2020: 382-402
Informal and Other Publications
- 2024
- [i151]Daniel M. Kane, Anthony Ostuni, Kewen Wu:
Locality Bounds for Sampling Hamming Slices. CoRR abs/2402.14278 (2024) - [i150]Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas, Nikos Zarifis:
Statistical Query Lower Bounds for Learning Truncated Gaussians. CoRR abs/2403.02300 (2024) - [i149]Ilias Diakonikolas, Daniel Kane, Lisheng Ren, Yuxin Sun:
SQ Lower Bounds for Non-Gaussian Component Analysis with Weaker Assumptions. CoRR abs/2403.04744 (2024) - [i148]Ilias Diakonikolas, Daniel M. Kane, Sushrut Karmalkar, Ankit Pensia, Thanasis Pittas:
Robust Sparse Estimation for Gaussians with Optimal Error under Huber Contamination. CoRR abs/2403.10416 (2024) - [i147]Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Sihan Liu, Nikos Zarifis:
Super Non-singular Decompositions of Polynomials and their Application to Robustly Learning Low-degree PTFs. CoRR abs/2404.00529 (2024) - [i146]Max Hopkins, Russell Impagliazzo, Daniel Kane, Sihan Liu, Christopher Ye:
Replicability in High Dimensional Statistics. CoRR abs/2406.02628 (2024) - [i145]Daniel M. Kane, Anthony Ostuni, Kewen Wu:
Locality Bounds for Sampling Hamming Slices. Electron. Colloquium Comput. Complex. TR24 (2024) - 2023
- [i144]Max Hopkins, Daniel M. Kane, Shachar Lovett, Gaurav Mahajan:
Do PAC-Learners Learn the Marginal Distribution? CoRR abs/2302.06285 (2023) - [i143]Ilias Diakonikolas, Daniel M. Kane, Lisheng Ren:
Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginals. CoRR abs/2302.06512 (2023) - [i142]Daniel Kane, Sihan Liu, Shachar Lovett, Gaurav Mahajan, Csaba Szepesvári, Gellért Weisz:
Exponential Hardness of Reinforcement Learning with Linear Function Approximation. CoRR abs/2302.12940 (2023) - [i141]Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Sihan Liu, Nikos Zarifis:
Efficient Testable Learning of Halfspaces with Adversarial Label Noise. CoRR abs/2303.05485 (2023) - [i140]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 abs/2305.00966 (2023) - [i139]Ilias Diakonikolas, Daniel M. Kane, Ankit Pensia, Thanasis Pittas:
Nearly-Linear Time and Streaming Algorithms for Outlier-Robust PCA. CoRR abs/2305.02544 (2023) - [i138]Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas, Nikos Zarifis:
SQ Lower Bounds for Learning Bounded Covariance GMMs. CoRR abs/2306.13057 (2023) - [i137]Ilias Diakonikolas, Jelena Diakonikolas, Daniel M. Kane, Puqian Wang, Nikos Zarifis:
Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise. CoRR abs/2306.16352 (2023) - [i136]Ilias Diakonikolas, Jelena Diakonikolas, Daniel M. Kane, Puqian Wang, Nikos Zarifis:
Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise. CoRR abs/2307.08438 (2023) - [i135]Ilias Diakonikolas, Daniel M. Kane:
Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials. CoRR abs/2307.12840 (2023) - [i134]Yuqian Cheng, Daniel M. Kane, Zhicheng Zheng:
New Lower Bounds for Testing Monotonicity and Log Concavity of Distributions. CoRR abs/2308.00089 (2023) - [i133]Ilias Diakonikolas, Daniel M. Kane, Yuxin Sun:
SQ Lower Bounds for Learning Mixtures of Linear Classifiers. CoRR abs/2310.11876 (2023) - [i132]Daniel M. Kane, Ilias Diakonikolas, Hanshen Xiao, Sihan Liu:
Online Robust Mean Estimation. CoRR abs/2310.15932 (2023) - [i131]Ilias Diakonikolas, Daniel M. Kane, Sihan Liu:
Testing Closeness of Multivariate Distributions via Ramsey Theory. CoRR abs/2311.13154 (2023) - [i130]Ilias Diakonikolas, Daniel M. Kane, Ankit Pensia, Thanasis Pittas:
Near-Optimal Algorithms for Gaussians with Huber Contamination: Mean Estimation and Linear Regression. CoRR abs/2312.01547 (2023) - [i129]Ilias Diakonikolas, Daniel M. Kane, Jasper C. H. Lee, Thanasis Pittas:
Clustering Mixtures of Bounded Covariance Distributions Under Optimal Separation. CoRR abs/2312.11769 (2023) - [i128]Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis:
Agnostically Learning Multi-index Models with Queries. CoRR abs/2312.16616 (2023) - 2022
- [i127]Daniel Kane, Sihan Liu, Shachar Lovett, Gaurav Mahajan:
Computational-Statistical Gaps in Reinforcement Learning. CoRR abs/2202.05444 (2022) - [i126]Alaa Maalouf, Murad Tukan, Eric Price, Daniel Kane, Dan Feldman:
Coresets for Data Discretization and Sine Wave Fitting. CoRR abs/2203.03009 (2022) - [i125]Ilias Diakonikolas, Daniel M. Kane, Ankit Pensia, Thanasis Pittas:
Streaming Algorithms for High-Dimensional Robust Statistics. CoRR abs/2204.12399 (2022) - [i124]Ilias Diakonikolas, Daniel M. Kane, Sushrut Karmalkar, Ankit Pensia, Thanasis Pittas:
Robust Sparse Mean Estimation via Sum of Squares. CoRR abs/2206.03441 (2022) - [i123]Ilias Diakonikolas, Daniel M. Kane, Yuxin Sun:
Optimal SQ Lower Bounds for Robustly Learning Discrete Product Distributions and Ising Models. CoRR abs/2206.04589 (2022) - [i122]Ilias Diakonikolas, Daniel M. Kane, Sushrut Karmalkar, Ankit Pensia, Thanasis Pittas:
List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filtering. CoRR abs/2206.05245 (2022) - [i121]Clément L. Canonne, Ilias Diakonikolas, Daniel M. Kane, Sihan Liu:
Near-Optimal Bounds for Testing Histogram Distributions. CoRR abs/2207.06596 (2022) - [i120]Ilias Diakonikolas, Daniel M. Kane, Pasin Manurangsi, Lisheng Ren:
Cryptographic Hardness of Learning Halfspaces with Massart Noise. CoRR abs/2207.14266 (2022) - [i119]Ilias Diakonikolas, Daniel M. Kane, Lisheng Ren, Yuxin Sun:
SQ Lower Bounds for Learning Single Neurons with Massart Noise. CoRR abs/2210.09949 (2022) - [i118]Ilias Diakonikolas, Daniel M. Kane, Ankit Pensia:
Gaussian Mean Testing Made Simple. CoRR abs/2210.13706 (2022) - [i117]Ilias Diakonikolas, Daniel M. Kane, Jasper C. H. Lee, Ankit Pensia:
Outlier-Robust Sparse Mean Estimation for Heavy-Tailed Distributions. CoRR abs/2211.16333 (2022) - [i116]Ilias Diakonikolas, Christos Tzamos, Daniel M. Kane:
A Strongly Polynomial Algorithm for Approximate Forster Transforms and its Application to Halfspace Learning. CoRR abs/2212.03008 (2022) - [i115]Daniel M. Kane, Ilias Diakonikolas:
A Nearly Tight Bound for Fitting an Ellipsoid to Gaussian Random Points. CoRR abs/2212.11221 (2022) - [i114]Ilias Diakonikolas, Christos Tzamos, Daniel Kane:
A Strongly Polynomial Algorithm for Approximate Forster Transforms and its Application to Halfspace Learning. Electron. Colloquium Comput. Complex. TR22 (2022) - 2021
- [i113]Daniel Kane, Andreas Fackler, Adam Gagol, Damian Straszak:
Highway: Efficient Consensus with Flexible Finality. CoRR abs/2101.02159 (2021) - [i112]Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart, Yuxin Sun:
Outlier-Robust Learning of Ising Models Under Dobrushin's Condition. CoRR abs/2102.02171 (2021) - [i111]Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas, Nikos Zarifis:
The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals. CoRR abs/2102.04401 (2021) - [i110]Max Hopkins, Daniel Kane, Shachar Lovett, Michal Moshkovitz:
Bounded Memory Active Learning through Enriched Queries. CoRR abs/2102.05047 (2021) - [i109]Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis:
Agnostic Proper Learning of Halfspaces under Gaussian Marginals. CoRR abs/2102.05629 (2021) - [i108]Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan, Daniel Kane:
Fooling Gaussian PTFs via Local Hyperconcentration. CoRR abs/2103.07809 (2021) - [i107]Ilias Diakonikolas, Russell Impagliazzo, Daniel Kane, Rex Lei, Jessica Sorrell, Christos Tzamos:
Boosting in the Presence of Massart Noise. CoRR abs/2106.07779 (2021) - [i106]Ilias Diakonikolas, Daniel M. Kane, Daniel Kongsgaard, Jerry Li, Kevin Tian:
Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation. CoRR abs/2106.08537 (2021) - [i105]Ilias Diakonikolas, Daniel M. Kane, Ankit Pensia, Thanasis Pittas, Alistair Stewart:
Statistical Query Lower Bounds for List-Decodable Linear Regression. CoRR abs/2106.09689 (2021) - [i104]Ilias Diakonikolas, Daniel M. Kane, Christos Tzamos:
Forster Decomposition and Learning Halfspaces with Noise. CoRR abs/2107.05582 (2021) - [i103]Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis:
Threshold Phenomena in Learning Halfspaces with Massart Noise. CoRR abs/2108.08767 (2021) - [i102]Yu Cheng, Ilias Diakonikolas, Daniel M. Kane, Rong Ge, Shivam Gupta, Mahdi Soltanolkotabi:
Outlier-Robust Sparse Estimation via Non-Convex Optimization. CoRR abs/2109.11515 (2021) - [i101]Daniel M. Kane, Shahed Sharif, Alice Silverberg:
Quantum Money from Quaternion Algebras. CoRR abs/2109.12643 (2021) - [i100]Max Hopkins, Daniel M. Kane, Shachar Lovett, Gaurav Mahajan:
Realizable Learning is All You Need. CoRR abs/2111.04746 (2021) - [i99]Ilias Diakonikolas, Daniel M. Kane:
Non-Gaussian Component Analysis via Lattice Basis Reduction. CoRR abs/2112.09104 (2021) - [i98]Daniel M. Kane, Shahed Sharif, Alice Silverberg:
Quantum Money from Quaternion Algebras. IACR Cryptol. ePrint Arch. 2021: 1294 (2021) - 2020
- [i97]Max Hopkins, Daniel Kane, Shachar Lovett, Gaurav Mahajan:
Noise-tolerant, Reliable Active Classification with Comparison Queries. CoRR abs/2001.05497 (2020) - [i96]Max Hopkins, Daniel M. Kane, Shachar Lovett, Gaurav Mahajan:
Point Location and Active Learning: Learning Halfspaces Almost Optimally. CoRR abs/2004.11380 (2020) - [i95]Ilias Diakonikolas, Samuel B. Hopkins, Daniel Kane, Sushrut Karmalkar:
Robustly Learning any Clusterable Mixture of Gaussians. CoRR abs/2005.06417 (2020) - [i94]Ilias Diakonikolas, Daniel M. Kane, Daniel Kongsgaard:
List-Decodable Mean Estimation via Iterative Multi-Filtering. CoRR abs/2006.10715 (2020) - [i93]Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Nikos Zarifis:
Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks. CoRR abs/2006.12476 (2020) - [i92]Ilias Diakonikolas, Daniel M. Kane, Nikos Zarifis:
Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals. CoRR abs/2006.16200 (2020) - [i91]Daniel M. Kane:
Robust Learning of Mixtures of Gaussians. CoRR abs/2007.05912 (2020) - [i90]Ilias Diakonikolas, Daniel M. Kane, Pasin Manurangsi:
The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise. CoRR abs/2007.15220 (2020) - [i89]Ilias Diakonikolas, Daniel M. Kane, Ankit Pensia:
Outlier Robust Mean Estimation with Subgaussian Rates via Stability. CoRR abs/2007.15618 (2020) - [i88]Ilias Diakonikolas, Themis Gouleakis, Daniel M. Kane, John Peebles, Eric Price:
Optimal Testing of Discrete Distributions with High Probability. CoRR abs/2009.06540 (2020) - [i87]Daniel M. Kane, Scott Duke Kominers:
Prisoners, Rooms, and Lightswitches. CoRR abs/2009.08575 (2020) - [i86]Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis:
A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise. CoRR abs/2010.01705 (2020) - [i85]Ilias Diakonikolas, Daniel M. Kane, Daniel Kongsgaard, Jerry Li, Kevin Tian:
List-Decodable Mean Estimation in Nearly-PCA Time. CoRR abs/2011.09973 (2020) - [i84]Ainesh Bakshi, Ilias Diakonikolas, He Jia, Daniel M. Kane, Pravesh K. Kothari, Santosh S. Vempala:
Robustly Learning Mixtures of k Arbitrary Gaussians. CoRR abs/2012.02119 (2020) - [i83]Ilias Diakonikolas, Daniel M. Kane:
Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models. CoRR abs/2012.07774 (2020) - [i82]Ilias Diakonikolas, Daniel M. Kane:
Hardness of Learning Halfspaces with Massart Noise. CoRR abs/2012.09720 (2020) - [i81]Ilias Diakonikolas, Daniel M. Kane:
The Sample Complexity of Robust Covariance Testing. CoRR abs/2012.15802 (2020) - [i80]Ilias Diakonikolas, Themis Gouleakis, Daniel Kane, John Peebles, Eric Price:
Optimal Testing of Discrete Distributions with High Probability. Electron. Colloquium Comput. Complex. TR20 (2020) - 2019
- [i79]Surbhi Goel, Daniel M. Kane, Adam R. Klivans:
Learning Ising Models with Independent Failures. CoRR abs/1902.04728 (2019) - [i78]Olivier Bousquet, Daniel Kane, Shay Moran:
The Optimal Approximation Factor in Density Estimation. CoRR abs/1902.05876 (2019) - [i77]Ilias Diakonikolas, Themis Gouleakis, Daniel M. Kane, Sankeerth Rao:
Communication and Memory Efficient Testing of Discrete Distributions. CoRR abs/1906.04709 (2019) - [i76]Max Hopkins, Daniel M. Kane, Shachar Lovett:
The Power of Comparisons for Actively Learning Linear Classifiers. CoRR abs/1907.03816 (2019) - [i75]Ilias Diakonikolas, Daniel M. Kane, Pasin Manurangsi:
Nearly Tight Bounds for Robust Proper Learning of Halfspaces with a Margin. CoRR abs/1908.11335 (2019) - [i74]Ilias Diakonikolas, Daniel M. Kane:
Recent Advances in Algorithmic High-Dimensional Robust Statistics. CoRR abs/1911.05911 (2019) - [i73]Ilias Diakonikolas, Sushrut Karmalkar, Daniel Kane, Eric Price, Alistair Stewart:
Outlier-Robust High-Dimensional Sparse Estimation via Iterative Filtering. CoRR abs/1911.08085 (2019) - 2018
- [i72]Daniel M. Kane, Carlo Sanna, Jeffrey O. Shallit:
Waring's Theorem for Binary Powers. CoRR abs/1801.04483 (2018) - [i71]Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Jacob Steinhardt, Alistair Stewart:
Sever: A Robust Meta-Algorithm for Stochastic Optimization. CoRR abs/1803.02815 (2018) - [i70]Ilias Diakonikolas, Daniel M. Kane, John Peebles:
Testing Identity of Multidimensional Histograms. CoRR abs/1804.03636 (2018) - [i69]Daniel M. Kane, Shachar Lovett, Shay Moran:
Generalized comparison trees for point-location problems. CoRR abs/1804.08237 (2018) - [i68]Daniel M. Kane:
Quantum Money from Modular Forms. CoRR abs/1809.05925 (2018) - [i67]Yuval Dagan, Yuval Filmus, Daniel Kane, Shay Moran:
The entropy of lies: playing twenty questions with a liar. CoRR abs/1811.02177 (2018) - [i66]Ilias Diakonikolas, Daniel M. Kane:
Degree-d Chow Parameters Robustly Determine Degree-d PTFs (and Algorithmic Applications). CoRR abs/1811.03491 (2018) - [i65]Ilias Diakonikolas, Daniel Kane:
Degree-$d$ Chow Parameters Robustly Determine Degree-$d$ PTFs (and Algorithmic Applications). Electron. Colloquium Comput. Complex. TR18 (2018) - [i64]Daniel M. Kane, Shachar Lovett, Shay Moran:
Generalized comparison trees for point-location problems. Electron. Colloquium Comput. Complex. TR18 (2018) - 2017
- [i63]Daniel M. Kane, Shachar Lovett, Sankeerth Rao:
Labeling the complete bipartite graph with no zero cycles. CoRR abs/1702.05773 (2017) - [i62]Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, Alistair Stewart:
Being Robust (in High Dimensions) Can Be Practical. CoRR abs/1703.00893 (2017) - [i61]Ilias Diakonikolas, Daniel M. Kane, Vladimir Nikishkin:
Near-Optimal Closeness Testing of Discrete Histogram Distributions. CoRR abs/1703.01913 (2017) - [i60]Daniel M. Kane, Shachar Lovett, Shay Moran, Jiapeng Zhang:
Active classification with comparison queries. CoRR abs/1704.03564 (2017) - [i59]Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, Alistair Stewart:
Robustly Learning a Gaussian: Getting Optimal Error, Efficiently. CoRR abs/1704.03866 (2017) - [i58]Daniel M. Kane, Shachar Lovett, Shay Moran:
Near-optimal linear decision trees for k-SUM and related problems. CoRR abs/1705.01720 (2017) - [i57]Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart:
Learning Geometric Concepts with Nasty Noise. CoRR abs/1707.01242 (2017) - [i56]Daniel M. Kane, Sushrut Karmalkar, Eric Price:
Robust polynomial regression up to the information theoretic limit. CoRR abs/1708.03257 (2017) - [i55]Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart:
Sharp Bounds for Generalized Uniformity Testing. CoRR abs/1709.02087 (2017) - [i54]Daniel M. Kane, R. Ryan Williams:
The Orthogonal Vectors Conjecture for Branching Programs and Formulas. CoRR abs/1709.05294 (2017) - [i53]Daniel M. Kane, Roi Livni, Shay Moran, Amir Yehudayoff:
On Communication Complexity of Classification Problems. CoRR abs/1711.05893 (2017) - [i52]Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart:
List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussians. CoRR abs/1711.07211 (2017) - [i51]Clément L. Canonne, Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart:
Testing Conditional Independence of Discrete Distributions. CoRR abs/1711.11560 (2017) - [i50]Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart:
Sharp Bounds for Generalized Uniformity Testing. Electron. Colloquium Comput. Complex. TR17 (2017) - [i49]Valentine Kabanets, Daniel M. Kane, Zhenjian Lu:
A Polynomial Restriction Lemma with Applications. Electron. Colloquium Comput. Complex. TR17 (2017) - [i48]Daniel M. Kane, Shachar Lovett, Shay Moran:
Near-optimal linear decision trees for k-SUM and related problems. Electron. Colloquium Comput. Complex. TR17 (2017) - [i47]Daniel M. Kane, Roi Livni, Shay Moran, Amir Yehudayoff:
On Communication Complexity of Classification Problems. Electron. Colloquium Comput. Complex. TR17 (2017) - [i46]Daniel M. Kane, Shachar Lovett, Shay Moran, Jiapeng Zhang:
Active classification with comparison queries. Electron. Colloquium Comput. Complex. TR17 (2017) - [i45]Daniel M. Kane, Shachar Lovett, Sankeerth Rao:
Labeling the complete bipartite graph with no zero cycles. Electron. Colloquium Comput. Complex. TR17 (2017) - 2016
- [i44]Ilias Diakonikolas, Daniel M. Kane:
A New Approach for Testing Properties of Discrete Distributions. CoRR abs/1601.05557 (2016) - [i43]Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Zheng Li, Ankur Moitra, Alistair Stewart:
Robust Estimators in High Dimensions without the Computational Intractability. CoRR abs/1604.06443 (2016) - [i42]Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart:
Learning Multivariate Log-concave Distributions. CoRR abs/1605.08188 (2016) - [i41]Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart:
Efficient Robust Proper Learning of Log-concave Distributions. CoRR abs/1606.03077 (2016) - [i40]Yu Cheng, Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart:
Robust Learning of Fixed-Structure Bayesian Networks. CoRR abs/1606.07384 (2016) - [i39]Xue Chen, Daniel M. Kane, Eric Price, Zhao Song:
Fourier-sparse interpolation without a frequency gap. CoRR abs/1609.01361 (2016) - [i38]Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart:
Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures. CoRR abs/1611.03473 (2016) - [i37]Clément L. Canonne, Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart:
Testing Bayesian Networks. CoRR abs/1612.03156 (2016) - [i36]Ilias Diakonikolas, Daniel M. Kane:
A New Approach for Testing Properties of Discrete Distributions. Electron. Colloquium Comput. Complex. TR16 (2016) - [i35]Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart:
Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures. Electron. Colloquium Comput. Complex. TR16 (2016) - [i34]Mihir Bellare, Daniel Kane, Phillip Rogaway:
Big-Key Symmetric Encryption: Resisting Key Exfiltration. IACR Cryptol. ePrint Arch. 2016: 541 (2016) - 2015
- [i33]Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart:
Nearly Optimal Learning and Sparse Covers for Sums of Independent Integer Random Variables. CoRR abs/1505.00662 (2015) - [i32]Parikshit Gopalan, Daniel M. Kane, Raghu Meka:
Pseudorandomness via the discrete Fourier transform. CoRR abs/1506.04350 (2015) - [i31]Ilias Diakonikolas, Daniel M. Kane, Vladimir Nikishkin:
Optimal Algorithms and Lower Bounds for Testing Closeness of Structured Distributions. CoRR abs/1508.05538 (2015) - [i30]Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart:
The Fourier Transform of Poisson Multinomial Distributions and its Algorithmic Applications. CoRR abs/1511.03592 (2015) - [i29]Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart:
Properly Learning Poisson Binomial Distributions in Almost Polynomial Time. CoRR abs/1511.04066 (2015) - [i28]Daniel M. Kane, Ryan Williams:
Super-Linear Gate and Super-Quadratic Wire Lower Bounds for Depth-Two and Depth-Three Threshold Circuits. CoRR abs/1511.07860 (2015) - [i27]Daniel M. Kane, Ryan Williams:
Super-Linear Gate and Super-Quadratic Wire Lower Bounds for Depth-Two and Depth-Three Threshold Circuits. Electron. Colloquium Comput. Complex. TR15 (2015) - [i26]Mihir Bellare, Joseph Jaeger, Daniel Kane:
Mass-surveillance without the State: Strongly Undetectable Algorithm-Substitution Attacks. IACR Cryptol. ePrint Arch. 2015: 808 (2015) - 2014
- [i25]Daniel M. Kane:
A Polylogarithmic PRG for Degree $2$ Threshold Functions in the Gaussian Setting. CoRR abs/1404.1103 (2014) - [i24]Ilias Diakonikolas, Daniel M. Kane, Vladimir Nikishkin:
Testing Identity of Structured Distributions. CoRR abs/1410.2266 (2014) - [i23]Parikshit Gopalan, Daniel M. Kane, Raghu Meka:
Pseudorandomness for concentration bounds and signed majorities. CoRR abs/1411.4584 (2014) - 2013
- [i22]Daniel M. Kane:
The Average Sensitivity of an Intersection of Half Spaces. CoRR abs/1309.2987 (2013) - [i21]Daniel M. Kane, Osamu Watanabe:
A Short Implicant of CNFs with Relatively Many Satisfying Assignments. Electron. Colloquium Comput. Complex. TR13 (2013) - 2012
- [i20]Daniel M. Kane:
A Structure Theorem for Poorly Poorly Anticoncentrated Gaussian Chaoses and Applications to the Study of Polynomial Threshold Functions. CoRR abs/1204.0543 (2012) - [i19]Daniel M. Kane:
A Low-Depth Monotone Function that is not an Approximate Junta. CoRR abs/1206.6541 (2012) - [i18]Daniel M. Kane:
A Pseudorandom Generator for Polynomial Threshold Functions of Gaussian with Subpolynomial Seed Length. CoRR abs/1210.1280 (2012) - [i17]Daniel M. Kane:
The Correct Exponent for the Gotsman-Linial Conjecture. CoRR abs/1210.1283 (2012) - [i16]Daniel M. Kane, Raghu Meka:
A PRG for Lipschitz Functions of Polynomials with Applications to Sparsest Cut. CoRR abs/1211.1109 (2012) - 2011
- [i15]Daniel M. Kane:
A Small PRG for Polynomial Threshold Functions of Gaussians. CoRR abs/1104.1209 (2011) - 2010
- [i14]Daniel M. Kane, Jelani Nelson:
A Derandomized Sparse Johnson-Lindenstrauss Transform. CoRR abs/1006.3585 (2010) - [i13]Daniel M. Kane, Jelani Nelson, Ely Porat, David P. Woodruff:
Fast Moment Estimation in Data Streams in Optimal Space. CoRR abs/1007.4191 (2010) - [i12]Daniel M. Kane:
Unary Subset-Sum is in Logspace. CoRR abs/1012.1336 (2010) - [i11]Daniel M. Kane, Jelani Nelson:
A Sparser Johnson-Lindenstrauss Transform. CoRR abs/1012.1577 (2010) - [i10]Daniel M. Kane:
k-Independent Gaussians Fool Polynomial Threshold Functions. CoRR abs/1012.1614 (2010) - [i9]Daniel Kane, Raghu Meka, Jelani Nelson:
Almost Optimal Explicit Johnson-Lindenstrauss Transformations. Electron. Colloquium Comput. Complex. TR10 (2010) - [i8]Daniel M. Kane, Jelani Nelson:
A Derandomized Sparse Johnson-Lindenstrauss Transform. Electron. Colloquium Comput. Complex. TR10 (2010) - 2009
- [i7]Daniel Kane, Gregory Nathan Price, Erik D. Demaine:
A Pseudopolynomial Algorithm for Alexandrov's Theorem. Computational Geometry 2009 - [i6]Daniel M. Kane, Samuel A. Kutin:
Quantum interpolation of polynomials. CoRR abs/0909.5683 (2009) - [i5]Ilias Diakonikolas, Daniel M. Kane, Jelani Nelson:
Bounded Independence Fools Degree-2 Threshold Functions. CoRR abs/0911.3389 (2009) - [i4]Daniel M. Kane:
The Gaussian Surface Area and Noise Sensitivity of Degree-$d$ Polynomials. CoRR abs/0912.2709 (2009) - [i3]Ilias Diakonikolas, Daniel M. Kane, Jelani Nelson:
Bounded Independence Fools Degree-2 Threshold Functions. Electron. Colloquium Comput. Complex. TR09 (2009) - 2008
- [i2]Daniel M. Kane, Jelani Nelson, David P. Woodruff:
Revisiting Norm Estimation in Data Streams. CoRR abs/0811.3648 (2008) - [i1]Daniel Kane, Gregory N. Price, Erik D. Demaine:
A Pseudopolynomial Algorithm for Alexandrov's Theorem. CoRR abs/0812.5030 (2008)
Coauthor Index
aka: Jerry Zheng Li
![](https://dblp.uni-trier.de/img/cog.dark.24x24.png)
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-08-10 01:25 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint