Papers:
If you are a potential student and would like to get a better
idea of what I do, here is a curated list of Introductory Papers, which
might be more approachable than simply reading random papers off
this list.
Note: Author order for all papers is either alphabetical or
randomized.
Books:
Publications:
- Ilias Diakonikolas, Daniel M. Kane, Jasper C. H. Lee, Thanasis Pittas Clustering Mixtures of Bounded Covariance Distributions Under Optimal Separation, in preparation.
- Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis Agnostically Learning Multi-index Models with Queries, in preparation.
- Max Hopkins, Daniel M. Kane, Shachar Lovett, Gaurav Mahajan
Do
PAC-Learners Learn the Marginal Distribution?, in
preparation.
- Ilias Diakonikolas, Daniel M. Kane Efficiently
Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials, in preparation.
- Ery Arias-Castro, Clement Berenfeld, Daniel Kane Theoretical
Foundations of Ordinal Multidimensional Scaling, Including
Internal and External Unfolding, in preparation.
- Ilias Diakonikolas, Daniel M. Kane Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials, Conference on
Learning Theory (COLT) 2024.
- Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas, Nikos Zarifis Statistical Query Lower Bounds for Learning Truncated Gaussians, Conference on
Learning Theory (COLT) 2024.
- Ilias Diakonikolas, Daniel M Kane, Sihan Liu, Nikos Zarifis Testable Learning of General Halfspaces with Adversarial Label Noise, Conference on
Learning Theory (COLT) 2024.
- Yuqian Cheng, Daniel M. Kane, Zhicheng Zheng New
Lower Bounds for Testing Monotonicity and Log Concavity of
Distributions, Conference on
Learning Theory (COLT) 2024.
- Ilias Diakonikolas, Daniel M. Kane, Sushrut Karmalkar, Ankit Pensia, Thanasis Pittas Robust Sparse Estimation for Gaussians with Optimal Error under Huber Contamination, International
Conference on Machine Learning (ICML) 2024.
- 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, Symposium
on Theory of Computation (STOC) 2024.
- Ilias Diakonikolas, Daniel M. Kane, Sihan Liu Testing Closeness of Multivariate Distributions via Ramsey Theory, Symposium
on Theory of Computation (STOC) 2024.
- Daniel M. Kane, Anthony Ostuni, Kewen Wu Locality Bounds for Sampling Hamming Slices, Symposium
on Theory of Computation (STOC) 2024.
- Daniel M. Kane, Ilias Diakonikolas, Hanshen Xiao, Sihan Liu
Online
Robust Mean Estimation, Symposium on Discrete
Algorithms (SODA) 2024.
- Ilias Diakonikolas, Daniel M. Kane, Yuxin Sun SQ
Lower Bounds for Learning Mixtures of Linear Classifiers,
Advances in Neural Information Processing Systems
(NeurIPS) 2023.
- Ilias Diakonikolas, Daniel M. Kane, Lisheng Ren, Yuxin Sun SQ Lower Bounds for Non-Gaussian Component Analysis with
Weaker Assumptions, Advances in Neural Information
Processing Systems (NeurIPS) 2023.
- Ilias Diakonikolas, Daniel M. Kane, Ankit Pensia, Thanasis
Pittas Near-Optimal
Algorithms for Gaussians with Huber Contamination: Mean
Estimation and Linear Regression, Advances in Neural
Information Processing Systems (NeurIPS) 2023.
- Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Sihan
Liu, Nikos Zarifis Efficient
Testable Learning of Halfspaces with Adversarial Label Noise,
Advances in Neural Information Processing Systems
(NeurIPS) 2023.
- Ilias Diakonikolas, Jelena Diakonikolas, Daniel M. Kane,
Puqian Wang, Nikos Zarifis Near-Optimal
Bounds for Learning Gaussian Halfspaces with Random
Classification Noise, Advances in Neural Information
Processing Systems (NeurIPS) 2023.
- Ilias Diakonikolas, Daniel M. Kane, Jasper C. H. Lee, Ankit
Pensia, Thanasis Pittas A
Spectral Algorithm for List-Decodable Covariance Estimation
in Relative Frobenius Norm, Advances in Neural
Information Processing Systems (NeurIPS) 2023 (spotlight
presentation).
- Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas, Nikos
Zarifis SQ Lower
Bounds for Learning Bounded Covariance GMMs, Conference on
Learning Theory (COLT) 2023.
- Ilias Diakonikolas, Jelena Diakonikolas, Daniel M. Kane,
Puqian Wang, Nikos Zarifis Information-Computation
Tradeoffs for Learning Margin Halfspaces with Random
Classification Noise, Conference on
Learning Theory (COLT) 2023.
- Ilias Diakonikolas, Daniel M. Kane, Yuetian Luo, Anru R.
Zhang Statistical
and Computational Limits for Tensor-on-Tensor Association
Detection, Conference
on
Learning Theory (COLT) 2023.
- Daniel Kane, Sihan Liu, Shachar Lovett, Gaurav Mahajan,
Csaba Szepesvári, Gellért Weisz Exponential
Hardness of Reinforcement Learning with Linear Function
Approximation, Conference
on
Learning Theory (COLT) 2023.
- Daniel M. Kane, Ilias Diakonikolas A
Nearly Tight Bound for Fitting an Ellipsoid to Gaussian
Random Points, Conference
on
Learning Theory (COLT) 2023.
- Ilias Diakonikolas, Daniel M. Kane, Lisheng Ren Near-Optimal
Cryptographic Hardness of Agnostically Learning Halfspaces
and ReLU Regression under Gaussian Marginals, International
Conference on Machine Learning (ICML) 2023.
- Ilias Diakonikolas, Daniel M. Kane, Ankit Pensia, Thanasis
Pittas Nearly-Linear
Time and Streaming Algorithms for Outlier-Robust PCA, International
Conference on Machine Learning (ICML) 2023.
- Ilias Diakonikolas, Christos Tzamos, Daniel Kane A
Strongly Polynomial Algorithm for Approximate Forster
Transforms and its Application to Halfspace Learning, Symposium
on Theory of Computation (STOC) 2023.
- Ilias Diakonikolas, Daniel M. Kane, Ankit Pensia Gaussian
Mean Testing Made Simple, Symposium on Simplicity in
Algorithms (SOSA 2023).
- Daniel Beaglehole, Max Hopkins, Daniel Kane, Sihan Liu,
Shachar Lovett Sampling
Equilibria: Fast No-Regret Learning in Structured Games,
Symposium on Discrete
Algorithms (SODA) 2023.
- Ilias Diakonikolas, Daniel M. Kane, Lisheng Ren, Yuxin Sun SQ
Lower Bounds for Learning Single Neurons with Massart Noise,
Advances in Neural Information Processing Systems
(NeurIPS) 2022.
- Clément L. Canonne, Ilias Diakonikolas, Daniel M. Kane,
Sihan Liu Near-Optimal
Bounds for Testing Histogram Distributions, Advances
in Neural Information Processing Systems (NeurIPS) 2022.
- Ilias Diakonikolas, Daniel M. Kane, Pasin Manurangsi,
Lisheng Ren Cryptographic
Hardness of Learning Halfspaces with Massart Noise, Advances
in Neural Information Processing Systems (NeurIPS) 2022.
- Yu Cheng, Ilias Diakonikolas, Daniel M. Kane, Rong Ge,
Shivam Gupta, Mahdi Soltanolkotabi Outlier-Robust
Sparse Estimation via Non-Convex Optimization, Advances
in Neural Information Processing Systems (NeurIPS) 2022.
- Ilias Diakonikolas, Daniel M. Kane, Sushrut Karmalkar, Ankit
Pensia, Thanasis Pittas List-Decodable
Sparse Mean Estimation via Difference-of-Pairs Filtering,
Advances in Neural Information Processing Systems
(NeurIPS) 2022 (oral presentation).
- Daniel M. Kane Asymptotic
Results for the
Queen Packing Problem, submitted to Journal
of Combinatorics.
- Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan with appendix
by Daniel Kane Fooling
Gaussian PTFs via Local Hyperconcentration, Journal
of the ACM, to appear.
- Ilias Diakonikolas, Daniel M. Kane, Jasper C.H. Lee, Ankit
Pensia Outlier-Robust
Sparse Mean Estimation for Heavy-Tailed Distributions, Advances
in Neural Information Processing Systems (NeurIPS) 2022.
- Jeffery S. Cohen, Daniel M. Kane Bounds
on the
Independence Required for Cuckoo Hashing, manuscript.
- Ilias Diakonikolas, Daniel M. Kane, Sushrut Karmalkar, Ankit
Pensia, Thanasis Pittas Robust
Sparse Mean Estimation via Sum of Squares, Conference
on Learning Theory (COLT) 2022.
- Ilias Diakonikolas, Daniel M. Kane, Yuxin Sun, Optimal
SQ Lower Bounds for Robustly Learning Discrete Product
Distributions and Ising Models, Conference on
Learning Theory (COLT) 2022.
- Max Hopkins, Daniel Kane, Shachar Lovett, Gaurav Mahajan Realizable
Learning is All You Need, Conference on Learning
Theory (COLT) 2022, Journal version TheoretiCS, Vol 3 (2024).
- Daniel Kane, Sihan Liu, Shachar Lovett, Gaurav Mahajan Computational-Statistical
Gaps in Reinforcement Learning, Conference on
Learning Theory (COLT) 2022.
- Ilias Diakonikolas, Daniel M. Kane Non-Gaussian
Component Analysis via Lattice Basis Reduction, Conference
on Learning Theory (COLT) 2022.
- Ilias Diakonikolas, Daniel M. Kane Near-Optimal
Statistical Query Hardness of Learning Halfspaces with
Massart Noise, Conference on Learning Theory
(COLT) 2022.
- Ilias Diakonikolas, Daniel M. Kane, Ankit Pensia, Thanasis
Pittas Streaming
Algorithms for High-Dimensional Robust Statistics, International
Conference on Machine Learning (ICML) 2022.
- Daniel M. Kane, Shahed Sharif, Alice Silverberg Quantum
Money from Quaternion Algebras, MathCrypt 2022.
- Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis,
Christos Tzamos, Nikos Zarifis Learning
General Halfspaces with General Massart Noise under the
Gaussian Distribution, Symposium on Theory of
Computation (STOC) 2022.
- Ilias Diakonikolas, Daniel M. Kane, Daniel Kongsgaard, Jerry
Li, Kevin Tian, Clustering
Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation, Symposium on Theory of Computation (STOC)
2022.
- Ainesh Bakshi, Ilias Diakonikolas, He Jia, Daniel M. Kane,
Pravesh K. Kothari, Santosh S. Vempala, Robustly
Learning Mixtures of k Arbitrary Gaussians, Symposium
on Theory of Computation (STOC) 2022.
- Ilias Diakonikolas, Daniel Kane, Pasin Manurangsi, Lisheng
Ren Hardness
of Learning a Single Neuron with Adversarial Label Noise
International Conference on Artificial Intelligence and
Statistics (AISTATS) 2022 (oral presentation).
- Alaa Maalouf, Murad Tukan, Eric Price, Daniel Kane, Dan
Feldman Coresets
for Data Discretization and Sine Wave Fitting, Conference
on Artificial Intelligence and Statistics (AISTATS)
2022.
- Ilias Diakonikolas, Daniel M. Kane, Ankit Pensia, Thanasis
Pittas, Alistair Stewart Statistical
Query Lower Bounds for List-Decodable Linear Regression,
Conference on Neural Information Processing Systems
(NeurIPS) 2021, spotlight presentation.
- Ilias Diakonikolas, Daniel M. Kane, Christos Tzamos Forster
Decomposition and Learning Halfspaces with Noise, Conference
on Neural Information Processing Systems (NeurIPS) 2021,
spotlight presentation.
- Ilias Diakonikolas, Daniel M. Kane, Daniel Kongsgaard, Jerry
Li, Kevin Tian, List-Decodable
Mean Estimation in Nearly-PCA Time, Advances in
Neural Information Processing Systems (NeurIPS) 2021,
spotlight presentation.
- Max Hopkins, Daniel Kane, Shachar Lovett, Michal Moshkovitz
Bounded
Memory Active Learning through Enriched Queries Conference
on Learning Theory (COLT) 2021.
- Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis,
Christos Tzamos, Nikos Zarifis Agnostic
Proper Learning of Halfspaces under Gaussian Marginals Conference
on Learning Theory (COLT) 2021.
- Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas, Nikos
Zarifis The
Optimality of Polynomial Regression for Agnostic Learning
under Gaussian Marginals Conference on Learning
Theory (COLT) 2021.
- Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart, Yuxin
Sun Outlier-Robust
Learning of Ising Models Under Dobrushin’s Condition Conference
on Learning Theory (COLT) 2021.
- Ilias Diakonikolas, Russell Impagliazzo, Daniel Kane, Rex
Lei, Jessica Sorrell, Christos Tzamos Boosting
in the Presence of Massart Noise Conference on
Learning Theory (COLT) 2021.
- Ilias Diakonikolas, Daniel M. Kane, The
Sample Complexity of Robust Covariance Testing, Conference
on Learning Theory (COLT) 2021.
- Ilias Diakonikolas, Themis Gouleakis, Daniel M. Kane, John
Peebles, Eric Price, Optimal
Testing of Discrete Distributions with High Probability,
Symposium on Theory of Computation (STOC) 2021.
- Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis,
Christos Tzamos, Nikos Zarifis, A
Polynomial Time Algorithm for Learning Halfspaces with
Tsybakov Noise, Symposium on Theory of Computation (STOC)
2021.
- Yuval Dagan, Yuval Filmus, Daniel Kane, Shay Moran The
entropy of lies: playing twenty questions with a liar, Innovations
in Theoretical Computer Science (ITCS) 2021.
- Ilias Diakonikolas, Gautam Kamath, Daniel M Kane, Jerry Li,
Ankur Moitra, Alistair Stewart Robustness
Meets Algorithms, Communications of the ACM Vol
64(5) p. 107-115, 2021.
- Daniel M. Kane, Scott Duke Kominers Prisoners,
Rooms, and Lightswitches, Electronic Journal of
Combinatorics, Vol 28 (1), 2021 pp. 1-27.
- Daniel M. Kane Robust
Learning of Mixtures of Gaussians, Symposium
On Discrete Algorithms (SODA) 2021.
- Daniel Kane, Andreas Fackler, Adam Gągol, Damian Straszak, Highway:
Efficient Consensus with Flexible Finality, in
preparation.
- Ilias Diakonikolas, Samuel B. Hopkins, Daniel Kane, Sushrut
Karmalkar Robustly
Learning any Clusterable Mixture of Gaussians, Foundations
Of Computer Science (FOCS) 2020.
- Ilias Diakonikolas, Daniel M. Kane Small
Covers for Near-zero Sets of Polynomials and Learning Latent Variable Models, Foundations
Of Computer Science (FOCS) 2020.
- Max Hopkins, Daniel Kane, Shachar Lovett, Gaurav Mahajan, Point
Location and Active Learning: Learning Halfspaces Almost
Optimally, Foundations
Of
Computer Science (FOCS) 2020.
- Ilias Diakonikolas, Daniel M. Kane, Ankit Pensia Outlier
Robust Mean Estimation with Subgaussian Rates via Stability,
Advances in Neural Information Processing Systems
(NeurIPS) 2020.
- Ilias Diakonikolas, Daniel M. Kane, Pasin Manurangsi The
Complexity of Adversarially Robust Proper Learning of
Halfspaces with Agnostic Noise, Advances in Neural
Information Processing Systems (NeurIPS) 2020.
- Ilias Diakonikolas, Daniel M. Kane, Nikos Zarifis Near-Optimal
SQ Lower Bounds for Agnostically Learning Halfspaces and
ReLUs under Gaussian Marginals, Advances in Neural
Information Processing Systems (NeurIPS) 2020.
- Ilias Diakonikolas, Daniel M. Kane, Daniel Kongsgaard List-Decodable
Mean Estimation via Iterative Multi-Fitering, Advances
in Neural Information Processing Systems (NeurIPS) 2020.
- Max Hopkins, Daniel Kane, Shachar Lovett, The
Power of Comparisons for Actively Learning Linear
Classifiers, Advances in Neural Information
Processing Systems (NeurIPS) 2020.
- Venkata Gandikota, Daniel Kane, Raj Kumar Maity, Arya
Mazumdar Vector
Quantized Stochastic Gradient Descent, 54th Asilomar
Conference on Signals, Systems and Computers (Asilomar)
2020, journal version in IEEE Transactions on Information
Theory, 2022.
- Ilias Diakonikolas, Daniel Kane, Vasileios Kontonis, Nikos
Zarifis Algorithms
and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU
Networks Conference On Learning Theory (COLT)
2020.
- Max Hopkins, Daniel Kane, Shachar Lovett, Gaurav Mahajan Noise-tolerant,
Reliable Active Classification with Comparison Queries,
Conference On Learning Theory (COLT) 2020.
- Ilias Diakonikolas, Daniel M. Kane Recent
Advances in Algorithmic High-Dimensional Robust Statistics,
shortened version in Tim Roughgarden's Beyond Worst Case
Analysis book.
- Daniel M. Kane, Carlo Sanna, Jeffrey Shallit Waring's
Theorem for Binary Powers, Combinatorica Vol 39
(2019) pp. 1335-1350.
- M. Aliakbarpour, I. Diakonikolas, D. Kane, R. Rubinfeld Private
Testing of Distributions via Sample Permutations, Advances
in Neural Information Processing Systems (NeurIPS) 2019.
- Ilias Diakonikolas, Daniel M. Kane, Pasin Manurangsi Nearly
Tight Bounds for Robust Proper Learning of Halfspaces with a
Margin, Advances in Neural Information Processing
Systems (NeurIPS) 2019 (Spotlight Presentation).
- Ilias Diakonikolas, Sushrut Karmalkar, Daniel Kane, Eric
Price, Alistair Stewart Outlier-Robust
High-Dimensional Sparse Estimation via Iterative Filtering,
Advances in Neural Information Processing Systems
(NeurIPS) 2019.
- Daniel M Kane, Roi Livni, Shay Moran, Amir Yehudayoff On
Communication Complexity of Classification Problems, Conference on
Learning Theory (COLT) 2019.
- Surbhi Goel, Daniel M. Kane, Adam R. Klivans Learning
Ising Models with Independent Failures, Conference on
Learning Theory (COLT) 2019.
- Ilias Diakonikolas, Themis Gouleakis, Daniel M. Kane,
Sankeerth Rao, Communication
and Memory Efficient Testing of Discrete Distributions,
Conference on
Learning Theory (COLT) 2019.
- Olivier Bousquet, Daniel Kane, Shay Moran The
Optimal Approximation Factor in Density Estimation, Conference on
Learning Theory (COLT) 2019.
- Ilias Diakonikolas, Daniel M. Kane, John Peebles Testing
Identity of Multidimensional Histograms, Conference on
Learning Theory (COLT) 2019.
- Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li,
Jacob Steinhardt, Alistair Stewart Sever: A
Robust Meta-Algorithm for Stochastic Optimization, International
Conference on Machine Learning (ICML) 2019.
- Ilias Diakonikolas, Daniel M. Kane, Degree-d
Chow Parameters Robustly Determine Degree-d PTFs (and
Algorithmic Applications) Symposium on Theory Of
Computation (STOC) 2019.
- Daniel M Kane, Ryan Williams The
Orthogonal Vectors Conjecture for Branching Programs and
Formulas, Innovations in Theoretical Computer
Science (ITCS) 2019.
- Daniel M. Kane, Robert C. Rhoades A Proof of
Andrews' Conjecture
on Partitions with no Short Sequences, Forum of
Mathematics
Sigma, Vol 7, 2019.
- Ben Green, Daniel M. Kane, An
Example
Concerning Set Addition in F_2^n, Trudy Matematicheskogo Instituta
im. V.A. Steklova Vol 303 (2018) pp.
116-119.
- Ilias Diakonikolas, Daniel M Kane, Alistair Stewart Sharp
Bounds for Generalized Uniformity Testing, Advances
in Neural Information Processing Systems (NeurIPS) 2018,
Spotlight Presentation at NeurIPS 2018.
- Yu Cheng, Ilias Diakonikolas, Daniel M. Kane, Alistair
Stewart Robust
Learning
of Fixed-Structure Bayesian Networks, Neural
Information Processing Systems (NIPS) 2018.
- Daniel M Kane, Shachar Lovett, Shay Moran Generalized
Comparison Trees for Point-Location Problems, International Colloquium on Automata, Languages and
Programming
(ICALP) 2018.
- Ilias Diakonikolas, Daniel M Kane, Alistair Stewart Learning
Geometric Concepts with Nasty Noise, Symposium on
Theory Of Computation (STOC) 2018.
- Clement Canonne, Ilias Diakonikolas, Daniel M.
Kane, Alistair Stewart Testing
Conditional Independence of Discrete Distributions, Symposium
on Theory Of Computation (STOC) 2018.
- Ilias Diakonikolas, Daniel M.
Kane, Alistair Stewart List-Decodable
Robust Mean Estimation and Learning Mixtures of Spherical
Gaussians, Symposium on Theory Of Computation
(STOC) 2018.
- Daniel M Kane, Shachar Lovett, Shay Moran Near-Optimal
Linear Decision
Trees for k-SUM and Related Problems, Symposium on
Theory Of Computation (STOC) 2018, invited to STOC
special issue, Journal of the ACM, Vol 66, no 3
(2019).
- Daniel M Kane, Sankeerth Rao A
PRG for Boolean PTF of Degree 2 with Seed Length
Subpolynomial in ε and Logarithmic in n, Conference on Computational Complexity (CCC)
2018.
- Ilias Diakonikolas, Gautam Kamath, Daniel M.
Kane, Jerry Li, Ankur Moitra, Alistair Stewart Robustly
Learning a Gaussian: Getting Optimal Error Efficiently,
Symposium On Discrete Algorithms (SODA) 2018.
- Daniel M. Kane, Joseph Palmer, Alvaro Pelayo Minimal
Models of Compact
Symplectic Semiotic Manifolds, Journal of Geometry
and Physics, Vol 125 (2018) pp. 48-74.
- Daniel M. Kane,
Joseph Palmer, Alvaro Pelayo Classifying
Toric and Semitoric Fans by
Lifting Equations from SL2(Z),
SIGMA Vol 14 (2018).
- Daniel M. Kane, Zev Klagsbrun, On
the Joint Distribution
Of Selφ(E/Q) and Selφ^(E/Q)
in
Quadratic Twist Families, manuscript.
- Daniel Kane, Sushrut Karmalkar, Eric Price Robust
Polynomial
Regression up to the Information Theoretic Limit, Foundations of Computer
Science (FOCS)
2017.
- Daniel
M. Kane, Shachar Lovett, Shay Moran,
Jiapeng Zhang, Active
Classification
with Comparison Queries, Foundations
Of Computer Science (FOCS) 2017.
- Daniel M Kane, Shachar Lovett, Sankeerth Rao, The
Independence Number
of the Birkhoff Polytope Graph and Applications to Maximally
Recoverable Codes, Foundations Of Computer
Science
(FOCS) 2017, journal version SIAM Journal of computing (SICOMP)
Vol 48, no 4 (2019) pp 1425-1435.
- Ilias Diakonikolas, Daniel M. Kane, Alistair
Stewart Statistical
Query
Lower Bounds for Robust Estimation of High Dimensional
Gaussians and
Gaussian Mixtures, Foundations Of
Computer Science (FOCS) 2017.
- Ilias Diakonikolas, Daniel M. Kane, Vladimir
Nikishkin Near-Optimal
Closeness
Testing of Discrete Histogram Distributions, International Colloquium on Automata, Languages and
Programming
(ICALP) 2017.
- Ilias Diakonikolas, Gautam Kamath, Daniel M.
Kane, Jerry Li, Ankur Moitra, Alistair Stewart Being
Robust in High
Dimensions Can Be Practical, International
Conference on Machine Learning (ICML) 2017.
- Clement Canonne, Ilias Diakonikolas, Daniel M.
Kane, Alistair Stewart Testing
Bayesian
Networks, Conference
on
Learning Theory (COLT) 2017; Journal version in IEEE
Transactions on Information Theory pp. 1-39, 2020.
- Ilias Diakonikolas, Daniel M. Kane, Alistair
Stewart Learning
Multivariate
Log-concave Distributions, Conference
On Learning Theory (COLT)
2017.
- Valentine Kabanets, Daniel M. Kane, Zhenjian Lu A
Polynomial
Restriction Lemma with Applications, Symposium
on Theory Of Computation (STOC)
2017.
- Daniel M. Kane, Terence Tao A
Bound on
Partitioning Clusters, Electronic
Journal of Combinatorics Vol 24 no 2 (2017) #P2.31.
- Daniel M. Kane On
the Crossing
Number of Complete Graphs with an Uncrossed Hamiltonian
Cycle, manuscript.
- Daniel M. Kane, Jack A. Thorne, On
the φ-Selmer Groups of Elliptic Curves y2 = x3
– Dx, Mathematical
Proceedings of the Cambridge Philosophical Society, Vol
163 no 1 (2017) pp. 1–23.
- Chung-Kuan Cheng, Daniel
M. Kane, Ilgweon Kang, Fang Qiao, 3D
Floorplan
Representations: Corner Links and Partial Ordering,
IEEE International 3D
Systems Integration
Conference (3DIC) 2016, Journal Version: Kang, I., Qiao,
F., Park, D., Kane, D., Young, E.F.Y., Cheng, C.K., Graham, R.
Three-dimensional
Floorplan Representations by Using Corner Links and
Partial Order ACM Transactions on Design
Automation of Electronic Systems (TODAES), 24(1), p.13,
2018.
- Ilias Diakonikolas, Daniel M. Kane, Alistair
Stewart Efficient
Robust
Proper Learning of Log-concave Distributions,
manuscript.
- Xue Chen, Daniel M. Kane, Eric Price, Zhao Song, Fourier-sparse
interpolation
without a frequency gap, Foundations
Of Computer Science, (FOCS) 2016.
- Ilias Diakonikolas, Gautam Kamath, Daniel M.
Kane, Jerry Li, Ankur Moitra, Alistair Stewart, Robust
Estimators
in High Dimensions without the Computational Intractability,
Foundations Of Computer
Science, (FOCS)
2016, journal version in SIAM Journal of computing (SICOMP)
Vol 48, no 2 (2019), pp. 742-864.
- Ilias Diakonikolas, Daniel M. Kane, A
New Approach for Testing Properties of Discrete
Distributions, Foundations
Of Computer Science, (FOCS)
2016.
- Mihir Bellare, Daniel M. Kane, Phillip Rogaway Big-Key
Symmetric Encryption:
Resisting Key Exfiltration, International
Cryptography Conference (CRYPTO) 2016.
- Ilias Diakonikolas, Daniel M. Kane, Alistair
Stewart, Nearly
Optimal
Learning and Sparse Covers for Sums of Independent Integer
Random Variables, Conference
On
Learning Theory, (COLT) 2016.
- Ilias Diakonikolas, Daniel M. Kane, Alistair
Stewart, Properly
Learning Poisson Binomial Distributions in Almost
Polynomial Time, Conference On
Learning Theory, (COLT) 2016.
- Daniel M. Kane, Ryan Williams, Super-Linear
Gate and
Super-Quadratic Wire Lower Bounds for Depth-Two and
Depth-Three Threshold
Circuits, Symposium
on the Theory of
Computation (STOC) 2016.
- Ilias Diakonikolas, Daniel M. Kane, Alistair
Stewart The
Fourier
Transform of Poisson Multinomial Distributions and its
Algorithmic Applications, Symposium on the Theory
of Computation (STOC)
2016.
- Mihir Bellare, Joseph Jaeger, Daniel Kane, Mass-surveillance
without the State: Strongly Undetectable
Algorithm-Substitution Attacks on
Symmetric Encryption, Conference
on Computer and Communications Security (CCS) 2016.
- Daniel
M. Kane On the
Number of ABC Solutions with Restricted Radical Sizes, Journal
of Number
Theory, (2015),
pp. 32-43.
- Daniel M. Kane Small
Designs for Path
Connected Spaces and Path Connected Homogeneous Spaces,
Transactions of the AMS,
Vol. 367
(2015), pp. 6387-6414.
- Daniel M. Kane Canonical
Projective
Embeddings of the Deligne-Lusztig Curves Associated to 2A2,
2B2 and 2G2,
International
Mathematics Research Notices,
(2015) pp. 1158-1189.
- Manjul Bhargava, Daniel M. Kane,
Hendrik W.
Lenstra Jr., Bjorn Poonen, Eric Rains Modeling
the Distribution of
Ranks, Selmer Groups, and Shafarevich-Tate Groups of
Elliptic Curves, Cambridge
Journal of Mathematics, Vol. 3
(2015), pp. 275-321.
- Bobbie Chern, Persi Diaconis,
Daniel M. Kane,
Robert C. Rhoades Central
Limit
Theorems for Some Set Partition Statistics, Advances in Applied Mathematics, Vol. 70 (2015),
pp. 92–105.
- Andrew Granville, Daniel M Kane, Dimitris Koukoulopoulos,
Robert J Lemke Oliver Best
Possible Densities of Dickson m-Tuples, as a Consequence of
Zhang–Maynard–Tao in Analytic Number Theory Springer,
2015.
- Ilias Diakonikolas, Daniel M. Kane, Vladimir Nikishkin, Optimal
Algorithms
and Lower Bounds for Testing Closeness of Structured
Distributions, Foundations of Computer
Science,
(FOCS) 2015.
- Parikshit Gopalan, Daniel M. Kane, Raghu Meka, Pseudorandomness
via the
Discrete Fourier Transform, Foundations
of Computer Science (FOCS) 2015, SIAM Journal of
computing (SICOMP) Vol 47, no 6 pp. 2451-2487.
- Daniel M. Kane A
Polylogarthmic PRG for
Degree 2 Threshold Functions in the Gaussian Setting, Conference on Computational Complexity (CCC)
2015.
- Ilias
Diakonikolas, Daniel M. Kane, Vladimir
Nikishkin, Testing
Identity of Structured
Distributions, Symposium
On Discrete Algorithms (SODA)
2015.
- Daniel M. Kane, Osamu Watanabe A Short
Implicant of CNFs with
a Relatively Many Satisfying Assignments, International Symposium on Algorithms And
Computation (ISAAC) 2014;
journal version Algorithmica,
(2016),
DOI: 10.1007/s00453-016-0125-z.
- Daniel M. Kane The
Average Sensitivity
of an Intersection of Half Spaces, Symposium
on the Theory Of Computing 2014, journal
version (open access) in Research In
the Mathematical Sciences Vol. 1 no 1 (2014).
- Daniel M. Kane A
Pseudorandom Generator
for Polynomial Threshold Functions of Gaussians with
Subpolynomial Seed Length, Conference on
Computational Complexity
2014.
- Bobbie Chern, Persi Diaconis,
Daniel M. Kane,
Robert C. Rhoades Closed
Expressions
for Averages of Set Partition Statistics, Research in the Mathematical Sciences, Vol. 1
(2014) no. 2.
- Daniel M. Kane, Scott Duke Kominers
Asymptotic
Improvements of
Lower Bounds for the Least Common Multiples of Arithmetic
Progressions, Canadian
Mathematical Bulletin, Vol. 57
(2014), pp. 551-561.
- Daniel M. Kane, Adam Klivans, Raghu Meka Learning
Half Spaces Under
Log-Concave Densities: Polynomial Approximation and Moment
Matching, Conference
on Learning Theory (COLT) 2013.
- Daniel M. Kane The
Correct Exponent for
the Gotsman-Linial Conjecture, Conference
on Computational Complexity (CCC) 2013 (won best
paper award).
- Daniel
M. Kane, Raghu Meka A PRG
for Lipschitz Functions of Polynomials with Applications
to Sparsest Cut, Symposium on the Theory
of Computation (STOC) 2013.
- Daniel M. Kane A
Low-Depth
Monotone Function Given by a
Low-Depth Decision Tree
that is not an Approximate Junta, Theory
of Computing Vol. 9 (2013) pp. 587-592.
- Noam D. Elkies, Daniel M. Kane,
Scott Duke
Kominers, Minimal
S-Criteria
May Vary in Size, Journal de Theorie des Nombres de
Bordeaux, Vol.
23 no. 3 (2013) pp. 557-563.
- Daniel M. Kane On
the Ranks of the 2-Selmer Groups of Twists of a Given
Elliptic Curve, Algebra
& Number Theory, 7 issue 5 (2013),
pp. 1253-1297.
- Daniel M. Kane An
Asymptotic for the
Number of Solutions to Linear Equations in Prime Numbers
from Specified Chebotarev
Classes, International Journal of Number Theory, Vol. 9 no. 4 (2013) pp.
1073-1111.
- Daniel M. Kane A
Structure
Theorem for Poorly Anticoncentrated Gaussian Chaoses and
Applications to the
Study of Polynomial Threshold Functions, Foundations of Computer Science (FOCS) 2012,
pp. 91-100; journal
version Annals of Probability, Vol. 45 no. 3 (2017) pp.
1612-1679.
- Daniel
M. Kane, Kurt Mehlhorn, Thomas Sauerwald,
He Sun Counting
Arbitrary
Subgraphs in Data Streams, International
Colloquium on Automata, Languages and Programming (ICALP)
2012, pp. 598-609.
- Eric Blais, Daniel Kane Tight
Bounds
for Testing k-Linearity, International
Workshop on Randomization and Computation (RANDOM) 2012.
- Daniel M. Kane, Jelani Nelson, Sparser
Johnson-Lindenstrauss
Transforms, Symposium
on
Discrete Algorithms (SODA) 2012, Journal of the ACM,
Vol. 61 no. 1,
Article 4, 2014.
- Daniel M. Kane, A
Small PRG for Polynomial Threshold Functions of Gaussians,
Foundations of Computer
Science (FOCS)
2011.
- Daniel M. Kane, Raghu Meka, Jelani Nelson, Almost
Optimal
Explicit Johnson-Lindenstrauss Transforms, International Workshop on Randomization and
Computation (RANDOM), 2011.
- Daniel
Kane, Jelani Nelson, A
Derandomized Sparse
Johnson-Lindenstrauss Transform, superseded by Sparser
Johnson-Lindenstrauss
Transforms (above).
- Daniel M. Kane k-Independent
Gaussians
Fool Polynomial Threshold Functions, Conference
on Computational Complexity (CCC), 2011.
- Daniel M. Kane, Jelani Nelson, Ely Porat,
David P. Woodruff, Fast
Moment Estimation in Data Streams in Optimal Space, Symposium
on the
Theory of Computing (STOC) 2011.
- Daniel M. Kane, Samuel A. Kutin, Quantum
Interpolation
of Polynomials, presented at Combinatorics, Groups, Algorithms, and Complexity
(conference in honor
of Laci Babai’s 60th birthday (CGAC) 2010,
journal version in Quantum
Information and Computation Vol.
11 no. 1&2 (2011).
- Daniel M. Kane Unary
Subset-Sum is in
Logspace, unpublished.
- Ilias Diakonikolas, Daniel M. Kane, Jelani
Nelson, Bounded
Independence Fools Degree-2 Threshold Functions, Foundations of Computer Science (FOCS) 2010.
- Daniel M. Kane The
Gaussian Surface Area and Noise Sensitivity of Degree-d
Polynomial Threshold
Functions, in Conference
on
Computational Complexity (CCC) 2010, pp. 205-210 (Won
CCC 2010 best student
paper).
- Daniel M. Kane, Jelani Nelson, David P. Woodruff An
Optimal Algorithm
for the Distinct Elements Problem, Symposium
on Principles of Database Systems (PODS) 2010 (Won PODS
2010 best paper,
and 2010 IBM research Pat Goldberg Memorial Best Paper Award
in Computer
Science, Electrical Engineering and Math). Invited
to Journal of the ACM.
- Daniel M. Kane, Jelani Nelson, David P. Woodruff On the
Exact Space
Complexity of Sketching and Streaming Small Norms, Proceedings of the 21st Annual ACM-SIAM Symposium on
Discrete
Algorithms (SODA) 2010.
- Chris Dodd, Phakawa Jeasakul, Anne
Jirapattanakul, Daniel M. Kane, Becky Robinson, Noah Stein,
Cesar E. Silva Ergodic
Properties of a Class
of Discrete Abelian Group Extensions of Rank-One
Transformations, Colloquium
Mathematicum, 119 (2010), pp.
1-22.
- Daniel M. Kane On
Solving Games
Constructed Using Both Shortened and Continued Conjunctive
Sums, Integers:
Electronic Journal of
Combinatorial Number Theory, 10 (2010), pp. 849-878.
- Daniel M. Kane A
Partition of the Positive Reals into Algebraically Closed
Subsets,
unpublished.
- Erik D. Demaine, Dion Harmon, John Iacono,
Daniel M. Kane, Mihai Pǎtraşcu, The
Geometry of Binary
Search Trees, in Symposium
on
Discrete Algorithms (SODA) 2009.
- Daniel M. Kane, Gregory N. Price, Erik D.
Demaine, A
Pseudopolynomial Algorithm for Alexandrov's Theorem, Algorithms and Data Structures Symposium (WADS)
2009. Also in Lecture
Notes in Computer Science, 5664 (2009) pp. 435–446.
- Bakir Farhi, Daniel Kane New Results
on the Least Common
Multiple of Consecutive Integers, Proceedings
of the AMS, 137 (2009), no. 6, pp. 1933-1939.
- Daniel Kane, Steven Sivek On the
Sn-Modules
Generated by Partitions of a Given Shape, The Electronic Journal of Combinatorics, 15
(2008), 12 pages.
- Daniel M. Kane On
Lower Bounds on the Size of Sums-of-Squares Formulas Journal
of Number
Theory, 128 (2008) pp. 639-644.
- Daniel M. Kane Improved
Bounds on the
Number of Ways of Expressing t as a
Binomial Coefficient, Integers:
Electronic Journal of Combinatorial Number Theory, Vol.
7 (2007), #A53 pp.
1-7.
- Dan Gulotta, Daniel M. Kane, Andrew
Spann Electoral
Redistricting with
Moment of Inertia and Diminishing Halves Models(3.81 MB)
UMAP Journal, Vol.
28 (2007), pp.
281-299
- Daniel M. Kane Weak
Mixing of a
Transformation Similar to Pascal, Colloquium
Mathematicum,
Vol. 108 no. 1(2007), pp. 135-140.
- Daniel M. Kane Asymptotics
of McKay
Numbers for Sn, Journal of Number Theory, Vol.
124 (2007) pp.
200-228.
- Dan Gulotta, Daniel M. Kane, Andrew
Spann Application
of Min-Cost Flow
to Airline Accessibility Services UMAP Journal,
Vol. 27 (2006), pp.
367-385.
- Daniel M. Kane Generalized
Base
Representations Journal of Number Theory, Vol. 120 (2006)
pp. 92-100.
- Daniel M. Kane, Jonathan M. Kane Dropping
Lowest Grades Mathematics Magazine, Vol. 79
(June 2006) pp. 181-189.
- Daniel M. Kane An
Elementary
Derivation of the Asymptotics of Partition Functions The
Ramanujan
Journal, Vol. 11 no. 1(2006)
pp. 49-66.
- Tim G. Abbott, Daniel M. Kane, Paul Valiant On the
Complexity of Two-Player Win-Lose Games Foundations
Of
Computer Science (FOCS) 2005 (Won
Machtey award for best student paper).
- 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, Computational
Geometry: Theory and Applications, Vol. 42, no. 5, July
2009, pages
419–428. Special issue
of selected papers
from the 17th Canadian Conference on Computational Geometry,
2005.
- Tim Abbott, Erik D. Demaine, Martin L. Demaine,
Daniel M. Kane, Setfan Langerman, Jelani Nelson, Vincent Yeung
Dynamic
Ham-Sandwich
Cuts of Polygons in the Plane Canadian
Conference on Computational Geometry, (2005) pp. 61-64.
- Dan Gulotta, Daniel M. Kane, Andrew
Spann Lane
Changes and Close
Following: Troublesome Tollbooth Traffic(6
MB) UMAP
Journal, Vol. 26 no. 3 (2005) pp. 251-264.
- Daniel M. Kane On
the Number of Ways of
Writing t as a Product of Factorials Integers:
Electronic Journal of
Combinatorial Number Theory, Vol. 5 (2005), #A02, pp.
1-10.
- Daniel M. Kane Resolution
of a
Conjecture Involving Cranks of Partitions of Andrews and
Lewis Proceedings
of the American Mathematical Society, Vol. 132 No.
8(2004), pp. 2247-2256.
-
Daniel M. Kane New
Bounds on the
Number of Representations of t as a Binomial Coefficient
Integers: Electronic
Journal of
Combinatorial Number Theory, Vol. 4 (2004), #A07, pp.
1-10.
By Topic:
- Computer Science:
- Learning Theory:
- Robust Statistics:
- Ilias Diakonikolas, Daniel M. Kane, Sushrut Karmalkar, Ankit Pensia, Thanasis Pittas Robust Sparse Estimation for Gaussians with Optimal Error under Huber Contamination, International
Conference on Machine Learning (ICML) 2024.
- Daniel M. Kane, Ilias Diakonikolas, Hanshen Xiao,
Sihan Liu Online
Robust Mean Estimation, Symposium on Discrete
Algorithms (SODA) 2024.
- Ilias Diakonikolas, Daniel M. Kane, Lisheng Ren,
Yuxin Sun SQ Lower Bounds for Non-Gaussian Component Analysis
with Weaker Assumptions, Advances in Neural
Information Processing Systems (NeurIPS) 2023.
- Ilias Diakonikolas, Daniel M. Kane, Ankit Pensia,
Thanasis Pittas Near-Optimal
Algorithms for Gaussians with Huber Contamination:
Mean Estimation and Linear Regression, Advances
in Neural Information Processing Systems
(NeurIPS) 2023.
- Ilias Diakonikolas, Daniel M. Kane, Jasper C. H.
Lee, Ankit Pensia, Thanasis Pittas A
Spectral Algorithm for List-Decodable Covariance
Estimation in Relative Frobenius Norm, Advances
in Neural Information Processing Systems
(NeurIPS) 2023 (spotlight presentation).
- Ilias Diakonikolas, Daniel M. Kane, Ankit Pensia,
Thanasis Pittas Nearly-Linear
Time and Streaming Algorithms for Outlier-Robust PCA,
International Conference on Machine Learning
(ICML) 2023.
- Yu Cheng, Ilias Diakonikolas, Daniel M. Kane, Rong
Ge, Shivam Gupta, Mahdi Soltanolkotabi Outlier-Robust
Sparse Estimation via Non-Convex Optimization, Advances
in Neural Information Processing Systems
(NeurIPS) 2022.
- Ilias Diakonikolas, Daniel M. Kane, Sushrut
Karmalkar, Ankit Pensia, Thanasis Pittas List-Decodable
Sparse Mean Estimation via Difference-of-Pairs
Filtering, Advances in Neural Information
Processing Systems (NeurIPS) 2022 (oral
presentation).
- Ilias Diakonikolas, Daniel M. Kane, Jasper C.H. Lee,
Ankit Pensia Outlier-Robust
Sparse Mean Estimation for Heavy-Tailed
Distributions, Advances in Neural
Information Processing Systems (NeurIPS) 2022.
- Ilias Diakonikolas, Daniel M. Kane, Sushrut
Karmalkar, Ankit Pensia, Thanasis Pittas Robust
Sparse Mean Estimation via Sum of Squares,
Conference on Learning Theory (COLT) 2022.
- Ilias Diakonikolas, Daniel M. Kane, Yuxin Sun, Optimal
SQ Lower Bounds for Robustly Learning Discrete
Product Distributions and Ising Models, Conference
on Learning Theory (COLT) 2022.
- Ilias Diakonikolas, Daniel M. Kane, Ankit Pensia,
Thanasis Pittas Streaming
Algorithms for High-Dimensional Robust Statistics,
International Conference on Machine Learning
(ICML) 2022.
- Ainesh Bakshi, Ilias Diakonikolas, He Jia, Daniel M.
Kane, Pravesh K. Kothari, Santosh S. Vempala, Robustly
Learning Mixtures of k Arbitrary Gaussians, Symposium
on Theory of Computation (STOC) 2022.
- Ilias Diakonikolas, Daniel M. Kane, Daniel
Kongsgaard, Jerry Li, Kevin Tian Clustering
Mixture Models in Almost-Linear Time via
List-Decodable Mean Estimation, Symposium on
Theory of Computation (STOC) 2022.
- Ilias Diakonikolas, Daniel M. Kane, Ankit Pensia,
Thanasis Pittas, Alistair Stewart Statistical
Query Lower Bounds for List-Decodable Linear
Regression, Conference on Neural Information
Processing Systems (NeurIPS) 2021, spotlight
presentation.
- Ilias Diakonikolas, Daniel M. Kane, Alistair
Stewart, Yuxin Sun Outlier-Robust
Learning of Ising Models Under Dobrushin’s Condition,
Conference on
Learning Theory (COLT) 2021.
- Ilias Diakonikolas, Daniel M. Kane, The
Sample Complexity of Robust Covariance Testing,
Conference on
Learning Theory (COLT) 2021.
- Ilias Diakonikolas, Gautam Kamath, Daniel M Kane,
Jerry Li, Ankur Moitra, Alistair Stewart Robustness
Meets Algorithms, Communications of the ACM
Vol 64(5) p. 107-115, 2021.
- Ilias Diakonikolas, Daniel M. Kane, Daniel
Kongsgaard, Jerry Li, Kevin Tian, List-Decodable
Mean Estimation in Nearly-PCA Time, Advances
in Neural Information Processing Systems
(NeurIPS) 2021, spotlight presentation.
- Daniel M. Kane Robust
Learning of Mixtures of Gaussians, Symposium
On Discrete Algorithms (SODA) 2021.
- Ilias Diakonikolas, Daniel M. Kane, Ankit Pensia Outlier
Robust Mean Estimation with Subgaussian Rates via
Stability, Advances in Neural Information
Processing Systems (NeurIPS) 2020.
- Ilias Diakonikolas, Daniel M. Kane, Nikos Zarifis Near-Optimal
SQ Lower Bounds for Agnostically Learning Halfspaces
and ReLUs under Gaussian Marginals, Advances
in Neural Information Processing Systems
(NeurIPS) 2020.
- Ilias Diakonikolas, Daniel M. Kane, Daniel
Kongsgaard List-Decodable
Mean Estimation via Iterative Multi-Fitering, Advances
in Neural Information Processing Systems
(NeurIPS) 2020.
- Ilias Diakonikolas, Samuel B. Hopkins, Daniel Kane,
Sushrut Karmalkar Robustly
Learning any Clusterable Mixture of Gaussians, Foundations
Of Computer Science (FOCS) 2020.
- Ilias Diakonikolas, Daniel M. Kane Recent
Advances in Algorithmic High-Dimensional Robust
Statistics, shortened version in Tim
Roughgarden's Beyond Worst Case Analysis book.
- Ilias Diakonikolas, Sushrut Karmalkar, Daniel Kane,
Eric Price, Alistair Stewart Outlier-Robust
High-Dimensional Sparse Estimation via Iterative
Filtering, Advances in Neural Information
Processing Systems (NeurIPS 2019).
- Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane,
Jerry Li, Jacob Steinhardt, Alistair Stewart Sever:
A Robust Meta-Algorithm for Stochastic Optimization,
International
Conference on Machine Learning (ICML) 2019.
- Yu Cheng, Ilias Diakonikolas, Daniel M. Kane,
Alistair
Stewart Robust
Learning
of Fixed-Structure Bayesian Networks, Neural
Information Processing Systems (NIPS) 2018.
- Ilias Diakonikolas, Daniel M Kane, Alistair Stewart
Learning
Geometric Concepts with Nasty Noise, Symposium
on Theory Of Computation (STOC) 2018.
- Ilias Diakonikolas, Daniel M.
Kane, Alistair Stewart List-Decodable
Robust Mean Estimation and Learning Mixtures of
Spherical Gaussians, Symposium on Theory Of
Computation (STOC) 2018.
- Ilias Diakonikolas, Gautam Kamath, Daniel M.
Kane, Jerry Li, Ankur Moitra, Alistair Stewart Robustly
Learning a Gaussian: Getting Optimal Error
Efficiently, Symposium On Discrete
Algorithms (SODA) 2018.
- Ilias Diakonikolas, Daniel M. Kane, Alistair
Stewart Statistical
Query
Lower Bounds for Robust Estimation of High
Dimensional Gaussians and
Gaussian Mixtures, Foundations Of
Computer Science (FOCS) 2017.
- Ilias Diakonikolas, Gautam Kamath, Daniel M.
Kane, Jerry Li, Ankur Moitra, Alistair Stewart Being
Robust in High
Dimensions Can Be Practical, International
Conference on Machine Learning (ICML) 2017.
- Ilias Diakonikolas, Gautam Kamath, Daniel M.
Kane, Jerry Li, Ankur Moitra, Alistair Stewart, Robust
Estimators
in High Dimensions without the Computational
Intractability, Foundations Of
Computer Science, (FOCS)
2016, journal version in SIAM Journal of computing
(SICOMP) Vol 48, no 2 (2019), pp. 742-864.
- Testing Discrete Distributions:
- Yuqian Cheng, Daniel M. Kane, Zhicheng Zheng New
Lower Bounds for Testing Monotonicity and Log
Concavity of Distributions, Conference on
Learning Theory (COLT) 2024.
- Clément L. Canonne, Ilias Diakonikolas, Daniel M.
Kane, Sihan Liu Near-Optimal
Bounds for Testing Histogram Distributions, Advances
in Neural Information Processing Systems
(NeurIPS) 2022.
- Ilias Diakonikolas, Themis Gouleakis, Daniel M.
Kane, John Peebles, Eric Price, Optimal
Testing of Discrete Distributions with High
Probability, Symposium on Theory of
Computation (STOC) 2021.
- M. Aliakbarpour, I. Diakonikolas, D. Kane, R.
Rubinfeld Private
Testing of Distributions via Sample Permutations,
Advances in Neural Information Processing Systems
(NeurIPS 2019).
- Ilias Diakonikolas, Themis Gouleakis, Daniel M.
Kane, Sankeerth Rao, Communication
and Memory Efficient Testing of Discrete
Distributions, Conference on
Learning Theory (COLT) 2019.
- Ilias Diakonikolas, Daniel M Kane, Alistair Stewart
Sharp
Bounds for Generalized Uniformity Testing, Advances
in Neural Information Processing Systems
(NeurIPS) 2018, Spotlight Presentation at NeurIPS
2018.
- Clement Canonne, Ilias Diakonikolas, Daniel M.
Kane, Alistair Stewart Testing
Conditional Independence of Discrete Distributions,
Symposium on Theory Of Computation (STOC) 2018.
- Ilias Diakonikolas, Daniel M. Kane, A
New Approach for Testing Properties of Discrete
Distributions, Foundations Of
Computer Science, (FOCS)
2016.
- Structured Learning/Testing Problems:
- Ilias Diakonikolas, Daniel M. Kane Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials, Conference on
Learning Theory (COLT) 2024.
- Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas, Nikos Zarifis Statistical Query Lower Bounds for Learning Truncated Gaussians, Conference on
Learning Theory (COLT) 2024.
- Ilias Diakonikolas, Daniel M. Kane, Sihan Liu Testing Closeness of Multivariate Distributions via Ramsey Theory, Symposium
on Theory of Computation (STOC) 2024.
- Ilias Diakonikolas, Daniel M. Kane, Yuxin Sun SQ
Lower Bounds for Learning Mixtures of Linear
Classifiers, Advances in Neural Information
Processing Systems (NeurIPS) 2023.
- Ilias Diakonikolas, Daniel M. Kane Efficiently
Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials, in preparation.
- Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas,
Nikos Zarifis SQ Lower
Bounds for Learning Bounded Covariance GMMs, Conference on
Learning Theory (COLT)
2023.
- Ilias Diakonikolas, Daniel M. Kane, Yuetian Luo,
Anru R. Zhang Statistical
and Computational Limits for Tensor-on-Tensor
Association Detection, Conference on
Learning Theory (COLT)
2023.
- Ilias Diakonikolas, Daniel M. Kane, Ankit Pensia Gaussian
Mean Testing Made Simple, Symposium on
Simplicity in Algorithms (SOSA 2023).
- Ilias Diakonikolas, Daniel M. Kane, John Peebles Testing
Identity of Multidimensional Histograms, Conference on
Learning Theory (COLT) 2019.
- Ilias Diakonikolas, Daniel M. Kane, Vladimir
Nikishkin Near-Optimal
Closeness
Testing of Discrete Histogram Distributions, International Colloquium on Automata,
Languages and Programming
(ICALP) 2017.
- Ilias Diakonikolas, Daniel M. Kane, Alistair
Stewart, Nearly
Optimal
Learning and Sparse Covers for Sums of Independent
Integer Random Variables, Conference On
Learning Theory, (COLT) 2016.
- Ilias Diakonikolas, Daniel M. Kane, Alistair
Stewart, Properly
Learning
Poisson Binomial Distributions in Almost
Polynomial Time, Conference On
Learning Theory, (COLT) 2016.
- Ilias Diakonikolas, Daniel M. Kane, Alistair
Stewart The
Fourier
Transform of Poisson Multinomial Distributions and
its Algorithmic Applications, Symposium on the
Theory of Computation (STOC)
2016.
- Ilias Diakonikolas, Daniel M. Kane, Vladimir Nikishkin, Optimal
Algorithms
and Lower Bounds for Testing Closeness of
Structured Distributions, Foundations of
Computer Science,
(FOCS) 2015.
- Ilias Diakonikolas, Daniel M. Kane, Vladimir Nikishkin, Testing
Identity of Structured
Distributions, Symposium On Discrete Algorithms (SODA)
2015.
- Active Learning and Inference Dimension:
- Max Hopkins, Daniel Kane, Shachar Lovett, Michal
Moshkovitz Bounded
Memory Active Learning through Enriched Queries,
Conference on
Learning Theory (COLT)
2021.
- Max Hopkins, Daniel M. Kane, Shachar Lovett, Gaurav
Mahajan Point
Location and Active Learning: Learning Halfspaces
Almost Optimally, Foundations
Of Computer Science (FOCS) 2020.
- Max Hopkins, Daniel Kane, Shachar Lovett, The
Power of Comparisons for Actively Learning Linear
Classifiers, Advances in Neural Information
Processing Systems (NeurIPS) 2020.
- Max Hopkins, Daniel Kane, Shachar Lovett, Gaurav
Mahajan Noise-tolerant,
Reliable Active Classification with Comparison
Queries, Conference On Learning Theory (COLT)
2020.
- Daniel M Kane, Shachar Lovett, Shay Moran Generalized
Comparison Trees for Point-Location Problems, International Colloquium on Automata,
Languages and Programming
(ICALP) 2018.
- Daniel M Kane, Shachar Lovett, Shay Moran Near-Optimal
Linear Decision
Trees for k-SUM and Related Problems, Symposium
on Theory Of Computation (STOC) 2018, invited to
STOC special issue, Journal of the ACM, Vol
66, no 3 (2019).
- Daniel M. Kane, Shachar Lovett, Shay Moran,
Jiapeng Zhang, Active
Classification
with Comparison Queries Foundations
Of Computer Science (FOCS) 2017.
- Learning Functions:
- Ilias Diakonikolas, Daniel M Kane, Sihan Liu, Nikos Zarifis Testable Learning of General Halfspaces with Adversarial Label Noise, Conference on
Learning Theory (COLT) 2024.
- Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis Agnostically Learning Multi-index Models with Queries, in preparation.
- Ilias Diakonikolas, Daniel M. Kane, Vasilis
Kontonis, Sihan Liu, Nikos Zarifis Efficient
Testable Learning of Halfspaces with Adversarial
Label Noise, Advances in Neural Information
Processing Systems (NeurIPS) 2023.
- Ilias Diakonikolas, Daniel M. Kane, Lisheng Ren Near-Optimal
Cryptographic Hardness of Agnostically Learning
Halfspaces and ReLU Regression under Gaussian
Marginals, International Conference on
Machine Learning (ICML) 2023.
- Ilias Diakonikolas, Daniel Kane, Pasin Manurangsi,
Lisheng Ren Hardness
of Learning a Single Neuron with Adversarial Label
Noise International Conference on Artificial
Intelligence and Statistics (AISTATS) 2022
(oral presentation).
- Ilias Diakonikolas, Daniel M. Kane, Christos Tzamos
Forster
Decomposition and Learning Halfspaces with Noise,
Conference on Neural Information Processing Systems
(NeurIPS) 2021, spotlight presentation.
- Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas,
Nikos Zarifis The
Optimality of Polynomial Regression for Agnostic
Learning under Gaussian Marginals, Conference on
Learning Theory (COLT) 2021.
- Ilias Diakonikolas, Daniel M. Kane, Vasilis
Kontonis, Christos Tzamos, Nikos Zarifis Agnostic
Proper Learning of Halfspaces under Gaussian
Marginals, Conference on
Learning Theory (COLT) 2021.
- Ilias Diakonikolas, Daniel M. Kane Small
Covers for Near-zero Sets of Polynomials and Learning Latent Variable Models,
Foundations
Of Computer Science (FOCS) 2020.
- Ilias Diakonikolas, Daniel M. Kane, Pasin Manurangsi
The
Complexity of Adversarially Robust Proper Learning
of Halfspaces with Agnostic Noise, Advances
in Neural Information Processing Systems
(NeurIPS) 2020.
- Ilias Diakonikolas, Daniel Kane, Vasileios Kontonis,
Nikos Zarifis Algorithms
and SQ Lower Bounds for PAC Learning
One-Hidden-Layer ReLU Networks Conference On
Learning Theory (COLT) 2020.
- Ilias Diakonikolas, Daniel M. Kane, Pasin Manurangsi
Nearly
Tight Bounds for Robust Proper Learning of
Halfspaces with a Margin, Advances in Neural
Information Processing Systems (NeurIPS 2019)
(Spotlight Presentation).
- Ilias Diakonikolas, Daniel M. Kane, Vasilis
Kontonis, Christos Tzamos, Nikos Zarifis, A
Polynomial Time Algorithm for Learning Halfspaces
with Tsybakov Noise, Symposium on Theory of
Computation (STOC) 2021.
- Daniel Kane, Sushrut Karmalkar, Eric Price Robust
Polynomial
Regression up to the Information Theoretic Limit,
Foundations of
Computer Science (FOCS)
2017.
- Xue Chen, Daniel M. Kane, Eric Price, Zhao Song, Fourier-sparse
interpolation
without a frequency gap, Foundations
Of Computer Science, (FOCS) 2016.
- Semi-Random Noise Models:
- Ilias Diakonikolas, Jelena Diakonikolas, Daniel M.
Kane, Puqian Wang, Nikos Zarifis Near-Optimal
Bounds for Learning Gaussian Halfspaces with Random
Classification Noise, Advances in Neural
Information Processing Systems (NeurIPS) 2023.
- Ilias Diakonikolas, Jelena Diakonikolas, Daniel M.
Kane, Puqian Wang, Nikos Zarifis Information-Computation
Tradeoffs for Learning Margin Halfspaces with Random
Classification Noise, Conference on
Learning Theory (COLT) 2023.
- Ilias Diakonikolas, Daniel M. Kane, Lisheng Ren, Yuxin
Sun SQ
Lower Bounds for Learning Single Neurons with Massart
Noise, Advances in Neural Information
Processing Systems (NeurIPS) 2022.
- Ilias Diakonikolas, Daniel M. Kane, Pasin Manurangsi,
Lisheng Ren Cryptographic
Hardness of Learning Halfspaces with Massart Noise,
Advances in Neural Information Processing Systems
(NeurIPS) 2022.
- Ilias Diakonikolas, Daniel M. Kane, Near-Optimal
Statistical Query Hardness of Learning Halfspaces with
Massart Noise, Conference on Learning Theory
(COLT) 2022.
- Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis,
Christos Tzamos, Nikos Zarifis Learning
General Halfspaces with General Massart Noise under
the Gaussian Distribution, Symposium on Theory
of Computation (STOC) 2022.
- Ilias Diakonikolas, Russell Impagliazzo, Daniel Kane,
Rex Lei, Jessica Sorrell, Christos Tzamos Boosting
in the Presence of Massart Noise, Conference on
Learning Theory (COLT) 2021.
- Other Learning Theory:
- Ilias Diakonikolas, Daniel M. Kane, Jasper C. H. Lee, Thanasis Pittas Clustering Mixtures of Bounded Covariance Distributions Under Optimal Separation, in preparation.
- Max Hopkins, Daniel M. Kane, Shachar Lovett, Gaurav
Mahajan Do
PAC-Learners Learn the Marginal Distribution?,
in preparation.
- Daniel Kane, Sihan Liu, Shachar Lovett, Gaurav
Mahajan, Csaba Szepesvári, Gellért Weisz Exponential
Hardness of Reinforcement Learning with Linear
Function Approximation, Conference on
Learning Theory (COLT)
2023.
- Ilias Diakonikolas, Christos Tzamos, Daniel Kane A
Strongly Polynomial Algorithm for Approximate
Forster Transforms and its Application to Halfspace
Learning, Symposium on Theory of Computation
(STOC) 2023.
- Daniel Kane, Sihan Liu, Shachar Lovett, Gaurav
Mahajan Computational-Statistical
Gaps in Reinforcement Learning, in preparation.
- Max Hopkins, Daniel Kane, Shachar Lovett, Gaurav Mahajan Realizable
Learning is All You Need, Conference on Learning
Theory (COLT) 2022, Journal version TheoretiCS, Vol 3 (2024).
- Ilias Diakonikolas, Daniel M. Kane Non-Gaussian
Component Analysis via Lattice Basis Reduction,
Conference on Learning Theory (COLT) 2022.
- Ilias Diakonikolas, Daniel M. Kane, Alistair
Stewart Efficient
Robust
Proper Learning of Log-concave Distributions,
manuscript.
- Yuval Dagan, Yuval Filmus, Daniel Kane, Shay Moran The entropy
of lies: playing twenty questions with a liar, Innovations
in Theoretical Computer Science (ITCS) 2021.
- Daniel M Kane, Roi Livni, Shay Moran, Amir
Yehudayoff On
Communication Complexity of Classification Problems,
Conference on
Learning Theory (COLT) 2019.
- Surbhi Goel, Daniel M. Kane, Adam R. Klivans Learning
Ising Models with Independent Failures, Conference on
Learning Theory (COLT) 2019.
- Olivier Bousquet, Daniel Kane, Shay Moran The
Optimal Approximation Factor in Density Estimation,
Conference on
Learning Theory (COLT) 2019.
- Clement Canonne, Ilias Diakonikolas, Daniel M.
Kane, Alistair Stewart Testing
Bayesian
Networks, Conference
on
Learning Theory (COLT) 2017; Journal version in
IEEE Transactions on Information Theory pp.
1-39, 2020.
- Ilias Diakonikolas, Daniel M. Kane, Alistair
Stewart Learning
Multivariate
Log-concave Distributions, Conference
On Learning Theory
(COLT) 2017.
- Polynomial Threshold Functions:
- 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, Symposium
on Theory of Computation (STOC) 2024.
- Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan with
appendix by Daniel Kane Fooling
Gaussian PTFs via Local Hyperconcentration,
Journal of the ACM, to appear.
- Ilias Diakonikolas, Daniel M. Kane, Degree-d
Chow Parameters Robustly Determine Degree-d PTFs (and
Algorithmic Applications) Symposium on Theory
Of Computation (STOC) 2019.
- Daniel M Kane, Sankeerth Rao A
PRG for Boolean PTF of Degree 2 with Seed Length
Subpolynomial in ε and Logarithmic in n,
Conference on Computational Complexity
(CCC) 2018.
- Valentine Kabanets, Daniel M. Kane, Zhenjian Lu A
Polynomial
Restriction Lemma with Applications, Symposium
on Theory Of Computation (STOC)
2017.
- Parikshit Gopalan, Daniel M. Kane, Raghu Meka, Pseudorandomness
via the
Discrete Fourier Transform, Foundations
of Computer Science (FOCS) 2015, SIAM Journal
of computing (SICOMP) Vol 47, no 6 pp. 2451-2487.
- Daniel M. Kane A
Polylogarthmic PRG for
Degree 2 Threshold Functions in the Gaussian Setting,
Conference on Computational Complexity
(CCC) 2015.
- Daniel M. Kane The
Average Sensitivity
of an Intersection of Half Spaces, Symposium
on the Theory Of Computing 2014, journal
version (open access) in Research In
the Mathematical Sciences Vol. 1 no 1 (2014).
- Daniel M. Kane A
Pseudorandom Generator
for Polynomial Threshold Functions of Gaussians with
Subpolynomial Seed Length, Conference on
Computational Complexity
2014.
- Daniel M. Kane, Adam Klivans, Raghu Meka Learning
Half Spaces Under
Log-Concave Densities: Polynomial Approximation and
Moment Matching, Conference on
Learning Theory (COLT) 2013.
- Daniel M. Kane The
Correct Exponent for
the Gotsman-Linial Conjecture, Conference
on Computational Complexity (CCC) 2013 (won
best paper award).
- Daniel
M. Kane, Raghu Meka A
PRG
for Lipschitz Functions of Polynomials with
Applications to Sparsest Cut, Symposium on the
Theory of Computation (STOC) 2013.
- Daniel M. Kane A
Structure
Theorem for Poorly Anticoncentrated Gaussian Chaoses
and Applications to the
Study of Polynomial Threshold Functions, Foundations of Computer Science (FOCS) 2012, pp. 91-100; journal
version Annals of Probability, Vol. 45 no. 3
(2017) pp. 1612-1679.
- Daniel
M. Kane, A
Small PRG for Polynomial Threshold Functions of
Gaussians, Foundations of
Computer Science (FOCS)
2011.
- Daniel
M. Kane k-Independent
Gaussians
Fool Polynomial Threshold Functions, Conference
on Computational Complexity (CCC), 2011.
- Ilias
Diakonikolas, Daniel M. Kane, Jelani
Nelson, Bounded
Independence
Fools Degree-2 Threshold Functions, Foundations of Computer Science (FOCS)
2010.
- Daniel M. Kane The
Gaussian Surface Area and Noise Sensitivity of
Degree-d Polynomial Threshold
Functions, in Conference
on
Computational Complexity (CCC) 2010, pp. 205-210 (Won CCC 2010 best
student
paper).
- Streaming Algorithms:
- Daniel M. Kane, Kurt Mehlhorn, Thomas Sauerwald,
He Sun Counting
Arbitrary
Subgraphs in Data Streams, International
Colloquium on Automata, Languages and Programming (ICALP)
2012, pp. 598-609.
- Daniel M.
Kane, Jelani Nelson, Ely Porat,
David P. Woodruff, Fast
Moment
Estimation in Data Streams in Optimal Space, Symposium on
the
Theory of Computing (STOC) 2011.
- Daniel M.
Kane, Jelani Nelson, David P. Woodruff An
Optimal Algorithm
for the Distinct Elements Problem, Symposium
on Principles of Database Systems (PODS)
2010 (Won PODS 2010 best paper,
and 2010 IBM research Pat Goldberg Memorial Best Paper
Award in Computer
Science, Electrical Engineering and Math). Invited
to Journal of the ACM.
- Daniel M.
Kane, Jelani Nelson, David P. Woodruff On
the Exact Space
Complexity of Sketching and Streaming Small Norms,
Proceedings of the 21st Annual ACM-SIAM
Symposium on Discrete
Algorithms (SODA) 2010.
- Johnson-Lindenstrauss:
- Daniel M. Kane, Jelani Nelson, Sparser
Johnson-Lindenstrauss
Transforms, Symposium
on Discrete Algorithms (SODA) 2012, Journal of the
ACM, Vol. 61 no. 1,
Article 4, 2014.
- Daniel M. Kane, Raghu
Meka, Jelani Nelson, Almost
Optimal
Explicit Johnson-Lindenstrauss Transforms, International Workshop on Randomization and
Computation (RANDOM), 2011.
- Daniel Kane,
Jelani Nelson, A
Derandomized Sparse
Johnson-Lindenstrauss Transform, superseded by Sparser
Johnson-Lindenstrauss
Transforms (above).
- Circuit Complexity:
- Security:
- Computational Geometry:
- Daniel M.
Kane, Gregory N. Price, Erik D.
Demaine, A
Pseudopolynomial Algorithm for Alexandrov's Theorem,
Algorithms and Data Structures Symposium (WADS)
2009. Also
in Lecture
Notes in Computer Science, 5664 (2009) pp.
435–446.
- 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, Computational
Geometry: Theory and Applications, Vol. 42, no.
5, July 2009, pages
419–428. Special
issue of selected papers
from the 17th Canadian Conference on Computational
Geometry, 2005.
- Tim Abbott, Erik D.
Demaine, Martin L. Demaine,
Daniel M. Kane, Setfan Langerman, Jelani Nelson,
Vincent Yeung Dynamic
Ham-Sandwich
Cuts of Polygons in the Plane Canadian
Conference on Computational Geometry, (2005) pp.
61-64.
- Other Computer Science:
- Daniel M. Kane, Anthony Ostuni, Kewen Wu Locality Bounds for Sampling Hamming Slices, Symposium
on Theory of Computation (STOC) 2024.
- Daniel M. Kane, Ilias Diakonikolas A
Nearly Tight Bound for Fitting an Ellipsoid to
Gaussian Random Points, Conference on
Learning Theory (COLT) 2023.
- Daniel Beaglehole, Max Hopkins, Daniel Kane, Sihan
Liu, Shachar Lovett Sampling
Equilibria: Fast No-Regret Learning in Structured
Games, Symposium on Discrete
Algorithms (SODA) 2023.
- Alaa Maalouf, Murad Tukan, Eric Price, Daniel Kane,
Dan Feldman Coresets
for Data Discretization and Sine Wave Fitting, Conference
on Artificial Intelligence and Statistics
(AISTATS) 2022.
- Daniel Kane, Andreas Fackler, Adam
Gągol, Damian Straszak, Highway:
Efficient Consensus with Flexible Finality, in
preparation.
- Daniel M. Kane, Shahed Sharif, Alice Silverberg Quantum
Money from Quaternion Algebras, MathCrypt 2022.
- Venkata Gandikota, Daniel Kane, Raj
Kumar Maity, Arya Mazumdar Vector
Quantized Stochastic Gradient Descent, 4th
Asilomar Conference on Signals, Systems and Computers
(Asilomar) 2020, journal version in IEEE
Transactions on Information Theory, 2022.
- Jeffery S. Cohen, Daniel M. Kane Bounds on
the
Independence Required for Cuckoo Hashing,
manuscript.
- Chung-Kuan Cheng, Daniel
M. Kane, Ilgweon Kang, Fang
Qiao, 3D
Floorplan
Representations: Corner Links and Partial Ordering,
IEEE International
3D Systems Integration
Conference (3DIC) 2016, Journal Version: Kang, I.,
Qiao, F., Park, D., Kane, D., Young, E.F.Y., Cheng,
C.K., Graham, R. Three-dimensional
Floorplan Representations by Using Corner Links and
Partial Order ACM Transactions on Design
Automation of Electronic Systems (TODAES), 24(1),
p.13, 2018.
- Daniel M Kane, Shachar Lovett, Sankeerth Rao, The
Independence Number
of the Birkhoff Polytope Graph and Applications to
Maximally Recoverable Codes, Foundations Of
Computer Science
(FOCS) 2017, journal version SIAM Journal of
computing (SICOMP) Vol 48, no 4 (2019) pp
1425-1435.
- Daniel M. Kane, Osamu Watanabe A
Short Implicant of CNFs with
a Relatively Many Satisfying Assignments, International Symposium on Algorithms And
Computation (ISAAC) 2014;
journal version Algorithmica,
(2016),
DOI: 10.1007/s00453-016-0125-z.
- Daniel M. Kane A
Low-Depth
Monotone Function Given by
a Low-Depth Decision Tree
that is not an Approximate Junta, Theory
of Computing Vol. 9 (2013) pp. 587-592.
- Eric Blais, Daniel Kane Tight
Bounds
for Testing k-Linearity, International
Workshop on Randomization and Computation (RANDOM) 2012.
- Daniel M.
Kane, Samuel A. Kutin, Quantum
Interpolation
of Polynomials, presented at Combinatorics, Groups, Algorithms, and
Complexity (conference in honor
of Laci Babai’s 60th birthday (CGAC)
2010, journal version in Quantum
Information and Computation Vol.
11 no. 1&2 (2011).
- Daniel M.
Kane Unary
Subset-Sum is in
Logspace, unpublished.
- Erik D.
Demaine, Dion Harmon, John Iacono,
Daniel M. Kane, Mihai Pǎtraşcu, The
Geometry of Binary
Search Trees, in Symposium on
Discrete Algorithms (SODA) 2009.
- Daniel M.
Kane, Jonathan M. Kane Dropping
Lowest Grades Mathematics Magazine, Vol.
79 (June 2006) pp. 181-189.
- Tim G.
Abbott, Daniel M. Kane, Paul Valiant On the
Complexity of Two-Player Win-Lose Games Foundations Of Computer Science
(FOCS) 2005 (Won
Machtey award for best student paper).
- Mathematics:
- Number Theory:
- Arithmetic Statistics:
- Daniel M. Kane, Zev Klagsbrun, On
the Joint Distribution
Of Selφ(E/Q)
and Selφ^(E/Q) in
Quadratic Twist Families, in preparation.
- Daniel M. Kane, Jack A. Thorne, On
the φ-Selmer Groups of Elliptic Curves y2
= x3 – Dx,
Mathematical
Proceedings of the Cambridge Philosophical Society,
Vol 163 no 1 (2017) pp. 1–23.
- Manjul Bhargava, Daniel M. Kane, Hendrik W.
Lenstra Jr., Bjorn Poonen, Eric Rains Modeling
the Distribution of
Ranks, Selmer Groups, and Shafarevich-Tate Groups of
Elliptic Curves, Cambridge Journal
of Mathematics, Vol. 3
(2015), pp. 275-321.
- Daniel M. Kane On
the Ranks of the 2-Selmer Groups of Twists of a
Given Elliptic Curve, Algebra &
Number Theory, 7 issue 5 (2013),
pp. 1253-1297.
- Additive Combinatorics:
- Other Number Theory:
- Daniel M. Kane, Robert C. Rhoades A
Proof of Andrews' Conjecture
on Partitions with no Short Sequences, Forum
of Mathematics
Sigma, Vol 7, 2019.
- Daniel M. Kane On
the Crossing
Number of Complete Graphs with an Uncrossed
Hamiltonian Cycle, manuscript.
- Daniel M. Kane On the
Number of ABC Solutions with Restricted Radical
Sizes, Journal of Number
Theory,
(2015), pp. 32-43.
- Andrew Granville, Daniel M Kane, Dimitris
Koukoulopoulos, Robert J Lemke Oliver Best
Possible Densities of Dickson m-Tuples, as a
Consequence of Zhang–Maynard–Tao in Analytic
Number Theory Springer, 2015.
- Daniel M. Kane, Scott Duke Kominers Asymptotic
Improvements of
Lower Bounds for the Least Common Multiples of
Arithmetic Progressions, Canadian
Mathematical Bulletin, Vol. 57
(2014), pp. 551-561
- Noam D. Elkies, Daniel M. Kane, Scott Duke
Kominers, Minimal
S-Criteria
May Vary in Size, Journal de Theorie des
Nombres de Bordeaux, Vol. 23 no. 3
(2013) pp. 557-563.
- Daniel M. Kane An
Asymptotic for the
Number of Solutions to Linear Equations in Prime
Numbers from Specified Chebotarev
Classes, International Journal of Number Theory, Vol. 9 no. 4 (2013) pp. 1073-1111.
- Bakir Farhi, Daniel Kane New
Results on the Least Common
Multiple of Consecutive Integers, Proceedings
of the AMS, 137 (2009), no. 6, pp. 1933-1939.
- Daniel Kane, Steven Sivek On
the Sn-Modules
Generated by Partitions of a Given Shape, The Electronic Journal of Combinatorics,
15 (2008), 12 pages.
- Daniel M. Kane On
Lower Bounds on the Size of Sums-of-Squares Formulas
Journal of Number
Theory, 128 (2008) pp. 639-644.
- Daniel M. Kane Improved
Bounds on the
Number of Ways of Expressing t as a
Binomial Coefficient, Integers:
Electronic Journal of Combinatorial Number Theory,
Vol. 7 (2007), #A53 pp.
1-7.
- Daniel M. Kane Asymptotics
of McKay
Numbers for Sn, Journal of Number Theory,
Vol. 124 (2007) pp.
200-228.
- Daniel M. Kane Generalized
Base
Representations Journal of Number Theory, Vol. 120
(2006) pp. 92-100.
- Daniel M. Kane An
Elementary
Derivation of the Asymptotics of Partition Functions
The
Ramanujan Journal, Vol. 11 no.
1(2006) pp. 49-66.
- Daniel M. Kane On
the Number of Ways of
Writing t as a Product of Factorials Integers:
Electronic Journal of
Combinatorial Number Theory, Vol. 5 (2005),
#A02, pp. 1-10.
- Daniel M. Kane Resolution
of a
Conjecture Involving Cranks of Partitions of Andrews
and Lewis Proceedings
of the American Mathematical Society, Vol. 132
No. 8(2004), pp. 2247-2256.
-
Daniel M. Kane New
Bounds on the
Number of Representations of t as a Binomial
Coefficient Integers:
Electronic Journal of
Combinatorial Number Theory, Vol. 4 (2004),
#A07, pp. 1-10.
- Semitoric Manifolds:
- COMAP MCM Papers:
- Dan Gulotta, Daniel M. Kane, Andrew Spann Electoral
Redistricting with
Moment of Inertia and Diminishing Halves Models(3.81
MB) UMAP Journal,
Vol. 28 (2007), pp.
281-299.
- Dan Gulotta, Daniel M. Kane, Andrew Spann Application
of Min-Cost Flow
to Airline Accessibility Services UMAP
Journal, Vol. 27 (2006), pp.
367-385.
- Dan Gulotta, Daniel M. Kane, Andrew Spann Lane
Changes and Close
Following: Troublesome Tollbooth Traffic(6
MB) UMAP
Journal, Vol. 26 no. 3 (2005) pp. 251-264.
- Other Mathematics
- Ery Arias-Castro, Clement Berenfeld, Daniel Kane Theoretical
Foundations of Ordinal Multidimensional Scaling,
Including Internal and External Unfolding, in
preparation.
- Daniel M. Kane, Scott Duke Kominers Prisoners,
Rooms, and Lightswitches, Electronic Journal
of Combinatorics, Vol 28 (1), 2021 pp. 1-27.
- Daniel M. Kane Small
Designs for Path
Connected Spaces and Path Connected Homogeneous Spaces,
Transactions of
the AMS, Vol. 367
(2015), pp. 6387-6414.
- Daniel M. Kane Canonical
Projective
Embeddings of the Deligne-Lusztig Curves Associated to
2A2,
2B2 and 2G2,
International
Mathematics Research Notices,
(2015) pp. 1158-1189.
- Bobbie Chern, Persi Diaconis, Daniel M. Kane,
Robert C. Rhoades Central
Limit
Theorems for Some Set Partition Statistics, Advances in Applied Mathematics, Vol.
70 (2015), pp. 92–105.
- Bobbie Chern, Persi Diaconis, Daniel M. Kane,
Robert C. Rhoades Closed
Expressions
for Averages of Set Partition Statistics, Research in the Mathematical Sciences,
Vol. 1 (2014) no. 2.
- Chris Dodd, Phakawa Jeasakul, Anne
Jirapattanakul, Daniel M. Kane, Becky Robinson, Noah
Stein, Cesar E. Silva Ergodic
Properties of a Class
of Discrete Abelian Group Extensions of Rank-One
Transformations, Colloquium
Mathematicum, 119 (2010), pp.
1-22.
- Daniel M. Kane On
Solving Games
Constructed Using Both Shortened and Continued
Conjunctive Sums, Integers:
Electronic Journal of
Combinatorial Number Theory, 10 (2010), pp.
849-878.
- Daniel M. Kane A
Partition of the Positive Reals into Algebraically
Closed Subsets,
unpublished.
- Daniel
M. Kane Weak
Mixing of a
Transformation Similar to Pascal, Colloquium
Mathematicum,
Vol. 108 no. 1(2007), pp. 135-140.
Coauthors: Tim
Abbott, Ery
Arias-Castro, Daniel
Beaglehole, Mihir
Bellare, Clement Berenfeld, Manjul
Bhargava,
Eric Blais, Olivier
Bousquet, Michael
A. Burr, Clement Canonne,
Timothy M. Chan,
Xue Chen, Chung-Kuan
Cheng, Yu Cheng,
Yuqian Cheng, Bobbie Chern,
Jeffery Cohen, Yuval
Dagan, Erik
Demaine,
Martin
Demaine, Ilias
Diakonikolas, Chris Dodd, Noam Elkies,
Andreas Fackler, Bakir Farhi, Dan Feldman, Yuval Filmus,
Adam Gągol, Venkata
Gandikota, Rong
Ge, Surbhi
Goel, Themis
Gouleakis, Ron
Graham,
Andrew Granville,
Parikshit Gopalan, Ben Green,
Dan Gulotta,
Shivam Gupta, Max
Hopkins, Samuel
B. Hopkins, John Hugg, John
Iacono, Russell
Impagliazzo, Joseph Jaeger, Phakawa Jeasakul,
He Jia, Anne Jirapattanakul, Gautam Kamath, Ilgweon
Kang, Valentine
Kabanets, Jonathan
Kane, Ilgweon Kang, Sushrut
Karmalkar, Zev Klagsbrun, Adam Klivans,
Scott Kominers, Daniel
Kongsgaard, Vasileios
Kontonis, Pravesh
Kothari, Dimitris
Koukoulopoulos, Samuel A. Kutin,
Setfan Langerman, Rex Lei, Robert
Lemke Oliver, Hendrik
W.
Lenstra Jr., Jerry
Li, Sihan Liu, Roi Livni, Shachar
Lovett, Zhenjian
Lu, Yuetian
Luo, Alaa Maalouf, Gaurav
Mahajan, Pasin
Manurangsi, Raj Kumar Maity, Arya Mazumdar,
Kurt Mehlhorn,
Raghu Meka, Ankur Moitra, Shay Moran,
Michal
Moshkovitz, Jelani
Nelson, Vladimir
Nikishkin, Ryan O'Donnell, Anthony Ostuni,
Joseph Palmer,
Dongwon Park, Mihai
Pǎtraşcu, John Peebles, Alvaro Pelayo,
Ankit Pensia,
Thanasis Pittas, Bjorn
Poonen, Ely
Porat, Eric
Price, Gregory N. Price, Fang Qiao,
Eynat
Rafalin, Eric
Rains,
Sankeerth
Rao, Lisheng Ren, Robert Rhoades,
Becky Robinson, Phillip
Rogaway, Carlo Sanna, Thomas Sauerwald,
Rocco A. Servedio,
Kathryn Seyboth, Jeffrey
Shallit, Shahed
Sharif, Cesar E.
Silva, Alice
Silverberg, Mahdi
Soltanolkotabi, Zhao
Song, Jessica
Sorrell, Andrew
Spann, Jacob
Steinhardt, Alistair
Stewart, Noah
Stein, Damian Straszak, He Sun, Yuxin
Sun, Csaba
Szepesvári, Li-Yang Tan,
Terence Tao, Kevin Tian, Jack A. Thorne,
Murad Tukan, Christos Tzamos,
Paul Valiant,
Santosh Vempala,
Puqian Wang, Osamu
Watanabe, Gellért
Weisz, Ryan
Williams, David
Woodruff, Kewen Wu,
Hanshen
Xiao, Vincent Yeung, Amir Yehudayoff,
Evangeline Fung
Yu Young, Nikos
Zarifis, Anru
Zhang, Zhicheng Zheng