检索结果-内蒙古大学图书馆

55th annual acm symposium on Theory of Computing, STOC 2023

ISBN: (纸本)9781450399135

The proceedings contain 155 papers. The topics discussed include: almost Chor-Goldreich sources and adversarial random walks;a new Berry-Esseen Theorem for expander walks;near-optimal derandomization of medium-width branching programs;approximating iterated multiplication of stochastic matrices in small space;when Arthur has neither random coins nor time to spare: superfast derandomization of proof systems;exact phase transitions for stochastic block models and reconstruction on trees;parallel discrete sampling via continuous walks;sampling from convex sets with a cold start using multiscale decompositions;on regularity lemma and barriers in streaming and dynamic matching;optimal eigenvalue approximation via sketching;(noisy) gap cycle counting strikes back: random order streaming lower bounds for connected components and beyond;chaining, group leverage score overestimates, and fast spectral hypergraph sparsification;locally consistent decomposition of strings with applications to edit distance sketching;and sublinear time algorithms and complexity of approximate maximum matching.

关键词：

来源：评论

学校读者我要写书评

暂无评论

SPAA'21 panel paper: Architecture-friendly algorithms versus algorithm-friendly architectures 21

SPAA'21 panel paper: Architecture-friendly algorithms versus...

引用

33rd acm symposium on parallelism in algorithms and architectures, SPAA 2021

作者： Blelloch, Guy Dally, William Martonosi, Margraret Vishkin, Uzi Yelick, Katherine Carnegie Mellon University Pittsburgh United States NVIDIA Santa Clara United States Pricneton University Princeton United States College Park United States University of California Berkeley Electrical Engineering and Computer Sciences Berkeley United States

The current paper provides preliminary statements of the panelists ahead of a panel discussion at the acm SPAA 2021 conference on the topic: algorithm-friendly architecture versus architecture-friendly algorithms. ... 详细信息

ISBN: (纸本)9781450380706

关键词： parallel architectures

来源：评论

学校读者我要写书评

暂无评论

parallel Minimum Cuts in Near-linear Work and Low Depth

引用

acm TRANSACTIONS ON parallel COMPUTING 2021年第2期8卷 1–20页

作者： Geissmann, Barbara Gianinazzi, Lukas Swiss Fed Inst Technol Dept Comp Sci Univ Str 6 CAB Zurich Switzerland

We present the first near-linear work and poly-logarithmic depth algorithm for computing a minimum cut in an undirected graph. Previous parallel algorithms with poly-logarithmic depth required at least quadratic work in the number of vertices. In a graph with n vertices and m edges, our randomized algorithm computes the minimum cut with high probability in O(m log(4) n) work and O(log(3) n) depth. This result is obtained by parallelizing a data structure that aggregates weights along paths in a tree, in addition exploiting the connection between minimum cuts and approximate maximum packings of spanning trees. In addition, our algorithm improves upon bounds on the number of cache misses incurred to compute a minimum cut.

关键词： Minimum cut graph algorithms minimum path data structure parallel algorithms cache-oblivious algorithms

来源：评论

学校读者我要写书评

暂无评论

Poster: Dynamic and NM1-Right Selection for the parallel Iterative Improvement Stable Matching Algorithm 23

Poster: Dynamic and NM1-Right Selection for the Parallel Ite...

引用

2023 International symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing, MobiHoc 2023

作者： Kyritsis, Alec Wynn, Scott Alberi, Stephora Cesar Lu, Enyue Middlebury College United States University of Washington Seattle United States Salisbury University United States

ISBN: (纸本)9781450399265

Sequential algorithms for the Stable Matching Problem are often too slow in the context of some large scale applications like switch scheduling. parallel architectures can offer a notable reduction in complexity. We propose a stable matching algorithm using n2 processors that converges in O(nlog(n)) average runtime. The algorithm is structurally based on the parallel Iterative Improvement (PII) Algorithm [3], which successfully finds a stable matching in approximately 90% of cases. We suggest an alternative selection method for pairs in the PII algorithm, called Dynamic Selection, leading to an algorithm that fully converges over 200,000 trials and generally converges much faster. We also suggest the Right-Minimum selection method, leading to an algorithm which converges in approximately 99.9% of cases and can be combined with the PII-SC algorithm's cycle detection and Gale-Shapley Initiation to remove all cycles observed thus far. © 2023 Owner/Author(s).

关键词： parallel architectures

来源：评论

学校读者我要写书评

暂无评论

Brief announcement: parallel network mapping algorithms 33

Brief announcement: Parallel network mapping algorithms

引用

33rd acm symposium on parallelism in algorithms and architectures, SPAA 2021

作者： Afshar, Ramtin Goodrich, Michael T. Matias, Pedro Osegueda, Martha C. University of California IrvineCA United States

ISBN: (纸本)9781450380706

