应用于网络图的向量摘要的核心集
本文提出了一种有效的随机算法来计算图形摘要，旨在最小化重构误差，使用加权采样方案来合并顶点，提供算法运行时间的分析上限和得分计算的近似保证，并在几个真实世界图形上测试了算法以证明摘要的质量和与现有算法的比较，并使用摘要来回答有关原始图形的几个结构查询并报告其准确性。
Jun, 2018
我们研究了在公平性 / 分区约束条件下多样性最大化任务中的一种核心集构建算法。给定一个被划分为 m 组的度量空间中的点集 P，以及给定的每组 i 中的 ki 个点，该问题的目标是从每个组中选择 ki 个点，使得选择的 k 个点的整体多样性最大化。我们考虑了两种自然的多样性度量方法：对点对距离求和和对最近邻距离求和，并展示了针对这些度量方法的改进的核心集构建算法。具体而言，我们展示了第一种相对于点对距离求和而言大小与数据集大小和纵横比无关的核心集，同时我们还展示了第一个相对于最近邻距离求和而言的核心集。最后，我们进行了几个实验证明了我们的核心集方法的有效性。特别是，我们将约束的多样性最大化应用于一个考虑到消息的新旧的定时消息集的总结。具体而言，总结应该包含比较近期的消息而不是较早的消息。这是在一个最大的通信平台中的一个真实任务，每天活跃用户的体验都会受到影响。通过利用我们的核心集方法，我们实现了 100 倍的加速，只损失了少数百分比的多样性。此外，我们的方法还可以改进流式设置中算法的空间利用率。
Oct, 2023
该研究考虑了针对一组正函数的最小化问题，给出了一个压缩表示法（coresets），用于形状拟合（shape fitting）和近似聚类（approxiate clustering）问题。他们将 epsilon-approximations 与 PAC Learning 和 VC dimension 相联系，并给出了一般函数集的 coresets 的线性时间近似计算方法。
Jun, 2011
研究了多维欧氏空间中寻找一个 k 维子空间 F，使得一组 n 个点到该子空间的 p 次方欧氏距离和最小的问题。进一步探讨了在某些损失函数 M ()（如 Huber 和 Tukey 损失函数）下此问题的最优解。这些鲁棒子空间可替代奇异值分解（SVD）提供更有效的解决方案，对于典型的 M-Estimators，对离群值的鲁棒性更强。本文给出了一些这些鲁棒子空间逼近问题的算法和难度结果。
Oct, 2015
本文研究了适用于不同的 lP 范数的近似线性代数问题，提出了一种同时适用于每个 p ≥ 1 的确定性算法，并将其应用于多种问题，如 lP 回归，逐元素 l1 低秩逼近和近似矩阵乘法。
Jul, 2018
本文展示了在至少需要 ω(n^(2/(d+2))) 的节点度时（其中 d 为维度），可以从有向无权图中恢复欧几里得度量和相关密度的估计，其中我们的估计器基于有向图上的随机游走的特征化和相应连续极限。
Nov, 2014
一个可证明近似稀疏大数据 K-means 问题的流式算法及其性能提升结果，应用了一种稀疏的 (k, ε) 子集算法，可在不依赖于数据和维度的情况下，精确地计算每个点到 k 个中心的平方距离之和，从而使得在离线设置下的启发式算法的性能得到了大幅提升。
Nov, 2015
研究估计具有有界平均值和协方差的重尾随机向量均值的算法问题，提供了一种基于谱方法的算法来解决该问题，并且只需要计算近似特征向量，取得了最优的统计性能和更快的运行速度。
Aug, 2019
本文研究如何在分布式计算环境中在通信成本约束下，适应一系列随机化算法以在预期的通信成本和估计误差之间进行权衡，实现对一组向量的平均值估计，为分布式优化和学习算法中的 reduce-all 操作提供了一种解决方案。
Nov, 2016