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

A note on the search for k elements via quantum walk

INFORMATION PROCESSING LETTERS 2010年第22期110卷 975-978页

作者： Doern, Sebastian Thierauf, Thomas HTW Aalen Fak Elekt & Informat D-73430 Aalen Germany Carl Zeiss D-73447 Oberkochen Germany

In this paper we use the quantum walk search scheme by Magniez et al. (2007) [13] to find k solutions of a search problem. We show that the quantum query complexity is at most of order root klogk times the number of q... 详细信息

关键词： Quantum query complexity Quantum walk randomized algorithms Analysis of algorithms Combinatorial problems

来源：评论

学校读者我要写书评

暂无评论

Distributed Cross-Layer algorithms for the Optimal Control of Multihop Wireless Networks

引用

IEEE-ACM TRANSACTIONS ON NETWORKING 2010年第2期18卷 638-651页

作者： Eryilmaz, Atilla Ozdaglar, Asuman Shah, Devavrat Modiano, Eytan Ohio State Univ Dept Elect & Comp Engn Columbus OH 43210 USA MIT Lincoln Lab Cambridge MA 02139 USA

In this paper, we provide and study a general framework that facilitates the development of distributed mechanisms to achieve full utilization of multihop wireless networks. In particular, we describe a generic randomized routing, scheduling, and flow control scheme that allows for a set of imperfections in the operation of the randomized scheduler to account for potential errors in its operation. These imperfections enable the design of a large class of low-complexity and distributed implementations for different interference models. We study the effect of such imperfections on the stability and fairness characteristics of the system and explicitly characterize the degree of fairness achieved as a function of the level of imperfections. Our results reveal the relative importance of different types of errors on the overall system performance and provide valuable insight to the design of distributed controllers with favorable fairness characteristics. In the second part of the paper, we focus on a specific interference model, namely the secondary interference model, and develop distributed algorithms with polynomial communication and computation complexity in the network size. This is an important result given that earlier centralized throughput-optimal algorithms developed for such a model relies on the solution to an NP-hard problem at every decision. This results in a polynomial complexity cross-layer algorithm that achieves throughput optimality and fair allocation of network resources among the users. We further show that our algorithmic approach enables us to efficiently approximate the capacity region of a multihop wireless network.

关键词： Congestion control fair allocation dynamic routing multihop wireless networks network optimization randomized algorithms throughout-optimal scheduling

来源：评论

学校读者我要写书评

暂无评论

Final Comments by the Author

引用

EUROPEAN JOURNAL OF CONTROL 2010年第5期16卷 440-441页

作者： [Anonymous]

It has been a pleasure receiving and reading the discussion articles three outstanding scientists, namely, S. K. Mitter, A. Nemirovski and J. C. Willems have generously provided. Their comments increase the value of the discussion. In my article [1], I presented simple examples to get facts and concepts underlying randomized algorithms easily through. Arkadi Nemirovski presents nontrivial examples in optimization which suitably complement those in my article and add concreteness to the role of randomized algorithms in difficult problems.

关键词： Debates randomized algorithms Happiness flexible AC transmission systems iodine Nontrivial Writers final

来源：评论

学校读者我要写书评

暂无评论

A local decision test for sparse polynomials

引用

INFORMATION PROCESSING LETTERS 2010年第20期110卷 898-901页

作者： Grigorescu, Elena Jung, Kyomin Rubinfeld, Ronitt MIT Cambridge MA 02139 USA Korea Adv Inst Sci & Technol Taejon South Korea Tel Aviv Univ Tel Aviv Israel

An l-sparse (multivariate) polynomial is a polynomial containing at most l-monomials in its explicit description. We assume that a polynomial is implicitly represented as a black-box: on an input query from the domain, the black-box replies with the evaluation of the polynomial at that input. We provide an efficient, randomized algorithm, that can decide whether a polynomial f : F-q(n) -> F-q given as a black-box is l-sparse or not, provided that q is large compared to the polynomial's total degree. The algorithm makes only O(l) queries, which is independent of the domain size. The running time of our algorithm (in the bit-complexity model) is poly(n, log d, l), where d is an upper bound on the degree of each variable. Existing interpolation algorithms for polynomials in the same model run in time poly(n, d, l). We provide a similar test for polynomials with integer coefficients. (C) 2010 Elsevier B.V. All rights reserved.

关键词： randomized algorithms Sparsity tests Multivariate polynomials

来源：评论

学校读者我要写书评

暂无评论

An Approximation Algorithm for Counting Contingency Tables

引用

