We study statistical/computational tradeoffs for the following density
estimation problem: given $k$ distributions $v_1, \ldots, v_k$ over a discrete
domain of size $n$, and sampling access to a distribution $p$, identify $v_i$
that is "close" to $p$. Our main result is the first data structure that, given
a sublinear (in $n$) number of samples from $p$, identifies $v_i$ in time
sublinear in $k$. We also give an improved version of the algorithm of Acharya
et al. (2018) that reports $v_i$ in time linear in $k$. The experimental
evaluation of the latter algorithm shows that it achieves a significant
reduction in the number of operations needed to achieve a given accuracy
compared to prior work.

本文研究了统计 / 计算权衡的密度估计问题，提出了一种对给定分布数据进行处理的方法，并证明了该方法在时间和样本数量方面都具有非常良好的性能。

密度估计的数据结构

Data Structures for Density Estimation

In this paper we describe an approach to finding the shortest reset word of a
finite synchronizing automaton by using a SAT solver. We use this approach to
perform an experimental study of the length of the shortest reset word of a
finite synchronizing automaton. The largest automata we considered had 100
states. The results of the experiments allow us to formulate a hypothesis that
the length of the shortest reset word of a random finite automaton with $n$
states and 2 input letters with high probability is sublinear with respect to
$n$ and can be estimated as $1.95 n^{0.55}.$

使用 SAT 求解器来寻找有限同步自动机的最短重置词的方法进行描述，并对最短重置词的长度进行了实验研究。根据实验结果，提出一个假设：在具有高概率的 n 个状态和 2 个输入字母的随机有限自动机中，最短重置词的长度相对于 n 是次线性的，并且可以估计为 1.95n 的 0.55 次方。