A
lot of my work is fairly technical and often somewhat obscure. For
people trying to get an idea of what my research is like, here are some
easier to understand and more introductory papers to help give an idea
of the kinds of things that I do. These topics are roughly sorted in
decreasing order of how much time I have spent on them recently, so the
topics that I am most likely to have current projects related to are the
ones closest to the top.
Information-Computation Tradeoffs
A topic that has become more prominent in my work recently is the
study of information-computation tradeoffs in computational statistics.
That is cases where the optimal statistical guarantees seem not to be
possible to achieve in an algorithmically efficient manner. A good
starting point is the 2017 paper on various statistical query lower
bounds for what are known as Non-Gaussian Component Analysis problems.
These were later extended (using somewhat more advanced techniques) to
lower bounds against PTF tests. I've also included a nice paper about
lower bounds for a particular framework for reinforcement learning.
- 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.
- 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, Sihan Liu,
Thanasis Pittas PTF
Testing Lower Bounds for Non-Gaussian Component
Analysis, Foundations Of Computer Science
(FOCS), 2025.
Semi-Random Noise Models:
Another recent topic of mine has been that of learning with
semi-random noise. These are some noise models that sit between the
fully random noise models where the noise exactly fits some known model
with a small number of parameters, and the fully adversarial models
where the noise can be arbitrary (if small). A lot of this work is
fairly technical and a bit disconnected, but my paper on boosting in the
presence of Massart noise should be fairly accessible. Another
interesting model is that of entangled mean estimation (where samples
come from distributions with the same mean but perhaps wildly different
covariances) on which I have a nice recent paper.
Robust Statistics:
Perhaps my biggest impact has been in the area the area
of robust statistics.
The basic idea is that one wants to answer basic statistical questions
even if a small fraction of your samples have been adversarially
corrupted. It turns out that while the information-theoretic aspects of
this problem have been well understood for decades, finding
computationally efficient algorithms with non-trivial guarantees is
somewhat more difficult. The first modern algorithms for this kind of
problem appeared around 2016, and there has been a flurry of work since
then to flesh out these ideas. A good place to start on this topic would
be the survey that I wrote with Ilias Diakonikolas on the topic. If you
are interested in further information on the subject, you might want to
check out the recent book that we wrote on the topic. While this area
has been a bit less active recently as the major problems have mostly
been solved, there are still some problems off the beaten path, like
this paper on coordinate-wise corruptions for linear regression.
Distribution Testing:
Another area of research for me has been distribution property
testing. In distribution testing, one has a distribution (or perhaps a
few distributions) and by taking samples wants to distinguish between
the distribution having some property P or being far (usually in total
variational distance) from any distribution with that property. To get a
feel for the techniques in this area, a good starting point would be
the "New Approach" paper, which gives a clean way of solving many of the
basic problems in the field. A slightly more advanced paper is that on
Ak-testing which provides an important tool for answering questions
about structured one-dimensional distributions.A more recent (and
somewhat more complicated) paper in this area is on so-called replicable
distribution testing.
- Ilias Diakonikolas, Daniel M. Kane, A
New Approach for Testing Properties of Discrete Distributions, Foundations Of Computer Science, (FOCS)
2016.
- Ilias Diakonikolas, Daniel M. Kane, Vladimir Nikishkin, Testing Identity of Structured
Distributions, Symposium On Discrete Algorithms (SODA) 2015.
- Ilias Diakonikolas, Jingyi Gao, Daniel Kane, Sihan
Liu, Christopher Ye Replicable
Distribution Testing, Advances in Neural
Information Processing Systems (NeurIPS) 2025
(spotlight presentation).
Polynomial Threshold Functions:
This is an older topic, but was a
major component of my research roughly 2010-2015. These papers roughly
work towards trying to understand the behavior of medium degree
polynomials in high dimensions when evaluated on random inputs. In order
to get at these questions, papers tend to focus on things like noise
sensitivity questions (which the first paper below discusses) and
pseudorandom generators (like the second paper below). The first of
these papers is quite nice and contains some key ideas that proved
useful in later works. The latter paper is somewhat more technical, but
should help the reader get some understanding of what kinds of ideas go
into designing pseudorandom generators.
While there had been a period of little work in this area, there has
been renewed interest in this area in the context of proving lower
bounds for PTF tests. See the paper below on PTF tests for Non-Gaussian
Component Analysis (which is unfortunately, quite technical).
Inference Dimension and Active Learning:
In active learning, one is given a large amount of unlabelled
data cheaply, but then one has to pay in order to learn the labels (or
perform more general queries) on this data. It turns out that for a
number of such problems the query complexity needed to learn the
underlying labeling function is fairly well classified by a quantity
called the inference dimension of the dataset. This is a somewhat niche
topic, but has lead to several quite nice results (though none recently). The obvious place to
start here is the original paper the defines inference dimension.
Other Machine Learning:
I also have a bunch of other more one-off papers on the theoretical
end of machine learning theory. Here are two of the more readable ones.
The first is a technique for showing that realizable learning is enough
(information-theoretically at least) to build more complicated learners
in many contexts. The other gives a technique for proving lower bounds
in the statistical query model, and shows up in a bunch of my other more
recent work.