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

29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing

作者： Lenzen, Christoph Wattenhofer, Roger ETH Comp Engn & Networks Lab Zurich Switzerland

ISBN: (纸本)9781605588889

We demonstrate how to leverage a system's capability for all-to-all communication to achieve an exponential speed-up of local algorithms despite bandwidth and memory restrictions. More precisely, if a network comprises n nodes with all-to-all bandwidth n(epsilon) (epsilon > 0 constant) and nodes know their input and neighborhood with respect to a graph problem instance of polylogarithmic maximum degree, any local algorithm for this problem with running time r is an element of O(log n) and reasonably small states can be simulated within O(log r) rounds.

关键词： local algorithms simulation all-to-all communication

来源：评论

学校读者我要写书评

暂无评论

Survey of local algorithms

引用

ACM COMPUTING SURVEYS 2013年第2期45卷 24-24页

作者： Suomela, Jukka Univ Helsinki Helsinki Inst Informat Technol FIN-00014 Helsinki Finland

A local algorithm is a distributed algorithm that runs in constant time, independently of the size of the network. Being highly scalable and fault tolerant, such algorithms are ideal in the operation of large-scale distributed systems. Furthermore, even though the model of local algorithms is very limited, in recent years we have seen many positive results for nontrivial problems. This work surveys the state-of-the-art in the field, covering impossibility results, deterministic local algorithms, randomized local algorithms, and local algorithms for geometric graphs.

关键词： algorithms Theory local algorithms

来源：评论

学校读者我要写书评

暂无评论

ON THE POWER OF RELAXED local DECODING algorithms

引用

SIAM JOURNAL ON COMPUTING 2021年第2期50卷 788-813页

作者： Gur, Tom Lachish, Oded Univ Warwick Coventry W Midlands England Birkbeck Comp Sci & Infromat Syst London WC1E 7HX England

A locally decodable code (LDC) C: {0, 1}(k) -> {0, 1}(n) is an error correcting code wherein individual bits of the message can be recovered by only querying a few bits of a noisy codeword. LDCs found a myriad of applications both in theory and in practice, ranging from probabilistically checkable proofs to distributed storage. However, despite nearly two decades of extensive study, the best known constructions of O(1)-query LDCs have superpolynomial blocklength. The notion of relaxed LDCs is a natural relaxation of LDCs, which aims to bypass the foregoing barrier by requiring local decoding of nearly all individual message bits, yet allowing decoding failure (but not error) on the rest. State of the art constructions of O(1)-query relaxed LDCs achieve blocklength n = O (k(1+gamma)) for an arbitrarily small constant gamma. We prove a lower bound which shows that O(1)-query relaxed LDCs cannot achieve blocklength n = k(1+o(1)). This resolves an open problem raised by Goldreich in 2004.

关键词： locally decodable codes lower bounds local algorithms

来源：评论

学校读者我要写书评

暂无评论

local PCA algorithms

引用

IEEE TRANSACTIONS ON NEURAL NETWORKS 2000年第6期11卷 1242-1250页

作者： Weingessel, A Hornik, K Tech Univ Vienna Inst Stat A-1060 Vienna Austria

Within the last gears various principal component analysis (PCA) algorithms have been proposed. In this paper me use a general framework to describe those PCA algorithms which are based on Hebbian learning. For an important subset of these algorithms, the local algorithms, me fully describe their equilibria, where all lateral connections are set to zero and their local stability. We show how the parameters in the PCA algorithms have to be chosen in order to get an algorithm which converges to a stable equilibrium which pro tides principal component extraction.

关键词： Hebbian learning local algorithms principal component analysis (PCA)

来源：评论

学校读者我要写书评

暂无评论

On local Elimination algorithms for Sparse Discrete Optimization Problems

On Local Elimination Algorithms for Sparse Discrete Optimiza...

引用

4th International Conference on Problems of Cybernetics and Informatics (PCI)

作者： Lemtyuzhnikova, Daria Sviridenko, Aleksandr Shcherbina, Oleg Tavrian Natl Univ Simferopol Ukraine

ISBN: (纸本)9781467345026;9781467345002

We discuss local elimination algorithms that compute global information using local computations. Results of benchmarking show real computational capabilities of block elimination algorithms combined with SYMPHONY solver. Strategies for parallelizing a sequential local elimination algorithm for sparse discrete optimization problems are analyzed. We propose to use hybrid Master-Worker scheme where Worker processors (GPUs) solve concurrently subproblems corresponding to super-nodes of extended elimination tree that are generated by a single master process (CPU).

