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

ACM Symposium on Principles of Distributed Computing (PODC)

作者： Bankhamer, Gregor Berenbrink, Petra Biermeier, Felix Elsaesser, Robert Hosseinpour, Hamed Kaaser, Dominik Kling, Peter Univ Salzburg Salzburg Austria Univ Hamburg Hamburg Germany TU Hamburg Hamburg Germany

ISBN: (纸本)9781450392624

We consider the plurality consensus problem for population protocols. Here, n anonymous agents start each with one of k opinions. Their goal is to agree on the initially most frequent opinion (the plurality opinion) via random, pairwise interactions. Exact plurality consensus refers to the requirement that the plurality opinion must be identified even if the bias (difference between the most and second most frequent opinion) is only 1. The case of k = 2 opinions is known as the majority problem. Recent breakthroughs led to an always correct, exact majority population protocol that is both time- and space-optimal, needing O(log n) states per agent and, with high probability, O(log n) time [Doty, Eftekhari, Gasieniec, Severson, Uznanski, and Stachowiak;2021]. Meanwhile, results for general plurality consensus are rare and far from optimal. We know that any always correct protocol requires Omega(k(2)) states, while the currently best protocol needs O(k(11)) states [Natale and Ramezani;2019]. For ordered opinions, this can be improved to O(k(6)) [Gasieniec, Hamilton, Martin, Spirakis, and Stachowiak;2016]. We design protocols for plurality consensus that beat the quadratic lower bound by allowing a negligible failure probability. While our protocols might fail, they identify the plurality opinion with high probability even if the bias is 1. Our first protocol achieves this via k - 1 tournaments in time O(k center dot log n) using O(k + log n) states. While it assumes an ordering on the opinions, we remove this restriction in our second protocol, at the cost of a slightly increased time O(k center dot log n + log(2) n). By efficiently pruning insignificant opinions, our final protocol reduces the number of tournaments at the cost of a slightly increased state complexity O(k center dot log log n + log n). This improves the time to O(n/x(max) center dot log n + log(2) n), where x(max) is the initial size of the plurality. Note that n/x(max) is at most k and can be much sma

关键词： population protocols plurality consensus randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Two-Way Linear Probing Revisited

引用

algorithms 2023年第11期16卷 500-500页

作者： Dalal, Ketan Devroye, Luc Malalla, Ebrahim McGill Univ Sch Comp Sci Montreal PQ H3A 2K6 Canada Ahlia Univ Dept Math Sci POB 10878 Manama Bahrain

Linear probing continues to be one of the best practical hashing algorithms due to its good average performance, efficiency, and simplicity of implementation. However, the worst-case performance of linear probing seems to degrade with high load factors due to a primary-clustering tendency of one collision to cause more nearby collisions. It is known that the maximum cluster size produced by linear probing, and hence the length of the longest probe sequence needed to insert or search for a key in a hash table of size n, is omega(logn), in probability. In this article, we introduce linear probing hashing schemes that employ two linear probe sequences to find empty cells for the keys. Our results show that two-way linear probing is a promising alternative to linear probing for hash tables. We show that two-way linear probing has an asymptotically almost surely O(loglogn) maximum cluster size when the load factor is constant. Matching lower bounds on the maximum cluster size produced by any two-way linear probing algorithm are obtained as well. Our analysis is based on a novel approach that uses the multiple-choice paradigm and witness trees.

关键词： open addressing hashing linear probing parking problem worst-case search time two-way chaining multiple-choice paradigm randomized algorithms witness tree probabilistic analysis

来源：评论

学校读者我要写书评

暂无评论

A binomial sum of harmonic numbers

引用

DISCRETE MATHEMATICS 2023年第1期346卷

作者： Mneimneh, Saad CUNY Hunter Coll Dept Comp Sci 695 Pk Ave New York NY 10065 USA

Let n is an element of N = {1, 2, 3, ...} and 0 <= p <= 1. We show that sigma H-n (k=0)k((n)(k))p(k)q(n-k )= sigma(n)(i=1)1-qi/iwhere H-k = sigma(k)(i=1) 1/i is the kth harmonic number and q =1 - p. This generalizes a previously known identity for the special case of p = 1/2. We derive several forms related to this sum and show how they can be useful in the probabilistic analysis of some simple variants of existing problems. (c) 2022 Elsevier B.V. All rights reserved.

关键词： Harmonic numbers Binomial random variables Binomial coefficients and sums Expectations Probabilistic analysis randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Measuring the Algorithmic Convergence of randomized Ensembles: The Regression Setting

