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

52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS)

作者： Fraigniaud, Pierre Korman, Amos Peleg, David CNRS Paris France

ISBN: (纸本)9780769545714

A central theme in distributed network algorithms concerns understanding and coping with the issue of locality. Despite considerable progress, research efforts in this direction have not yet resulted in a solid basis in the form of a fundamental computational complexity theory for locality. Inspired by sequential complexity theory, we focus on a complexity theory for distributed decision problems. In the context of locality, solving a decision problem requires the processors to independently inspect their local neighborhoods and then collectively decide whether a given global input instance belongs to some specified language. We consider the standard LOCAL model of computation and define LD(t) (for local decision) as the class of decision problems that can be solved in t communication rounds. We first study the intriguing question of whether randomization helps in local distributed computing, and to what extent. Specifically, we define the corresponding randomized class BPLD (t, p, q), containing all languages for which there exists a randomized algorithm that runs in t rounds, accepts correct instances with probability at least p and rejects incorrect ones with probability at least q. We show that p(2) + q = 1 is a threshold for the containment of LD(t) in BPLD(t, p, q). More precisely, we show that there exists a language that does not belong to LD(t) for any t = o(n) but does belong to BPLD (0, p, q) for any p, q is an element of (0, 1] such that p(2) + q <= 1. On the other hand, we show that, restricted to hereditary languages, BPLD (t, p, q) = LD(O(t)), for any function t and any p, q is an element of (0;1] such that p(2) + q > 1. In addition, we investigate the impact of non-determinism on local decision, and establish some structural results inspired by classical computational complexity theory. Specifically, we show that non-determinism does help, but that this help is limited, as there exist languages that cannot be decided non-deterministically. Perhaps su

关键词： Local distributed algorithms local decision nondeterminism randomized algorithms oracles

来源：评论

学校读者我要写书评

暂无评论

A Polylogarithmic-Competitive Algorithm for the k-Server Problem (Extended Abstract)

A Polylogarithmic-Competitive Algorithm for the k-Ser...

引用

52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS)

作者： Bansal, Nikhil Buchbinder, Niv Madry, Aleksander Naor, Joseph (Seffi) IBM Corp Thomas J Watson Res Ctr Yorktown Hts NY 10598 USA Open Univ Dept Comp Sci Raanana Israel Microsoft Res Cambridge MA 02142 USA Technion Haifa Dept Comp Sci Haifa Israel

ISBN: (纸本)9780769545714

We give the first polylogarithmic-competitive randomized algorithm for the k-server problem on an arbitrary finite metric space. In particular, our algorithm achieves a competitive ratio of (O) over tilde (log(3) n log(2) k) for any metric space on n points. This improves upon the (2k - 1)-competitive algorithm of Koutsoupias and Papadimitriou [22] whenever n is sub-exponential in k.

关键词： k-server problem randomized algorithms competitive analysis

来源：评论

学校读者我要写书评

暂无评论

Everywhere complex sequences and the probabilistic method

Everywhere complex sequences and the probabilistic method

引用

28th International Symposium on Theoretical Aspects of Computer Science (SATCS)

作者： Rumyantsev, Andrey Yu. Moscow MV Lomonosov State Univ Moscow Russia

ISBN: (纸本)9783939897255

The main subject of the paper is everywhere complex sequences. An everywhere complex sequence is a sequence that does not contain substrings of Kolmogorov complexity less than alpha n - O(1) where n is the length of the substring and alpha is a constant between 0 and 1. First, we prove that no randomized algorithm can produce an everywhere complex sequence with positive probability. On the other hand, for weaker notions of everywhere complex sequences the situation is different. For example, there is a probabilistic algorithm that produces (with probability 1) sequences whose substrings of length n have complexity root n - O(1). Finally, one may replace the complexity of a substring (in the definition of everywhere complex sequences) by its conditional complexity when the position is given. This gives a stronger notion of everywhere complex sequence, and no randomized algorithm can produce (with positive probability) such a sequence even if alpha n is replaced by root n, log* n or any other monotone unbounded computable function.

关键词： Kolmogorov complexity everywhere complex sequences randomized algorithms Medvedev reducibility Muchnik reducibility

来源：评论

学校读者我要写书评

暂无评论

Social Networks Spread Rumors in Sublogarithmic Time

引用

Electronic Notes in Discrete Mathematics 2011年 38卷 303-308页

作者： Doerr, Benjamin Fouz, Mahmoud Friedrich, Tobias Max-Planck-Institut Informatik Germany Universität des Saarlandes Germany

