Graph Sketching against Adaptive Adversaries Applied to the Minimum Degree Algorithm
Graph Sketching against Adaptive Adversaries Applied to the Minimum Degree Algorithm
复制标题
DOI：
10.1109/focs.2018.00019
复制
发表时间：
2018-04
期刊：
影响因子：
--
通讯作者：
Matthew Fahrbach;G. Miller;Richard Peng;Saurabh Sawlani;Junxing Wang;Shen Chen Xu
中科院分区：
文献类型：
--
作者：
Matthew Fahrbach;G. Miller;Richard Peng;Saurabh Sawlani;Junxing Wang;Shen Chen Xu
出于组合科学计算中矩阵消除排序的研究，我们利用图形素描和局部采样给出了一个数据结构，提供了一个矩阵的近似填充度进行消除在多对数时间每个消除和查询。然后，我们研究的问题，使用这种数据结构的最小程度的算法，这是一个广泛使用的启发式生产稀疏矩阵的消除顺序，通过反复消除顶点（近似）最小填充度。这导致了一个近似的线性时间算法生成近似贪婪的最小度排序。尽管广泛的研究组合科学计算中的消除排序的算法，我们的结果是第一次严格纳入随机化工具在这种情况下，以及第一个近线性时间算法产生消除排序与可证明的近似保证。虽然我们的草图数据结构很容易在不经意的对手模型中工作，但通过重复查询和greenhouse更新自身，它进入了自适应对抗模型，由于其内部随机性的依赖性问题，底层草图变得容易失败。我们将展示如何使用一个额外的采样过程来规避这个问题，并创建一个独立的访问序列。我们的技术去相关交错查询和更新这个随机化的数据结构可能是独立的利益。
Motivated by the study of matrix elimination orderings in combinatorial scientific computing, we utilize graph sketching and local sampling to give a data structure that provides access to approximate fill degrees of a matrix undergoing elimination in polylogarithmic time per elimination and query. We then study the problem of using this data structure in the minimum degree algorithm, which is a widely-used heuristic for producing elimination orderings for sparse matrices by repeatedly eliminating the vertex with (approximate) minimum fill degree. This leads to a nearly-linear time algorithm for generating approximate greedy minimum degree orderings. Despite extensive studies of algorithms for elimination orderings in combinatorial scientific computing, our result is the first rigorous incorporation of randomized tools in this setting, as well as the first nearly-linear time algorithm for producing elimination orderings with provable approximation guarantees. While our sketching data structure readily works in the oblivious adversary model, by repeatedly querying and greedily updating itself, it enters the adaptive adversarial model where the underlying sketches become prone to failure due to dependency issues with their internal randomness. We show how to use an additional sampling procedure to circumvent this problem and to create an independent access sequence. Our technique for decorrelating interleaved queries and updates to this randomized data structure may be of independent interest.