关键词： discrete optimization decomposition nonserial dynamic programming local algorithms elimination

来源：评论

学校读者我要写书评

暂无评论

Errors are robustly tamed in cumulative knowledge processes

引用

PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA 2025年第5期122卷 e2416866122页

作者： Brandenberger, Anna Marcussen, Cassandra Mossel, Elchanan Sudan, Madhu MIT Dept Math Cambridge MA 02139 USA Harvard Univ Sch Engn & Appl Sci Comp Sci Boston MA 02134 USA

As knowledge accumulates in science and society in a distributed fashion, erroneous derivations can be introduced into the corpus of knowledge. Such derivations can compromise the validity of any units of knowledge that rely on them in the future. Can societal knowledge maintain some level of integrity given simple distributed error- checking mechanisms? In this paper, we investigate the following formulation of the question: assuming that a constant fraction of the new derivations is wrong, is it possible for simple error-checking mechanisms that apply when a new unit of knowledge is derived to maintain the integrity of the corpus of knowledge? This question was introduced by Ben-Eliezer et al. ["Is this correct? Let's check!" in 14th Innovations in Theoretical Computer Science Conference (ITCS, 2023)], who gave a robust affirmative answer in a specific probabilistic model for knowledge accumulation. Namely, this model required that new units depend on just one existing unit and join the process according to a preferential attachment rule. In this work, we consider much more general families of processes of knowledge accumulation, where new units may depend on multiple existing units and join according to varied attachment mechanisms. We also consider models with a (random) fraction of insertions of adversarial nodes. We give a robust affirmative answer to the above question by showing that for all of these models, as long as many of the units follow simple local heuristics for checking a bounded number of units they depend on, all errors will be eventually eliminated.

关键词： knowledge accumulation error elimination local algorithms probabilistic models

来源：评论

学校读者我要写书评

暂无评论

SUBLINEAR algorithms FOR local GRAPH-CENTRALITY ESTIMATION

引用

SIAM JOURNAL ON COMPUTING 2023年第4期52卷 968-1008页

作者： Bressan, Marco Peserico, Enoch Pretto, Luca Univ Milan Dipartimento Informat Via Celoria 18 I-20133 Milan Italy Univ Padua Dipartimento Ingn Informaz Via Gradenigo 6 I-35131 Padua Italy

We study the complexity of local graph-centrality estimation, with the goal of approximating the centrality score of a given target node while exploring only a sublinear number of nodes/arcs of the graph and performing a sublinear number of elementary operations. We develop a technique, which we apply to PageRank and Heat Kernel, for constructing a low-variance score estimator through a local exploration of the graph. We obtain an algorithm that, given any node in any graph of n nodes and m arcs, with probability (1 -delta) computes a multiplicative (1 +/-epsilon)-approximation of its score by examining only O(min(n(1/2)Delta(1/2),n(1/2)m(1/4))) nodes/arcs, where Delta is the maximum outdegree of the graph and poly(epsilon (-1)) and polylog(delta(-1)) factors are omitted for readability. A similar bound holds for computational cost. We also prove a lower bound of Omega (min(n(1/2)Delta(1/2), n(1/3)m(1/3))) for both query complexity and computational complexity. Moreover, in the jump-and-crawl graph -access model, our technique yields a O(min(n(1/2)Delta(1/2), n(2/3)))-queries algorithm;we show that this algorithm is optimal up to a logarithmic factor-in fact, sublogarithmic in the case of PageRank. These are the first algorithms with sublinear worst-case bounds for general directed graphs and any choice of the target node.

关键词： graph centrality sublinear algorithms local algorithms query complexity computational complexity random walks PageRank Heat Kernel

来源：评论

学校读者我要写书评

暂无评论

Engineering Smart Behavior in Evacuation Planning using local Cooperative Path Finding algorithms and Agent-based Simulations 11

Engineering Smart Behavior in Evacuation Planning using Loca...

引用

11th International Joint Conference on Knowledge Discovery, Knowledge Engineering and Knowledge Management (IC3K) / 11th International Conference on Knowledge Engineering and Ontology Development (KEOD)

