- MM分布式仿真和分布式推断
研究了一个关于 “simulate-and-infer” 的通信受限问题,在只要求每个参与者发送少于 log k 比特给中央仲裁者的情况下,寻找利用最少的参与者,对未知概率分布进行推断的最优策略,表明了 simulate-and-infer - KDD一种用于非光滑规则化的经验风险最小化的分布式拟牛顿算法
提出了一种使用二阶信息进行通信和计算效率高的分布式优化算法来解决具有非平滑正则化项的 ERM 问题。该算法使用逐步二次逼近法,并描述了如何在分布式方式下有效地维护 Hessian 的逼近并解决子问题。该方法适用于广泛的非强凸问题,具有全局线 - 关于近似支配集的参数化复杂性
论文研究了基于参数的复杂度近似算法,通过建立通信复杂度和近似难度的关系,研究了支撑不同假设下 Label Cover 问题变种的近似难度。
- 扩展器图与通信高效的分散式优化
本文讨论如何设计图形拓扑结构,以减少分散式优化算法的通信复杂度,发现扩展图形是最优选择之一,并提出三种方法以构建不同节点数和节点度数的扩展图形,数值结果显示分散式优化在扩展图形上的性能显著优于其他定期图形。
- MM近似纳什均衡的通信复杂度
针对二人 NxN 游戏的 epsilon-Nash 均衡和 n 人二元动作游戏的 epsilon 弱近似 Nash 均衡,我们证明了通信复杂度的下限是多项式 N 和指数级 n。
- 并行查询处理中的偏斜
研究使用 p 个服务器在大型数据库上并行计算简单查询 q 的通信复杂性,特别关注数据倾斜的情况下的情况,建立了查询的分数边覆盖与通信量之间的紧密联系,并提供了查询分数边覆盖的匹配上界和下界,所有下界都以比特通信量的形式表达。
- 在一般拓扑上进行分布式 k-Means 和 k-Median 聚类
本文提出一种新的分布式 k-median 和 k-means 聚类算法,通过 coresets 的方法,构建全局 coreset,降低了通信复杂度,实验结果表明该算法优于其他 coreset-based 分布式聚类算法。
- 消息传递模型下集合不相交的紧密界限
该研究使用信息复杂度工具及时间复杂度分析,证明在传递消息模型中,Sey Disjointness 问题及任务分配问题在最坏情况下的时间复杂度下界为 n*k。
- 分布式学习,通信复杂度和隐私
讨论分布式数据的 PAC 学习问题,分析了涉及的基本通信复杂性问题,包括教学维度和错误绑定。针对特定概念类别,如合取、奇偶函数和决策列表等,给出上下界限。讨论了如何通过增强来在分布式环境下进行一般性通信,以及如何在不确定环境下实现低通信回归 - MM随机信念传播:一种低复杂度替代乘积和算法的选择
本文提出了一种低复杂度的信念传播算法 —— 随机信念传播(SBP)算法,该算法是一种自适应随机的 BP 信息传递版本,其信息传递减少了计算复杂度和通讯复杂度,并在各种图形模型中证明了收敛性和计算复杂度降低的理论格局。
- Gap-Hamming 距离的通信复杂度的最优下界
本文通过引入高斯空间相关性的几何性质以及概率投影的方法证明了久负盛名的 Gap-Hamming-Distance 问题的随机通信复杂度的最优下界,并由此得出了在数据流模型中多遍通信所需的空间的最优下界。
- 量子指纹识别
本文证明出一种基于量子信息采用指纹技术的方式进行经典指纹,而无需任何相关性或纠缠。其指纹尺寸可以使得指纹大幅度压缩,并针对我们的方案进行优化,进一步提高了方案的效率。此方案表明了一个在通信复杂度的同时传递模型上的指纹相等问题的指数量子 /