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

OPTIMAL SPEEDUP OF las-vegas algorithms

INFORMATION PROCESSING LETTERS 1993年第4期47卷 173-180页

作者： LUBY, M SINCLAIR, A ZUCKERMAN, D UNIV CALIF BERKELEY BERKELEY CA 94720 USA UNIV EDINBURGH EDINBURGH EH8 9YL MIDLOTHIAN SCOTLAND MIT COMP SCI LAB CAMBRIDGE MA 02139 USA

Let A be a las vegas algorithm, i.e., A is a randomized algorithm that always produces the correct answer when it stops but whose running time is a random variable. We consider the problem of minimizing the expected time required to obtain an answer from A using strategies which simulate A as follows: run A for a fixed amount of time t1, then run A independently for a fixed amount of time t2, etc. The simulation stops if A completes its execution during any of the runs. Let J = (t1, t2, . . .) be a strategy, and let l(A) = inf(J)T(A, J), where T(A, J) is the expected value of the running time of the simulation of A under strategy J. We describe a simple universal strategy J(univ), with the property that, for any algorithm A, T(A, J(univ)) = O(l(A) log(l(A))). Furthermore, we show that this is the best performance that can be achieved, up to a constant factor, by any universal strategy.

关键词： DESIGN OF algorithms RANDOMIZED algorithms las vegas algorithms EXPECTED RUNNING TIME OPTIMAL STRATEGY PROOF SEARCH THEOREM-PROVING

来源：评论

学校读者我要写书评

暂无评论

Monte Carlo and las vegas randomized algorithms for systems and control - An introduction

引用

EUROPEAN JOURNAL OF CONTROL 2007年第2-3期13卷 189-203页

作者： Tempo, Roberto Ishii, Hideaki Politecn Torino CNR IEIIT I-10129 Turin Italy Tokyo Inst Technol Dept Computat Intelligence & Syst Sci Midori Ku Yokohama Kanagawa 2268502 Japan

In this paper, we present an introduction to Monte Carlo and las vegas randomized algorithms for systems and control. Specific applications of these algorithms include stability analysis, Lyapunov functions, and distr... 详细信息

关键词： systems and control probabilistic approach randomized algorithms Monte Carlo algorithms las vegas algorithms

来源：评论

学校读者我要写书评

暂无评论

The Energy Complexity of las vegas Leader Election 22

The Energy Complexity of Las Vegas Leader Election

引用

34th ACM Symposium on Parallelism in algorithms and Architectures (SPAA)

作者： Chang, Yi-Jun Jiang, Shunhua Natl Univ Singapore Singapore Singapore Columbia Univ New York NY USA

ISBN: (纸本)9781450391467

We consider the time (number of communication rounds) and energy (number of non-idle communication rounds per device) complexities of randomized leader election in a multiple-access channel, where the number of devices n >= 2 is unknown. It is well-known that for polynomial-time randomized leader election algorithms with success probability 1 - 1/poly(n), the optimal energy complexity is Theta(log log* n) if receivers can detect collisions, and it is Theta(log* n) otherwise. Without collision detection, all existing randomized leader election algorithms using o(log log n) energy are Monte Carlo in that they might fail with some small probability, and they might consume unbounded energy and never halt when they fail. Although the optimal energy complexity of leader election appears to have been settled, it is still an intriguing open question whether it is possible to attain the optimal O(log* n) energy complexity by an efficient las vegas algorithm that never fails. In this paper we address this fundamental question. center dot A separation between Monte Carlo and las vegas algorithms: Without collision detection, we prove that any las vegas leader election algorithm A with finite expected time complexity must use Omega(log log n) energy, establishing a large separation between Monte Carlo and las vegas algorithms. Our lower bound is tight, matching the energy complexity of an existing leader election algorithm that finishes in O(log n) time and uses O(log log n) energy in expectation. center dot An exponential improvement with sender collision detection: In the setting where transmitters can detect collisions, we design a new leader election algorithm that finishes in O(log(1+epsilon) n) time and uses O(epsilon(-1) log log log n) energy in expectation, showing that sender collision detection helps improve the energy complexity exponentially. Before this work, it was only known that sender collision detection is helpful for deterministic leader election. center dot