引用

SIAM JOURNAL ON MATHEMATICS OF DATA SCIENCE 2020年第4期2卷 921-943页

作者： Lopes, Miles E. Wu, Suofei Lee, Thomas C. M. Univ Calif Davis Dept Stat Davis CA 95616 USA

When randomized ensemble methods such as bagging and random forests are implemented, a basic question arises: Is the ensemble large enough? In particular, the practitioner desires a rigorous guarantee that a given ensemble will perform nearly as well as an ideal infinite ensemble (trained on the same data). The purpose of the current paper is to develop a bootstrap method for solving this problem in the context of regression-which complements our companion paper in the context of classification [Lopes, Ann. Statist., 47 (2019), 1088-1112]. In contrast to the classification setting, the current paper shows that theoretical guarantees for the proposed bootstrap can be established under much weaker assumptions. In addition, we illustrate the flexibility of the method by showing how it can be adapted to measure algorithmic convergence for variable selection. Lastly, we provide numerical results demonstrating that the method works well in a range of situations.

关键词： bagging bootstrap randomized algorithms random forests

来源：评论

学校读者我要写书评

暂无评论

Randomization of approximate bilinear computation for matrix multiplication

引用

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS- COMPUTER SYSTEMS THEORY 2021年第1期6卷 54-93页

作者： Malik, Osman Asif Becker, Stephen Univ Colorado Boulder Dept Appl Math Boulder CO USA

We present a method for randomizing formulas for bilinear computation of matrix products which does not increase the leading order complexity of the computation. We consider the implications of such randomization when there are two sources of error. The first source is due to the computation formula itself only being approximately correct. Such formulas come up when numerically searching for faster matrix multiplication algorithms. The second source is due to using floating point arithmetic. This kind of error is especially important when computing on low precision hardware like GPUs. Our theoretical results and numerical experiments indicate that our method can improve performance when the two kinds of error are present individually, as well as when they are present at the same time.

关键词： randomized algorithms approximate algorithms matrix multiplication Strassen's algorithm

来源：评论

学校读者我要写书评

暂无评论

Modern Analysis of Hutchinson's Trace Estimator 55

Modern Analysis of Hutchinson's Trace Estimator

引用

55th Annual Conference on Information Sciences and Systems (CISS)

作者： Skorski, Maciej Univ Luxembourg Esch Sur Alzette Luxembourg

ISBN: (纸本)9781665412681

The paper establishes the new state-of-art in the accuracy analysis of Hutchinson's estimator for the matrix trace. Leveraging tools that have not been previously used in this context, particularly hypercontractive inequalities and results on concentration of sub-gamma distributions, we offer an elegant and modular analysis, as well as numerically superior bounds. Besides the improvements, this work aims to better popularize the aforementioned techniques within the CS community.

关键词： randomized algorithms Trace estimation Hutchinson's estimator Monte Carlo methods Hypercontractive inequalities Sub-gamma distributions

来源：评论

学校读者我要写书评

暂无评论

Convergence Analysis of Weighted SPSA-based Consensus Algorithm in Distributed Parameter Estimation Problem 19

Convergence Analysis of Weighted SPSA-based Consensus Algori...

引用

19th IFAC Symposium on System Identification (SYSID)

作者： Sergeenko, Anna Erofeeva, Victoria Granichin, Oleg Granichina, Olga Proskurnikov, Anton St Petersburg State Univ Fac Math & Mech Res Lab Anal & Modeling Social Proc St Petersburg Russia Russian Acad Sci Inst Problems Mech Engn St Petersburg Russia Skolkovo Inst Sci & Technol Moscow Russia Herzen State Pedag Univ Russia St Petersburg Russia Politecn Torino Turin Italy

In this paper, we study a distributed parameter estimation problem in a large-scale network of communication sensors. The goal of the sensors is to find a global estimate of an unknown parameter minimizing, which minimizes some aggregate cost function. Each sensor can communicated to a few "neighbors", furthermore, the communication channels have limited capacities. To solve the resulting optimization problem, we use a weighted modification of the distributed consensus-based SPSA algorithm whose main advantage over the alternative method is its ability to work in presence of arbitrary unknown-but-bounded noises whose statistical characteristics can be unknown. We provide a convergence analysis of the weighted SPSA-based consensus algorithm and show its efficiency via numerical simulations. Copyright (C) 2021 The Authors.

关键词： Sensor network randomized algorithms consensus distributed parameter estimation

