Towards a theory of smoothed analysis for distributed computing

走向分布式计算的平滑分析理论

• 批准号: 21K17703
• 负责人: シュワルツマン グレゴリー
• 金额: $ 3万
• 依托单位: Japan Advanced Institute of Science and Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Early-Career Scientists
• 财政年份: 2021
• 资助国家: 日本
• 起止时间: 2021-04-01 至 2024-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-21K17703/
• 关键词: Smoothed analysis; Graph algorithms; Distributed computing; Distributed Computing

In the past year I have been working with collaborators in Europe and Israel on considering the smoothed complexity of online algorithms. We have some preliminary results for general covering problems which we want to formalize and submit for publication.I've also published a single author paper in ICLR, a leading machine learning conference. The paper considers the fundamental problem of mini-batch k-means. While the current analysis is worst-case, the analysis draws inspiration from smoothed analysis techniques.

在过去的一年里，我一直在与欧洲和以色列的合作者合作，研究在线算法的平滑复杂性。我们有一些关于一般覆盖问题的初步结果，我们希望将其形式化并提交发表。我还在领先的机器学习会议ICLR上发表了一篇单作者论文。本文研究了小批量k-均值算法的基本问题。虽然目前的分析是最坏的情况下，分析的灵感来自平滑分析技术。

项目成果

Mini-batch k-means terminates within O(d/ε) iterations

• DOI: 10.48550/arxiv.2304.00419
• 发表时间: 2023
• 期刊: ArXiv
• 作者: Gregory Schwartzman

Fully Polynomial-Time Distributed Computation in Low-Treewidth Graphs

低树宽图中的完全多项式时间分布式计算

• DOI: 10.1145/3490148.3538590
• 发表时间: 2022
• 期刊: Proc. of International Symposium on Parallelism in Algorithms and Architectures (SPAA)
• 作者: Izumi Taisuke;Kitamura Naoki;Naruse Takamasa;Schwartzman Gregory
• 通讯作者: Schwartzman Gregory

On the Complexity of Load Balancing in Dynamic Networks

论动态网络中负载均衡的复杂性

• 发表时间: 2021
• 作者: Pruekprasert Sasinee;Eberhart Clovis;Dubut Jeremy;Gregory Schwartzman
• 通讯作者: Gregory Schwartzman

Smoothed analysis of population protocols

群体协议的平滑分析

• 发表时间: 2021
• 作者: Schwartzman Gregory;Sudo Yuichi
• 通讯作者: Sudo Yuichi

Finding Subgraphs in Highly Dynamic Networks.

在高度动态网络中查找子图。

• 发表时间: 2021
• 作者: Yuga Maki;Wenju Mu;Masahiro Shibata;and Masato Tsuru;Gregory schwartzman;Victor I Kolobov
• 通讯作者: Victor I Kolobov