关键词： leader election radio network las vegas algorithms

来源：评论

学校读者我要写书评

暂无评论

The shifted number system for fast linear algebra on integer matrices

引用

JOURNAL OF COMPLEXITY 2005年第4期21卷 609-650页

作者： Storjohann, A Univ Waterloo Sch Comp Sci Waterloo ON N2L 3G1 Canada

The shifted number system is presented: a method for detecting and avoiding error producing carries during approximate computations with truncated expansions of rational numbers. Using the shifted number system the high-order lifting and integrality certification techniques of Storjohann 2003 for polynomial matrices are extended to the integer case. las vegas reductions to integer matrix multiplication are given for some problems involving integer matrices: the determinant and a solution of a linear system can be computed with about the same number of bit operations as required to multiply together two matrices having the same dimension and size of entries as the input matrix. The algorithms are space efficient. (c) 2005 Elsevier Inc. All rights reserved.

关键词： integer matrix matrix determinant linear system solving las vegas algorithms bit complexity matrix multiplication

来源：评论

学校读者我要写书评

暂无评论

Counting in one-hop beeping networks

引用

THEORETICAL COMPUTER SCIENCE 2019年第0期780卷 20-28页

作者： Casteigts, A. Metivier, Y. Robson, J. M. Zemmari, A. Univ Bordeaux LaBRI UMR CNRS 5800 Bordeaux INP 351 Cours Liberat F-33405 Talence France

We consider networks of processes which interact with beeps. In the basic model defined by Cornejo and Kuhn [8], which we refer to as the BL variant, processes can choose in each round either to beep or to listen. Those who beep are unable to detect simultaneous beeps. Those who listen can only distinguish between silence and the presence of at least one beep. Beeping models are weak in essence and even simple tasks may become difficult or unfeasible with them. In this paper, we address the problem of computing how many participants there are in a one-hop network: the counting problem. We first observe that no algorithm can compute this number with certainty in BL, even if it is randomised (las vegas). We thus consider the stronger variant where beeping nodes are able to detect simultaneous beeps, referred to as BcdL (cd stands for collision detection). We prove that at least n rounds are necessary in BcdL, and we present an algorithm whose running time is O(n) rounds with high probability. Further experimental results show that its expected running time is less than 10n. Finally, we discuss how this algorithm can be adapted in other beeping models. In particular, we show that the algorithm can be emulated in BL, at the cost of a logarithmic slowdown and of trading its las vegas nature (certain result, uncertain time) against a Monte Carlo one (certain time, uncertain result). (C) 2019 Published by Elsevier B.V.

关键词： Beeping model Size computation Counting problem las vegas algorithms

来源：评论

学校读者我要写书评

暂无评论

The quantum black-box complexity of majority

引用

ALGORITHMICA 2002年第4期34卷 480-501页

作者： Hayes, TP Kutin, S van Melkebeek, D Univ Chicago Dept Math Chicago IL 60637 USA Univ Chicago Dept Comp Sci Chicago IL 60637 USA Univ Wisconsin Dept Comp Sci Madison WI 53706 USA

We describe a quantum black-box network computing the majority of N bits with zero-sided error the correct answer with probability epsilon using only 2/3 N + O (rootN log(epsilon(-1) log N)) queries: the algorithm returns at least 1 - epsilon, and "I don't know" otherwise. Our algorithm is given as a randomized "XOR decision tree" for which the number of queries on any input is strongly concentrated around a value of at most 2/3 N. We provide a nearly matching lower bound of 2/3 N - O(rootN) on the expected number of queries on a worst-case input in the randomized XOR decision tree model with zero-sided error o(1). Any classical randomized decision tree computing the majority on N bits with zero-sided error 1/2 has cost N.

关键词： majority function quantum computing query complexity las vegas algorithms

来源：评论

学校读者我要写书评

暂无评论

Primality testing using elliptic curves

引用

JOURNAL OF THE ACM 1999年第4期46卷 450-472页