Motivated from parallel network mapping, we provide efficient query complexity and round complexity bounds for graph reconstruction using distance queries, including a bound that improves a previous sequential complexity bound. Our methods use a high-probability parametric parallelization of a graph clustering technique of Thorup and Zwick, which may be of independent interest. © 2021 Owner/Author.

关键词： Complex networks

来源：评论

学校读者我要写书评

暂无评论

Nearly Optimal Vertex Fault-Tolerant Spanners in Optimal Time: Sequential, Distributed, and parallel 2022

Nearly Optimal Vertex Fault-Tolerant Spanners in Optimal Tim...

引用

54th annual acm SIGACT symposium on Theory of Computing (STOC)

作者： Parter, Merav Weizmann Inst Sci Rehovot Israel

ISBN: (纸本)9781450392648

We (nearly) settle the time complexity for computing vertex faulttolerant (VFT) spanners with optimal sparsity (up to polylogarithmic factors). VFT spanners are sparse subgraphs that preserve distance information, up to a small multiplicative stretch, in the presence of vertex failures. These structures were introduced by [Chechik et al., STOC 2009] and have received a lot of attention since then. Recent work provided algorithms for computing VFT spanners with optimal sparsity but in exponential runtime. The first polynomial time algorithms for these structures have been given by [Bodwin, Dinitz and Robelle, SODA 2021]. Their algorithms, as all other prior algorithms, are greedy and thus inherently sequential. We provide algorithms for computing nearly optimal.. -VFT spanners for any n-vertex n-edge graph, with near optimal running time in several computational models: (i) A randomized sequential algorithm with a runtime of e.. (..) (i.e., independent in the number of faults..). The state-of-the-art time bound is e.. (.. 1-1/.. center dot..2+1/.. +.. 2..) by [Bodwin, Dinitz and Robelle, SODA 2021]. (ii) A distributed congest algorithm of e.. ( 1) rounds. Improving upon [Dinitz and Robelle, PODC 2020] that obtained FT spanners with near-optimal sparsity in e.. (.. 2) rounds. (iii) A PRAM (CRCW) algorithm with e.. (..) work and e.. (1) depth. Prior bounds implied by [Dinitz and Krauthgamer, PODC 2011] obtained sub-optimal FT spanners using e.. (.. 3..) work and e.. (.. 3) depth. An immediate corollary provides the first nearly-optimal PRAM algorithm for computing nearly optimal..-vertex connectivity certificates using polylogarithmic depth and near-linear work. This improves the state-of-the-art bounds of e.. (1) depth and.. (....) work, by [Karger and Motwani, STOC'93].

关键词： Spanners Connectivity Certificate Fault-Tolerance

来源：评论

学校读者我要写书评

暂无评论

SPAA 2021 - Proceedings of the 33rd acm symposium on parallelism in algorithms and architectures

SPAA 2021 - Proceedings of the 33rd ACM Symposium on Paralle...

引用

33rd acm symposium on parallelism in algorithms and architectures, SPAA 2021

ISBN: (纸本)9781450380706

The proceedings contain 49 papers. The topics discussed include: fast stencil computations using fast Fourier transforms;low-span parallel algorithms for the binary-forking model;provable advantages for graph algorithms in spiking neural networks;algorithms for right-sizing heterogeneous data centers;efficient parallel self-adjusting computation;speed scaling with explorable uncertainty;efficient online weighted multi-level paging;paging and the address-translation problem;massively parallel algorithms for distance approximation and spanners;efficient load-balancing through distributed token dropping;finding subgraphs in highly dynamic networks;near-optimal time-energy trade-offs for deterministic leader election;and efficient stepping algorithms and implementations for parallel shortest paths.

关键词：

来源：评论

学校读者我要写书评

暂无评论

parallel Repetition for All 3-Player Games over Binary Alphabet 2022

Parallel Repetition for All 3-Player Games over Binary Alpha...

引用

54th annual acm SIGACT symposium on Theory of Computing (STOC)

作者： Girish, Uma Holmgren, Justin Mittal, Kunal Raz, Ran Zhan, Wei Princeton Univ Princeton NJ 08544 USA NTT Res Palo Alto CA USA

We prove that for every 3-player (3-prover) game, with binary questions and answers and value 0, such that the value of the n-fold parallel repetition of the game is at most n(-c). Along the way to proving this theor... 详细信息

ISBN: (纸本)9781450392648

We prove that for every 3-player (3-prover) game, with binary questions and answers and value < 1, the value of the.. -fold parallel repetition of the game decays polynomially fast to 0. That is, for every such game, there exists a constant c > 0, such that the value of the n-fold parallel repetition of the game is at most n(-c). Along the way to proving this theorem, we prove two additional parallel repetition theorems for multiplayer (multiprover) games, that may be of independent interest: Playerwise Connected Games (with any number of players and any Alphabet size): We identify a large class of multiplayer games and prove that for every game with value < 1 in that class, the value of the n-fold parallel repetition of the game decays polynomially fast to 0. More precisely, our result applies for playerwise connected games, with any number of players and any alphabet size: For each player i, we define the graph G(i), whose vertices are the possible questions for that player and two questions x,x ' are connected by an edge if there exists a vector y of questions for all other players, such that both (x, y) and (x ' , y) are asked by the referee with non-zero probability. We say that the game is playerwise connected if for every i, the graphG(i) is connected. Our class of playerwise connected games is strictly larger than the class of connected games that was defined by Dinur, Harsha, Venkat and Yuen (ITCS 2017) and for which they proved exponential decay bounds on the value of parallel repetition. For playerwise connected games that are not connected, only inverse Ackermann decay bounds were previously known (Verbitsky 1996). Exponential Bounds for the Anti-Correlation Game: In the 3-player anti-correlation game, two out of three players are given 1 as input, and the remaining player is given 0. The two players whowere given 1 must produce different outputs in {0, 1}. We prove that the value of the n-fold parallel repetition of that game decays exponentially fast t