来源：评论

学校读者我要写书评

暂无评论

Towards a Theory of randomized Shared Memory algorithms 19

Towards a Theory of Randomized Shared Memory Algorithms

引用

38th ACM Symposium on Principles of Distributed Computing (PODC)

作者： Woelfel, Philipp Univ Calgary Calgary AB Canada

ISBN: (纸本)9781450362177

Randomization has become an invaluable tool to overcome some of the problems associated with asynchrony and faultiness. Allowing processors to use random bits helps to break symmetry, and to reduce the likelihood of undesirable schedules. As a consequence, randomized techniques can lead to simpler and more efficient algorithms, and sometimes to solutions of otherwise unsolvable computational problems. However, the design and the analysis of randomized shared memory algorithms remains challenging. This talk will give an overview of recent progress towards developing a theory of randomized shared memory algorithms. For many years, linearizability [6] has been the gold standard of distributed correctness conditions, and the corner stone of modular programming. In deterministic algorithms, implemented linearizable methods can be assumed to be atomic. But when processes can make random choices, the situation is not the same: Probability distributions of outcomes of algorithms using linearizable methods may be very different from those using equivalent atomic operations [4]. In general, modular algorithm design is much more difficult for randomized algorithms than for deterministic ones. The first part of the talk will present a correctness condition [2, 5] that is suitable for randomized algorithms in certain settings, and will explain why in other settings no such correctness condition exists [3] and what we can do about that. To this date, almost all randomized shared memory algorithms are Las Vegas, meaning they permit no error. Monte Carlo algorithms, which allow errors to occur with small probability, have been studied thoroughly for sequential systems. But in the shared memory world such algorithms have been neglected. The second part of this talk will discuss recent attempts to devise Monte Carlo algorithms for fundamental shared memory problems (e.g., [1]). It will also present some general techniques, that have proved useful in the design of concurrent randomize

关键词： randomized algorithms shared memory concurrency strong linearizability correctness condition mutual exclusion Monte Carlo

来源：评论

学校读者我要写书评

暂无评论

A randomized approach to sensor placement with observability assurance

引用

AUTOMATICA 2021年 123卷 109340-109340页

作者： Bopardikar, Shaunak D. Michigan State Univ Dept Elect & Comp Engn E Lansing MI 48824 USA

Given a linear dynamical system, we provide a probabilistic treatment to the classic problem of placing sensors in a set of candidate locations such that the observability Gramian of the resulting placement is sufficiently non-singular. Our contributions are as follows: First, we present a randomized algorithm that samples the sensor locations with replacement as per a specified distribution. Second, we derive a high probability bound on two measures of non-singularity, viz. the minimum eigenvalue and the trace of the inverse of the observability Gramian of the resulting placement, relative to that of placing one sensor at every location. Our analysis yields upper and lower bounds on any eigenvalue-based metric used in sensor placement and characterizes the tradeoff between the number of samples required by the algorithm and the two measures of the observability Gramian. We supplement the claims with insightful numerical studies and comparisons with multiple competing approaches. (c) 2020 Elsevier Ltd. All rights reserved.

关键词： Sensor placement randomized algorithms Observability Gramian

来源：评论

学校读者我要写书评

暂无评论

Simple Multi-Pass Streaming algorithms for Skyline Points and Extreme Points 38

Simple Multi-Pass Streaming Algorithms for Skyline Points an...

引用

38th International Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Chan, Timothy M. Rahul, Saladi Univ Illinois Dept Comp Sci Urbana IL 61801 USA Indian Inst Sci Bangalore Dept Comp Sci & Automat Bangalore Karnataka India

ISBN: (纸本)9783959771801

In this paper, we present simple randomized multi-pass streaming algorithms for fundamental computational geometry problems of finding the skyline (maximal) points and the extreme points of the convex hull. For the skyline problem, one of our algorithm occupies O(h) space and performs O(log n) passes, where h is the number of skyline points. This improves the space bound of the currently best known result by Das Sarma, Lall, Nanongkai, and Xu [VLDB'09] by a logarithmic factor. For the extreme points problem, we present the first non-trivial result for any constant dimension greater than two: an O( h log(O(1)) n) space and O(log(d) n) pass algorithm, where h is the number of extreme points. Finally, we argue why randomization seems unavoidable for these problems, by proving lower bounds on the performance of deterministic algorithms for a related problem of finding maximal elements in a poset.

关键词： multi-pass streaming algorithms skyline convex hull extreme points randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：