作者： Selvek, Robert Surynek, Pavel Czech Tech Univ Fac Informat Technol Thakurova 9 Prague 16000 6 Czech Republic

ISBN: (纸本)9789897583827

This paper addresses evacuation problems from the perspective of cooperative path finding (CPF). The evacuation problem we call multi-agent evacuation (MAE) consists of an undirected graph and a set of agents. The task is to move agents from the endangered part of the graph into the safe part as quickly as possible. Although there exist centralized evacuation algorithms based on network flows that are optimal with respect to various objectives, such algorithms would hardly be applicable in practice since real agents will not be able to follow the centrally created plan. Therefore we designed a local evacuation planning algorithm called LC-MAE based on local CPF techniques. Agent-based simulations in multiple real-life scenarios show that LC-MAE produces solutions that are only worse than the optimum by a small factor. Moreover our approach led to important findings about how many agents need to behave rationally to increase the speed of evacuation.

关键词： Evacuation Planning Cooperative Path-finding local algorithms Simulations Real-life Scenarios

来源：评论

学校读者我要写书评

暂无评论

Sublinear algorithms for local Graph Centrality Estimation 59

Sublinear Algorithms for Local Graph Centrality Estimation

引用

59th IEEE Annual Symposium on Foundations of Computer Science (FOCS)

作者： Bressan, Marco Peserico, Enoch Pretto, Luca Sapienza Univ Roma Rome Italy Univ Padua Padua Italy

ISBN: (纸本)9781538642306

We study the complexity of local graph centrality estimation, with the goal of approximating the centrality score of a given target node while exploring only a sublinear number of nodes/arcs of the graph and performing a sublinear number of elementary operations. We develop a technique, that we apply to the PageRank and Heat Kernel centralities, for building a low-variance score estimator through a local exploration of the graph. We obtain an algorithm that, given any node in any graph of m arcs, with probability (1 - delta) computes a multiplicative (1 +/- epsilon)-approximation of its score by examining only (O) over tilde (min(m(2/3)Delta(1/3)d(-2/3), m(4/5) d(-3/5))) nodes/arcs, where Delta and d are respectively the maximum and average outdegree of the graph (omitting for readability poly(epsilon(-1)) and polylog(delta(-1)) factors). A similar bound holds for computational cost. We also prove a lower bound of Omega(min(m(1/2)Delta(1/2)d(-1/2), m(2/3)d(-1/3))) for both query complexity and computational complexity. Moreover, our technique yields a (O) over tilde (n(2/3))-queries algorithm for an n-node graph in the access model of Brautbar et al. [1], widely used in social network mining;we show this algorithm is optimal up to a sublogarithmic factor. These are the first algorithms yielding worst-case sublinear bounds for general directed graphs and any choice of the target node.

关键词： graph centrality sublinear algorithms local algorithms query and computational complexity random walks PageRank heat kernel

来源：评论

学校读者我要写书评

暂无评论

local problems on grids from the perspective of distributed algorithms, finitary factors, and descriptive combinatorics

引用

ADVANCES IN MATHEMATICS 2023年第1期431卷

作者： Grebik, Jan Rozhon, Vaclav Masaryk Univ Fac Informat Botanicka 68A Brno 60200 Czech Republic UCLA Dept Math Los Angeles CA 90095 USA Univ Warwick Coventry Ireland Swiss Fed Inst Technol Zurich Switzerland

We present an intimate connection among the following fields: (a) distributed local algorithms: coming from the area of computer science, (b) finitary factors of iid processes: coming from the area of analysis of randomized processes, (c) descriptive combinatorics: coming from the area of combinatorics and measure theory. In particular, we study locally checkable problems on grids from all three perspectives. Most of our results are for perspective (b) where we prove time hierarchy theorems similar to those known in the field (a) Chang and Pettie (2017) [16]. This approach, which borrows techniques from fields (a) and (c), implies a number of results about the possible complexities of finitary factor solutions. Among others, it answers three open questions of Holroyd et al. (2017) [46] or the more general question of Brandt et al. Brandt (2017) [9] who asked for a formal connection between the fields (a) and (b). In general, we hope that our treatment will help to view all three perspectives as a part of a common theory of locality, in which we follow the insightful paper of Bernshteyn (2023) [6]. & COPY;2023 Elsevier Inc. All rights reserved.

关键词： Descriptive combinatorics local algorithms Finitary factors

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：