It has been observed that information spreads extremely fast in social networks. We model social networks with the preferential attachment model of Barabási and Albert (Science 1999) and information spreading with the random phone call model of Karp et al. (FOCS 2000). In a recent paper (STOC 2011), we prove the following two results. (i) The random phone call model delivers a message to all nodes of graphs in the preferential attachment model within Θ(logn) rounds with high probability. The best known bound so far was O(log²n). (ii) If we slightly modify the protocol so that contacts are chosen uniformly from all neighbors but the one Θ(logn/loglogn), which is the diameter of the graph. This is the first time that a sublogarithmic broadcast time is proven for a natural setting. Also, this is the first time that avoiding doublecontacts reduces the run-time to a smaller order of magnitude. © 2011 Elsevier B.V.

关键词： Preferential attachment randomized algorithms Rumor spreading

来源：评论

学校读者我要写书评

暂无评论

An Output-Sensitive Algorithm for Persistent Homology 11

An Output-Sensitive Algorithm for Persistent Homology

引用

27th Annual ACM Symposium on Computational Geometry

作者： Chen, Chao Kerber, Michael IST Austria Klosterneuburg Austria

ISBN: (纸本)9781450306829

In this paper, we present the first output-sensitive algorithm to compute the persistence diagram of a filtered simplicial complex. For any Gamma > 0, it returns only those homology classes with persistence at least F. Instead of the classical reduction via column operations, our algorithm performs rank computations on submatrices of the boundary matrix. For an arbitrary constant delta is an element of (0, 1), the running time is O(C((1-delta))(Gamma)R(n) log n), where C(1-delta)Gamma is the number of homology classes with persistence at least (1 - delta)F, n is the total number of simplices, and R(n) is the complexity of computing the rank of an nxn matrix with O(n) nonzero entries. Depending on the choice of the rank algorithm, this yields a deterministic O(C((1-delta)Gamma)n(2.376)) algorithm, a O(C((1-delta)Gamma)n(2.28)) Las-Vegas algorithm, or a O(C((1-delta)Gamma)n(2+epsilon)) Monte-Carlo algorithm for an arbitrary is an element of > 0.

关键词： computational topology persistent homology randomized algorithms rank computation

来源：评论

学校读者我要写书评

暂无评论

Non-fragile H_∞ Static Output Feedback Control for Discrete-time Linear Systems

Non-fragile H∞ Static Output Feedback Con...

引用

23rd Chinese Control and Decision Conference

作者： Ding, Dawei Li, Xiaoli Yin, Yixin Liu, Dexin Univ Sci & Technol Beijing Sch Automat & Elect Engn Beijing 100083 Peoples R China

ISBN: (纸本)9781424487363

This paper investigates the problem of non-fragile static output feedback control (SOF) design for discrete-time linear systems. Interval type of additive gain variations to reflect imprecision in controller implementation is considered. The non-fragile SOF controller design is firstly formulated as a robust convex problem. Then a deterministic algorithm and a randomized one are proposed to solve the obtained robust convex problem. These two algorithms complements each other. The deterministic algorithm is suitable for systems with low dimensions, while the randomized one is applicable for systems with high dimensions. In addition, the randomized algorithm can alleviate the conservatism of the deterministic one. Two examples are given to show the effectiveness of the proposed method.

关键词： Non-fragile Static output feedback randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Solving connectivity problems parameterized by treewidth in single exponential time (Extended abstract)

Solving connectivity problems parameterized by treewidth in ...

引用

52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS)

作者： Cygan, Marek Nederlof, Jesper Pilipczuk, Marcin Pilipczuk, Michal van Rooij, Johan M. M. Wojtaszczyk, Jakub Onufry Univ Warsaw Inst Informat Warsaw Poland Univ Bergen Dept Informat Bergen Norway Univ Warsaw Fac Math Fac Informat Fac Mech Warsaw Poland Univ Utrecht Dept Informat & Comp Sci Utrecht Netherlands Google Inc Krakow Poland

ISBN: (纸本)9780769545714

For the vast majority of local problems on graphs of small treewidth (where by local we mean that a solution can be verified by checking separately the neighbourhood of each vertex), standard dynamic programming techniques give c(tw) vertical bar V vertical bar(O(1)) time algorithms, where tw is the treewidth of the input graph G = (V, E) and c is a constant. On the other hand, for problems with a global requirement (usually connectivity) the best-known algorithms were naive dynamic programming schemes running in at least tw(tw) time. We breach this gap by introducing a technique we named Cut&Count that allows to produce c(tw) vertical bar V vertical bar(O(1)) time Monte Carlo algorithms for most connectivity-type problems, including HAMILTONIAN PATH, STEINER TREE, FEEDBACK VERTEX SET and CONNECTED DOMINATING SET. These results have numerous consequences in various fields, like parameterized complexity, exact and approximate algorithms on planar and H-minor-free graphs and exact algorithms on graphs of bounded degree. The constant c in our algorithms is in all cases small, and in several cases we are able to show that improving those constants would cause the Strong Exponential Time Hypothesis to fail. In contrast to the problems aiming to minimize the number of connected components that we solve using Cut&Count as mentioned above, we show that, assuming the Exponential Time Hypothesis, the aforementioned gap cannot be breached for some problems that aim to maximize the number of connected components like CYCLE PACKING.

