About

Daniel Kane is a professor in the Department of Mathematics with a dual appointment in the Department of Computer Science and Engineering. He earned his Ph.D. in Mathematics from Harvard University in 2011, after completing two Bachelor of Science degrees at MIT in 2007, one in mathematics with computer science and the other in physics. Prior to his doctoral studies, Kane was a member of the USA team at the International Mathematical Olympiad, winning gold medals in 2002 and 2003. Kane's research interests encompass a broad range of mathematics and theoretical computer science, with particular focus on number theory, complexity theory, and combinatorics. He has contributed to these fields through various research projects and has been recognized for his work, including receiving the Best Paper award at the Conference on Computational Complexity in 2013. His academic and research background includes a postdoctoral fellowship at Stanford University, supported by an NSF Postdoctoral Research Fellowship, where he was a researcher in the Department of Mathematics.

Research topics

• Computer Science
• Artificial Intelligence
• Mathematics
• Algorithm
• Combinatorics
• Biology
• Economics
• Ecology
• Mathematical economics
• Statistics
• Discrete mathematics

Selected publications

• Challenges and Opportunities: A Systematic Review of AI Tools in Engineering Education

  2025-08-21

  review
  PublisherDOI

• Agnostic Product Mixed State Tomography via Robust Statistics

  arXiv (Cornell University) · 2025-10-09

  preprintOpen access

  We study the complexity of two closely related learning problems, one quantum and one classical. In the quantum setting, we consider agnostic tomography for the natural class of product mixed states. Given $N$ copies of an $n$-qubit state $ρ$, the goal is to output a nearly optimal product mixed state approximation in trace distance. While recent work has focused on pure-state ansatz (e.g., product or stabilizer states), no polynomial-time guarantees were previously known for mixed-state ansatz. In the classical setting, we study robust learning of binary product distributions: given samples from an unknown distribution on ${0,1}^n$, the goal is to output a nearly optimal product approximation. Our main contributions are as follows. (1) We give a semi-agnostic tomography algorithm for product mixed states with polynomial sample and computational complexity achieving error $O(\mathrm{opt}\log(1/\mathrm{opt}))$, where $\mathrm{opt}$ is the trace distance to the best product approximation. This is the first efficient algorithm with any nontrivial agnostic guarantee for mixed-state ansatz, using only single-qubit, single-copy measurements. We also prove a Quantum Statistical Query lower bound showing near-optimality, and an unconditional lower bound demonstrating that adaptivity is necessary under single-qubit measurements. (2) We give a semi-agnostic algorithm for robustly learning binary product distributions with matching guarantees and establish a Statistical Query lower bound, essentially resolving the efficient robust learnability of this class and improving on prior work since Diakonikolas et al. (2016).

  PublisherOA PDFDOI

• Work in Progress: Assessing the Impact of Spatial Skills on Performance in a Statics Course

  2025-08-21

  article
  PublisherDOI

• BOARD # 98: WIP: Understanding Patterns of Generative AI Use: A Study of Student Learning Across University Colleges

  2025-08-21

  article1st authorCorresponding
  PublisherDOI

• Linear Regression under Missing or Corrupted Coordinates

  ArXiv.org · 2025-09-23

  preprintOpen access

  We study multivariate linear regression under Gaussian covariates in two settings, where data may be erased or corrupted by an adversary under a coordinate-wise budget. In the incomplete data setting, an adversary may inspect the dataset and delete entries in up to an $η$-fraction of samples per coordinate; a strong form of the Missing Not At Random model. In the corrupted data setting, the adversary instead replaces values arbitrarily, and the corruption locations are unknown to the learner. Despite substantial work on missing data, linear regression under such adversarial missingness remains poorly understood, even information-theoretically. Unlike the clean setting, where estimation error vanishes with more samples, here the optimal error remains a positive function of the problem parameters. Our main contribution is to characterize this error up to constant factors across essentially the entire parameter range. Specifically, we establish novel information-theoretic lower bounds on the achievable error that match the error of (computationally efficient) algorithms. A key implication is that, perhaps surprisingly, the optimal error in the missing data setting matches that in the corruption setting-so knowing the corruption locations offers no general advantage.

  PublisherOA PDFDOI