作者： Goldwasser, S Kilian, J MIT Dept Comp Sci Comp Sci Lab Cambridge MA 02139 USA NEC Res Inst Princeton NJ 08540 USA

We present a primality proving algorithm-a probabilistic primality test that produces short certificates of primality on prime inputs. We prove that the test runs in expected polynomial time for all but a vanishingly small fraction of the primes. As a corollary, we obtain an algorithm for generating large certified primes with distribution statistically close to uniform. Under the conjecture that the gap between consecutive primes is bounded by some polynomial in their size, the test is shown to run in expected polynomial time for all primes, yielding a las vegas primality test. Our test is based on a new methodology for applying group theory to the problem of prime certification, and the application of this methodology using groups generated by elliptic curves over finite fields. We note that our methodology and methods have been subsequently used and improved upon, most notably in the primality proving algorithm of Adleman and Huang using hyperelliptic curves and in practical primality provers using elliptic curves.

关键词： distribution of primes elliptic curves group theory las vegas algorithms primes prime certification prime generation

来源：评论

学校读者我要写书评

暂无评论

Algorithm portfolio selection as a bandit problem with unbounded losses

引用

ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE 2011年第2期61卷 49-86页

作者： Gagliolo, Matteo Schmidhuber, Jurgen Vrije Univ Brussel CoMo B-1050 Brussels Belgium IDSIA CH-6928 Lugano Switzerland Univ Lugano Fac Informat CH-6904 Lugano Switzerland

We propose a method that learns to allocate computation time to a given set of algorithms, of unknown performance, with the aim of solving a given sequence of problem instances in a minimum time. Analogous meta-learning techniques are typically based on models of algorithm performance, learned during a separate offline training sequence, which can be prohibitively expensive. We adopt instead an online approach, named GAMBLETA, in which algorithm performance models are iteratively updated, and used to guide allocation on a sequence of problem instances. GAMBLETA is a general method for selecting among two or more alternative algorithm portfolios. Each portfolio has its own way of allocating computation time to the available algorithms, possibly based on performance models, in which case its performance is expected to improve over time, as more runtime data becomes available. The resulting exploration-exploitation trade-off is represented as a bandit problem. In our previous work, the algorithms corresponded to the arms of the bandit, and allocations evaluated by the different portfolios were mixed, using a solver for the bandit problem with expert advice, but this required the setting of an arbitrary bound on algorithm runtimes, invalidating the optimal regret of the solver. In this paper, we propose a simpler version of GAMBLETA, in which the allocators correspond to the arms, such that a single portfolio is selected for each instance. The selection is represented as a bandit problem with partial information, and an unknown bound on losses. We devise a solver for this game, proving a bound on its expected regret. We present experiments based on results from several solver competitions, in various domains, comparing GAMBLETA with another online method.

关键词： Algorithm selection Algorithm portfolios Meta learning Online learning Multi-armed bandit problem Survival analysis las vegas algorithms Computational complexity Combinatorial optimization Constraint programming Satisfiability

来源：评论

学校读者我要写书评

暂无评论

A method for obtaining randomized algorithms with small tail probabilities

引用

ALGORITHMICA 1996年第4-5期16卷 543-547页

作者： Alt, H Guibas, L Mehlhorn, K Karp, R Wigderson, A STANFORD UNIV STANFORDCA 94305 DIGITAL EQUIPMENT CORP SYST RES CTRPALO ALTOCA 94301 UNIV SAARLAND MAX PLANCK INST INFORMATD-6600 SAARBRUCKENGERMANY UNIV SAARLAND FACHBEREICH INFORMATD-6600 SAARBRUCKENGERMANY INT COMP SCI INST BERKELEYCA 94704 UNIV CALIF BERKELEY BERKELEYCA 94720 HEBREW UNIV JERUSALEM DEPT COMP SCIIL-91905 JERUSALEMISRAEL PRINCETON UNIV DEPT COMP SCIPRINCETONNJ 07974

We study strategies for converting randomized algorithms of the las vegas type into randomized algorithms with small tail probabilities.

关键词： las vegas algorithms randomized algorithm tail probability

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：