关键词： treewidth fixed parameter tractability randomized algorithms exact algorithms

来源：评论

学校读者我要写书评

暂无评论

Neighbor Discovery in Wireless Networks with Multipacket Reception 11

Neighbor Discovery in Wireless Networks with Multipacket Rec...

引用

12th ACM International Symposium on Mobile Ad Hoc Networking and Computing

作者： Zeng, Wei Chen, Xian Russell, Alexander Vasudevan, Sudarshan Wang, Bing Wei, Wei Univ Connecticut Storrs CT 06269 USA Alcatel Lucent Bell Labs Boulogne France Univ Massachusetts Amherst NY USA

ISBN: (纸本)9781450307222

Neighbor discovery is one of the first steps in configuring and managing a wireless network. Most existing studies on neighbor discovery assume a single-ppacket reception model where only a single packet can be received successfully at a receiver. In this paper, motivated by the increasing prevalence of multipacket reception (MPR) technologies such as CDMA and MIMO, we study neighbor discovery in MPR networks that allow multiple packets to be received successfully at a receiver. More specifically, we design and analyze a series of randomized algorithms for neighbor discovery in MPR networks. We start with a simple Aloha-plike algorithm that assumes synchronous node transmissions and the number of neighbors, n, is known. We show that the time for all the nodes to discover their respective neighbors is Theta(ln n) in an idealized MPR network that allows an arbitrary number of nodes to transmit simultaneously. In a more realistic scenario, in which no more than k nodes can transmit simultaneously, we show that the time to discover all neighbors is Theta(n ln n/k). When a node knows whether its transmission is successful or not (e.g., based on feedbacks from other nodes), we design an adaptive Aloha-plike algorithm that dynamically determines the transmission probability for each node, and show that it yields a ln n improvement over the simple Aloha-plike scheme. Last, we extend our schemes to take into account a number of practical considerations, such as lack of knowledge of the number of neighbors and asynchronous algorithm operation, while resulting in only a constant or log n factor slowdown in algorithm performance.

关键词： Wireless Networks Ad Hoc Networks Sensor Networks Network Management Neighbor Discovery randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Social Networks Spread Rumors in Sublogarithmic Time 11

Social Networks Spread Rumors in Sublogarithmic Time

引用

43rd ACM Symposium on Theory of Computing

作者： Doerr, Benjamin Fouz, Mahmoud Friedrich, Tobias Max Planck Inst Informat D-66123 Saarbrucken Germany

ISBN: (纸本)9781450306911

With the prevalence of social networks, it has become increasingly important to understand their features and limitations. It has been observed that information spreads extremely fast in social networks. We study the performance of randomized rumor spreading protocols on graphs in the preferential attachment model. The well-known random phone call model of Karp et al. (FOCS 2000) is a push-pull strategy where in each round, each vertex chooses a random neighbor and exchanges information with it. We prove the following. The push-pull strategy delivers a message to all nodes within Theta(log n) rounds with high probability. The best known bound so far was O(log(2) n). If we slightly modify the protocol so that contacts are chosen uniformly from all neighbors but the one contacted in the previous round, then this time reduces to Theta(log n/log log n), which is the diameter of the graph. This is the first time that a sublogarithmic broadcast time is proven for a natural setting. Also, this is the first time that avoiding double-contacts reduces the run-time to a smaller order of magnitude.

关键词： randomized algorithms social network rumor spreading

来源：评论

学校读者我要写书评

暂无评论

Stabilizing Consensus With the Power of Two Choices 11

Stabilizing Consensus With the Power of Two Choices

引用

23rd Annual Symposium on Parallelism in algorithms and Architectures

作者： Doerr, Benjamin Goldberg, Leslie Ann Minder, Lorenz Sauerwald, Thomas Scheideler, Christian Max Planck Inst Informat Saarbrucken Germany

ISBN: (纸本)9781450307437

In the standard consensus problem there are n processes with possibly different input values and the goal is to eventually reach a point at which all processes commit to exactly one of these values. We are studying a slight variant of the consensus problem called the stabilizing consensus problem [2]. In this problem, we do not require that each process commits to a final value at some point, but that eventually they arrive at a common, stable value without necessarily being aware of that. This should work irrespective of the states in which the processes are starting. Our main result is a simple randomized algorithm called median rule that, with high probability, just needs O(log m log log n + log n) time and work per process to arrive at an almost stable consensus for any set of m legal values as long as an adversary can corrupt the states of at most root n processes at any time. Without adversarial involvement, just O(log n) time and work is needed for a stable consensus, with high probability. As a by-product, we obtain a simple distributed algorithm for approximating the median of n numbers in time O(log m log log n + log n) under adversarial presence.

关键词： distributed consensus self-stabilization randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：