RANDOM STRUCTURES & algorithms 2010年第1期37卷 25-66页

作者： Barvinok, Alexander Luria, Zur Samorodnitsky, Alex Yong, Alexander Univ Michigan Dept Math Ann Arbor MI 48109 USA Hebrew Univ Jerusalem Dept Comp Sci IL-91904 Jerusalem Israel Univ Illinois Dept Math Urbana IL 61801 USA

We present a randomized approximation algorithm for counting contingency tables, m x n non-negative integer matrices with given row sums R = (r(1), ... , r(m)) and column sums C = (c(1), ... , c(n)). We define smooth margins (R, C) in terms of the typical table and prove that for such margins the algorithm has quasi-polynomial N-O(In N) complexity, where N = r(1) + ... + r(m) = c(1) + ... + c(n). Various classes of margins are smooth, e.g., when m = O(n), n = O(m) and the ratios between the largest and the smallest row sums as well as between the largest and the smallest column sums are strictly smaller than the golden ratio (1 + root 5)/2 approximate to 1.618. The algorithm builds on Monte Carlo integration and sampling algorithms for log-concave densities, the matrix scaling algorithm, the permanent approximation algorithm, and an integral representation for the number of contingency tables. (C) 2010 Wiley Periodicals, Inc. Random Struct. Alg., 37, 25-66, 2010

关键词： contingency tables randomized algorithms matrix scaling permanent approximation

来源：评论

学校读者我要写书评

暂无评论

Structural complexity of AvgBPP

引用

ANNALS OF PURE AND APPLIED LOGIC 2010年第3期162卷 213-223页

作者： Itsykson, Dmitry VA Steklov Math Inst St Petersburg 191023 Russia