关键词： parallel Repetition Multiplayer Games

来源：评论

学校读者我要写书评

暂无评论

(1-ϵ)-Approximate Maximum Weighted Matching in poly(1/ϵ, log n) Time in the Distributed and parallel Settings 23

(1-ϵ)-Approximate Maximum Weighted Matching in poly(1/ϵ, l...

引用

42nd acm SIGACT-SIGOPS symposium on Principles of Distributed Computing, PODC 2023

作者： Huang, Shang-En Su, Hsin-Hao Boston College Chestnut HillMA United States

ISBN: (纸本)9798400701214

The maximum weighted matching (mwm) problem is one of the most well-studied combinatorial optimization problems in distributed graph algorithms. Despite a long development on the problem, and the recent progress of Fischer, Mitrovic, and Uitto [16] who gave a poly(1/ϵ, log n)-round algorithm for obtaining a (1 - ϵ)-approximate solution for unweighted maximum matching, it had been an open problem whether a (1 - ϵ)-approximate mwm can be obtained in poly(1/ϵ, log n) rounds in the CONGEST model. algorithms with such running times were only known for special graph classes such as bipartite graphs [1] and minor-free graphs [8]. For general graphs, the previously known algorithms require exponential in (1/ϵ) rounds for obtaining a (1 - ϵ)-approximate solution [13] or achieve an approximation factor of at most 2/3 [1]. In this work, we settle this open problem by giving a deterministic poly(1/ϵ, log n)-round algorithm for computing a (1 - ϵ)-approximate mwm for general graphs in the CONGEST model. Our proposed solution extends the algorithm of Fischer, Mitrovic, and Uitto [16], blends in the sequential algorithm from Duan and Pettie [11] and the work of Faour, Fuchs, and Kuhn [13]. Interestingly, this solution also implies a CREW PRAM algorithm with poly(1/ϵ, log n) span using only O(m) processors, and a poly(1/ϵ)-passes algorithm in the semi-streaming model. © 2023 Owner/Author(s).

关键词： Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Performance Analysis and Modelling of Concurrent Multi-access Data Structures 22

Performance Analysis and Modelling of Concurrent Multi-acces...

引用

34th acm symposium on parallelism in algorithms and architectures (SPAA)

作者： Rukundo, Adones Atalar, Aras Tsigas, Philippas Chalmers Univ Technol Gothenburg Sweden

ISBN: (纸本)9781450391467

The major impediment to scaling concurrent data structures is memory contention when accessing shared data structure access-points, leading to thread serialisation, hindering parallelism. Aiming to address this challenge, significant amount of work in the literature has proposed multi-access techniques that improve concurrent data structure parallelism. However, there is little work on analysing and modelling the execution behaviour of concurrent multi-access data structures especially in a shared memory setting. In this paper, we analyse and model the general execution behaviour of concurrent multi-access data structures in the shared memory setting. We study and analyse the behaviour of the two popular random access patterns: shared (Remote) and exclusive (Local) access, and the behaviour of the two most commonly used atomic primitives for designing lock-free data structures: Compare and Swap, and, Fetch and Add. We model the concurrent multi-accesses by splitting the thread execution procedure into five logical sessions: i) side-work, ii) access-point search iii) access-point acquisition, iv) access-point data acquisition and v) access-point data operation. We model the acquisition of an access-point, as a system of closed queuing networks with parallel servers, and data acquisition in terms of where the data is located within the memory system. We evaluate our model on a set of concurrent data structure designs including a counter, a stack and a FIFO queue. The evaluation is carried out on two state of the art multi-core processors: Intel Xeon Phi CPU 7290 with 72 physical cores and Intel Xeon E5-2695 with 14 physical cores. Our model is able to predict the throughput performance of the given concurrent data structures with 80% to 100% accuracy on both architectures.

关键词： concurrency data structures locality multi-access semantic relaxation performance modelling parallel programming lock-free parallelism cache multi-core queuing theorem

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：