• Batch List-Decodable Linear Regression via Higher Moments

  ArXiv.org · 2025-03-12

  preprintOpen access

  We study the task of list-decodable linear regression using batches. A batch is called clean if it consists of i.i.d. samples from an unknown linear regression distribution. For a parameter $α\in (0, 1/2)$, an unknown $α$-fraction of the batches are clean and no assumptions are made on the remaining ones. The goal is to output a small list of vectors at least one of which is close to the true regressor vector in $\ell_2$-norm. [DJKS23] gave an efficient algorithm, under natural distributional assumptions, with the following guarantee. Assuming that the batch size $n$ satisfies $n \geq \tildeΩ(α^{-1})$ and the number of batches is $m = \mathrm{poly}(d, n, 1/α)$, their algorithm runs in polynomial time and outputs a list of $O(1/α^2)$ vectors at least one of which is $\tilde{O}(α^{-1/2}/\sqrt{n})$ close to the target regressor. Here we design a new polynomial time algorithm with significantly stronger guarantees under the assumption that the low-degree moments of the covariates distribution are Sum-of-Squares (SoS) certifiably bounded. Specifically, for any constant $δ>0$, as long as the batch size is $n \geq Ω_δ(α^{-δ})$ and the degree-$Θ(1/δ)$ moments of the covariates are SoS certifiably bounded, our algorithm uses $m = \mathrm{poly}((dn)^{1/δ}, 1/α)$ batches, runs in polynomial-time, and outputs an $O(1/α)$-sized list of vectors one of which is $O(α^{-δ/2}/\sqrt{n})$ close to the target. That is, our algorithm achieves substantially smaller minimum batch size and final error, while achieving the optimal list size. Our approach uses higher-order moment information by carefully combining the SoS paradigm interleaved with an iterative method and a novel list pruning procedure. In the process, we give an SoS proof of the Marcinkiewicz-Zygmund inequality that may be of broader applicability.

  PublisherOA PDFDOI

• Clustering Mixtures of Bounded Covariance Distributions Under Optimal Separation

  Society for Industrial and Applied Mathematics eBooks · 2025-01-01

  book-chapter

  We study the clustering problem for mixtures of bounded covariance distributions, under a fine-grained separation assumption. Specifically, given samples from a k-component mixture distribution where each wi ≤ α for some known parameter α, and each Pi has unknown covariance for some unknown σi, the goal is to cluster the samples assuming a pairwise mean separation in the order of between every pair of components Pi and Pj. Our main contributions are as follows:

  PublisherDOI

• Robust Learning of Multi-index Models via Iterative Subspace Approximation

  ArXiv.org · 2025-02-13

  preprintOpen access

  We study the task of learning Multi-Index Models (MIMs) with label noise under the Gaussian distribution. A $K$-MIM is any function $f$ that only depends on a $K$-dimensional subspace. We focus on well-behaved MIMs with finite ranges that satisfy certain regularity properties. Our main contribution is a general robust learner that is qualitatively optimal in the Statistical Query (SQ) model. Our algorithm iteratively constructs better approximations to the defining subspace by computing low-degree moments conditional on the projection to the subspace computed thus far, and adding directions with relatively large empirical moments. This procedure efficiently finds a subspace $V$ so that $f(\mathbf{x})$ is close to a function of the projection of $\mathbf{x}$ onto $V$. Conversely, for functions for which these conditional moments do not help, we prove an SQ lower bound suggesting that no efficient learner exists. As applications, we provide faster robust learners for the following concept classes: * {\bf Multiclass Linear Classifiers} We give a constant-factor approximate agnostic learner with sample complexity $N = O(d) 2^{\mathrm{poly}(K/ε)}$ and computational complexity $\mathrm{poly}(N ,d)$. This is the first constant-factor agnostic learner for this class whose complexity is a fixed-degree polynomial in $d$. * {\bf Intersections of Halfspaces} We give an approximate agnostic learner for this class achieving 0-1 error $K \tilde{O}(\mathrm{OPT}) + ε$ with sample complexity $N=O(d^2) 2^{\mathrm{poly}(K/ε)}$ and computational complexity $\mathrm{poly}(N ,d)$. This is the first agnostic learner for this class with near-linear error dependence and complexity a fixed-degree polynomial in $d$. Furthermore, we show that in the presence of random classification noise, the complexity of our algorithm scales polynomially with $1/ε$.

  PublisherOA PDFDOI

• Spatial Problem-Solving in the Dark: A Qualitative Study of Sighted Engineering Students’ Spatial Strategies on the Tactile Mental Cutting Test While Blindfolded

  2025-08-21

  article1st authorCorresponding
  PublisherDOI

• Theoretical Foundations of Ordinal Multidimensional Scaling, Including Internal Unfolding and External Unfolding

  SIAM Journal on Mathematics of Data Science · 2025-09-04

  articleOpen accessSenior author
  PublisherDOI

Recent grants

• CAREER: Structure and Analysis of Low Degree Polynomials

  NSF · $500k · 2016–2025

• PostDoctoral Research Fellowship

  NSF · $135k · 2011–2015

Frequent coauthors

• Ilias Diakonikolas

  216 shared

• Alistair Stewart

  83 shared

• Gautam Kamath

  University of Waterloo

  50 shared

• Jerry Li

  Pfizer (United States)

  49 shared

• Ankur Moitra

  IIT@MIT

  48 shared

• Wade Goodridge

  Utah State University

  42 shared

• Natalie Shaheen

  38 shared

• Shachar Lovett

  35 shared

Education

• Mechanical and Aerospace Engineering, Mechanical and Aerospace Engineering

  Utah State University

  2022

Awards & honors

• Best Paper award at the Conference on Computational Complexi…
• Gold Medal at the International Mathematical Olympiad (2002)
• Gold Medal at the International Mathematical Olympiad (2003)