We study the class AvgBPP that consists of distributional problems which can be solved in average polynomial time (in terms of Levin's average-case complexity) by randomized algorithms with bounded error. We prove that there exists a distributional problem that is complete for AvgBPP under polynomial time samplable distributions. Since we use deterministic reductions, the existence of a deterministic algorithm with average polynomial running time for our problem would imply AvgP = AvgBPP. Note that, while it is easy to construct a promise problem that is complete for promise-BPP, it is unknown whether BPP contains complete languages. We also prove a time hierarchy theorem for AvgBPP (there are no known time hierarchy theorems for BPP). We compare average-case classes with their classical (worst-case) counterparts and show that the inclusions are proper. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Average-case complexity BPP Complete problems Errorless heuristics randomized algorithms Time hierarchy

来源：评论

学校读者我要写书评

暂无评论

Towards power-sensitive communication on a multiple-access channel

Towards power-sensitive communication on a multiple-access c...

引用

International Conference on Distributed Computing Systems (ICDCS 2010)

作者： De Marco, Gianluca Kowalski, Dariusz R. Univ Salerno Dipartimento Informat & Applicaz I-84084 Fisciano SA Italy Univ Liverpool Liverpool L69 3BX Merseyside England

ISBN: (纸本)9780769540597

We are given n stations of which k are active, while the remaining n - k are asleep. The active stations communicate via a multiple-access channel. If a subset Q of active stations transmits in the same round, all active stations can recognize from the signal strength how many stations have transmitted (i.e., they learn the size of set Q), even though they may not be able to decode the contents of transmitted messages. The goal is to let each active station to learn about the set of all active stations. It is well known that Theta(k log(k+1) n) rounds are enough, even for non-adaptive deterministic algorithms. A natural interesting generalization arises when we are required to identify a subset of m <= k active stations. We show that while for randomized or for adaptive deterministic algorithms O(m log(m+1) n) rounds are sufficient, the non-adaptive deterministic counterpart still requires Theta(k log(k+1) n) rounds;therefore, finding any subset of active stations is not easier than finding all of them by a non-adaptive deterministic algorithm. We prove our results in the more general framework of combinatorial search theory, where the problem of identifying active stations on a multiple-access channel can be viewed as a variant of the well-known counterfeit coin problem.

关键词： multiple-access channel distributed learning randomized algorithms combinatorial search theory

来源：评论

学校读者我要写书评

暂无评论

Partial Information Spreading with Application to Distributed Maximum Coverage

Partial Information Spreading with Application to Distribute...

引用

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

作者： Hillel, Keren Censor Shachnai, Hadas Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel

ISBN: (纸本)9781605588889

This paper addresses partial information spreading among n nodes of a network. As opposed to traditional information spreading, where each node has a message that must be received by all nodes, we propose a relaxed requirement, where only n/c nodes need to receive each message, and every node should receive n/c messages, for some c >= 1. As a key tool in our study we introduce the novel concept of weak conductance, a generalization of classic graph conductance which allows to analyze the time required for partial information spreading. We show the power of weak conductance as a measure of how well-knit the components of a graph are, by giving an example of a graph family for which the conductance is O(n(-2)), while the weak conductance is as large as 1/2. For such graphs, weak conductance can be used to show that partial information spreading requires time complexity of O(log n). Finally, we demonstrate the usefulness of partial information spreading in solving the maximum coverage problem, which naturally arises in circuit layout, job scheduling and facility location, as well as in distributed resource allocation with a global budget constraint. Our algorithm yields a constant approximation factor and a constant deviation from the given budget. For graphs with a constant weak conductance, this implies a scalable time complexity for solving a problem with a global constraint.

关键词： distributed computing randomized algorithms weak conductance partial information spreading maximum coverage approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Approximation algorithms for distributed systems

Approximation algorithms for distributed systems

引用

作者： Pandit, Saurav The University of Iowa

学位级别：Ph.D.

Distributed Approximation is a new and rapidly developing discipline that lies at the crossroads of various well-established areas of Computer Science - Distributed Computing, Approximation algorithms, Graph Theory and often, Computational Geometry. This thesis focuses on the design and analysis of distributed algorithms to solve optimization problems that usually arise in large-scale, heavily dynamic, resource constrained networks, e.g. wireless ad-hoc and sensor networks, P2P systems, mobile networks etc. These problems can often be abstracted by variations of well-known combinatorial optimization problems, such as topology control, clustering etc. Many of these problems are known to be hard (NP-complete). But we need fast and light-weight distributed algorithms for these problems, that yield near-optimal solutions. The results presented in this thesis can be broadly divided in two parts. The first part contains a set of results that obtain improved solutions to the classic problem of computing a sparse “backbone” for Wireless Sensor Networks (WSNs). In graph-theoretic terms, the goal is to compute a spanning subgraph of the input graph, that is sparse, lightweight and has low stretch. The term “low stretch” indicates that in spite of dropping many edges, the distance between any two nodes in the graph is not increased by much. We model WSNs as geometric graphs - unit ball graphs, quasi-unit ball graphs etc. in Euclidean spaces, as well as in more general metric spaces of low doubling dimension. We identify and exploit a variety of geometric features of those models to obtain our results. In the second part of the thesis we focus on distributed algorithms for clustering problems. We present several distributed approximation algorithms for clustering problems (e.g., minimum dominating set, facility location problems) that improve on best known results so far. The main contribution here is the design of distributed algorithms where the running time is a “tunable” pa

关键词： Approximation algorithms Complexity Distributed algorithms randomized algorithms Wireless sensor networks

来源：评论

学校读者我要写书评

暂无评论

Lower Bounds on Near Neighbor Search via Metric Expansion

Lower Bounds on Near Neighbor Search via Metric Expansion

引用

IEEE 51st Annual Symposium on Foundations of Computer Science (FOCS)

作者： Panigrahy, Rina Talwar, Kunal Wieder, Udi Microsoft Research United States

ISBN: (纸本)9780769542447

In this paper we show how the complexity of performing nearest neighbor (NNS) search on a metric space is related to the expansion of the metric space. Given a metric space we look at the graph obtained by connecting every pair of points within a certain distance r. We then look at various notions of expansion in this graph relating them to the cell probe complexity of NNS for randomized and deterministic, exact and approximate algorithms. For example if the graph has node expansion Phi then we show that any deterministic t-probe data structure for n points must use space S where (St/n)(t) > Phi. We show similar results for randomized algorithms as well. These relationships can be used to derive most of the known lower bounds in the well known metric spaces such as l1, l2, l infinity, and some new ones, by simply computing their expansion. In the process, we strengthen and generalize our previous results [18]. Additionally, we unify the approach in [18] and the communication complexity based approach. Our work reduces the problem of proving cell probe lower bounds of near neighbor search to computing the appropriate expansion parameter. In our results, as in all previous results, the dependence on t is weak;that is, the bound drops exponentially in l. We show a much stronger (tight) time-space tradeoff for the class of dynamic low contention data structures. These are data structures that supports updates in the data set and that do not look up any single cell too often. A full version of the paper could be found in [19].

关键词： Data Structures Expansion Metric Spaces approximate algorithms approximation theory communication complexity computational complexity data structures dynamic low contention data structures graph graph theory lower bounds metric expansion nearest neighbor search random processes randomized algorithms search problems

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：