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

randomized Query Complexity of Sabotaged and Composed Functions

THEORY OF COMPUTING 2018年 14卷 1-27页

作者： Ben-David, Shalev Kothari, Robin Univ Maryland Joint Ctr Quantum Informat & Comp Sci College Pk MD 20742 USA Microsoft Res Quantum Architectures & Computat Grp QuArC Redmond WA USA

We study the composition question for bounded-error randomized query complexity: Is R(f circle g) = Omega(R(f) R(g)) for all Boolean functions f and g? We show that inserting a simple Boolean function h, whose query complexity is only Theta(logR(g)), in between f and g allows us to prove R(f circle h circle g) = Omega(R(f) R(h) R(g)). We prove this using a new lower bound measure for randomized query complexity we call randomized sabotage complexity, RS(f). randomized sabotage complexity has several desirable properties, such as a perfect composition theorem, RS (f circle g) >= RS(f) RS(g), and a composition theorem with randomized query complexity, R(f circle g) = Omega(R(f) RS(g)). It is also a quadratically tight lower bound for total functions and can be quadratically superior to the partition bound, the best known general lower bound for randomized query complexity. Using this technique we also show implications for lifting theorems in communication complexity. We show that a general lifting theorem for zero-error randomized protocols implies a general lifting theorem for bounded-error protocols.

关键词： randomized algorithms query complexity composition theorems

来源：评论

学校读者我要写书评

暂无评论

Assigning Tasks to Workers based on Historical Data: Online Task Assignment with Two-sided Arrivals 17

Assigning Tasks to Workers based on Historical Data: Online ...

引用

17th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS)

作者： Dickerson, John P. Sankararaman, Karthik Abinav Srinivasan, Aravind Xu, Pan Univ Maryland College Pk MD 20742 USA

ISBN: (纸本)9781450356497

Efficient allocation of tasks to workers is a central problem in crowd-sourcing. In this paper, we consider a special setting inspired from spatial crowdsourcing platforms where both workers and tasks arrive dynamically. Additionally, we assume all tasks are heterogeneous and each worker-task assignment brings a distinct reward. The natural challenge lies in how to incorporate the uncertainty in the arrivals from both workers and tasks into our online allocation policy such that the total expected rewards are maximized. To attack this challenge, we assume the arrival patterns of worker "types" and task "types" are not erratic and can be predicted from historical data. To be more specific, we consider a finite time horizon T and assume in each time-step, a single worker and task are sampled (i.e., "arrive") from two respective distributions independently, and this sampling process repeats identically and independently for the entire T online time-steps. Our model, called Online Task Assignment with Two-Sided Arrival (OTA-TSA), is a significant generalization of the classical online task assignment where the set of tasks is assumed to be available offline. For the general version of OTA-TSA, we present an optimal non-adaptive algorithm which achieves an online competitive ratio of 0.295. For the special case of OTA-TSA where the reward is a function of just the worker type, we present an improved algorithm (which is adaptive) and achieves a competitive ratio of at least 0.343. On the hardness side, along with showing that the ratio obtained by our non-adaptive algorithm is the best possible among all non-adaptive algorithms, we further show that no (adaptive) algorithm can achieve a ratio better than 0.581 (unconditionally), even for the special case of OTA-TSA with homogenous tasks (i.e., all rewards are same). At the heart of our analysis lies a new technical tool (which is a refined notion of the birth-death process), called the two-stage birth-death process, which

关键词： Crowdsourcing model Online Matching randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

On fast and robust information spreading in the Vertex-Congest model 1

引用

22nd International Colloquium on Structural Information and Communication Complexity (SIROCCO)

作者： Censor-Hillel, Keren Toukan, Tariq Technion Israel Inst Technol Haifa Israel

ISBN: (数字)9783319252582

ISBN: (纸本)9783319252575

This paper initiates the study of the impact of failures on the fundamental problem of information spreading in the Vertex-Congest model, in which in every round, each of the n nodes sends the same O (logn)-bit message to all of its neighbors. We consider a strong failure model, in which links are reliable but nodes fail independently with probability q per round and never recover. Our contribution to coping with failures is twofold. First, we prove that the randomized algorithm which chooses uniformly at random the next message to forward is slow, requiring Omega(n/root k) rounds on some graphs, which we denote by G(n,k) , where k is the vertex-connectivity. Second, we design a randomized algorithm that makes dynamic message choices, with probabilities that change over the execution. We prove that for G(n,k) it requires only a near-optimal number of O(n log(3) n/k) rounds, despite a rate of q = O (k/n log(3) n) failures per round. Our technique of choosing probabilities that change according to the execution is of independent interest. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Distributed computing Information spreading randomized algorithms Vertex-connectivity Fault tolerance

来源：评论

学校读者我要写书评

暂无评论

MST in O(1) Rounds of Congested Clique 29

MST in <i>O</i>(1) Rounds of Congested Clique

引用

29th Annual ACM-SIAM Symposium on Discrete algorithms (SODA)

作者： Jurdzinski, Tomasz Nowicki, Krzysztof Univ Wroclaw Inst Comp Sci Wroclaw Poland

ISBN: (纸本)9781611975031

We present a distributed randomized algorithm finding Minimum Spanning Tree (MST) of a given graph in O(1) rounds, with high probability, in the congested clique model. The input graph in the congested clique model is a graph of n nodes, where each node initially knows only its incident edges. The communication graph is a clique with limited edge bandwidth: each two nodes (not necessarily neighbours in the input graph) can exchange O(log n) bits. As in previous works, the key part of the MST algorithm is an efficient Connected Components (CC) algorithm. However, unlike the former approaches, we do not aim at simulating the standard Boruvka's algorithm, at least at initial stages of the CC algorithm. Instead, we develop a new technique which combines connected components of sample sparse subgraphs of the input graph in order to accelerate the process of uncovering connected components of the original input graph. More specifically, we develop a sparsification technique which reduces an initial CC problem in O(1) rounds to its two restricted instances. The former instance has a graph with maximal degree O(log log n) as the input {here our sample-combining technique helps. In the latter instance, a partition of the input graph into O(n=log log n) connected components is known. This gives an opportunity to apply previous algorithms to determine connected components in O(1) rounds. Our result addresses a problem proposed by Lotker et al. [SPAA 2003;SICOMP 2005] and improves over previous O(log* n) algorithm of Ghaffari et al. [PODC 2016], and O(log log log n) algorithm of Hegeman et al. [PODC 2015]. It also determines Theta(1) round complexity in the congested clique for MST, as well as other graph problems, including bipartiteness, cut verification, s-t connectivity, and cycle containment.

关键词： congested clique connected components minimum spanning tree randomized algorithms broadcast unicast

来源：评论

学校读者我要写书评

暂无评论

Analysis of Consensus Sorting via the Cycle Metric 12th

Analysis of Consensus Sorting via the Cycle Metric

引用

12th Annual International Conference on Combinatorial Optimization and Applications (COCOA)

作者： Avramovic, Ivan Richards, Dana S. George Mason Univ Fairfax VA 22030 USA

ISBN: (纸本)9783030046514;9783030046507

Sorting is studied in this paper as an archetypal example to explore the optimizing power of consensus. In conceptualizing the consensus sort, the classical hill-climbing method of optimization is paired with the modern notion that value and fitness can be judged by data mining. Consensus sorting is a randomized sorting algorithm which is based on randomly selecting pairs of elements within an unsorted list (expressed in this paper as a permutation), and deciding whether to swap them based on appeals to a database of other permutations. The permutations in the database are all scored via some adaptive sorting metric, and the decision to swap depends on whether the database consensus suggests a better score as a result of swapping. This uninformed search process does not require the definition of the concept of sorting, but rather a depends on selecting a metric which does a good job of distinguishing a good path to the goal, a sorted list. A previous paper has shown that the ability of the algorithm to converge on the goal depends strongly on the metric which is used, and analyzed the performance of the algorithm when number of inversions was used as a metric. This paper continues by analyzing the performance of a much more efficient metric, the number of cycles in the permutation.

关键词： Adaptive sorting randomized algorithms Uninformed search Combinatorics Simulation and modeling

来源：评论

学校读者我要写书评

暂无评论

Minimizing Inputs for Strong Structural Controllability

Minimizing Inputs for Strong Structural Controllability

引用

American Control Conference

作者： Kumar Yashashwi Shana Moothedath Prasanna Chaporkar Indian Institute of Technology Bomhay India University of Washington USA

ISBN: (纸本)9781538679012;9781538679265

The notion of strong structural controllability (s-controllability) allows for determining controllability properties of large linear time-invariant systems even when numerical values of the system parameters are not known a priori. The s-controllability guarantees controllability for all numerical realizations of the system parameters. We address the optimization problem of minimal cardinality input selection for s-controllability. Previous work shows that not only the optimization problem is NP-hard, but finding an approximate solution is also hard. We propose a randomized algorithm using the notion of zero forcing sets to obtain an optimal solution with high probability. We compare the performance of the proposed algorithm with a known heuristic [1] for synthetic random systems and three real world networks, viz. IEEE 39-bus system, protein-protein interaction network, and US airport network. It is found that our algorithm performs much better than the heuristic in each of these cases.

关键词： system parameter structural controllability controllability randomized algorithms Heuristics numerical value Nondeterministic polynomial-time hard optimal solution

来源：评论

学校读者我要写书评

暂无评论

SAMPLING AND RECONSTRUCTION OF GRAPH SIGNALS VIA WEAK SUBMODULARITY AND SEMIDEFINITE RELAXATION

SAMPLING AND RECONSTRUCTION OF GRAPH SIGNALS VIA WEAK SUBMOD...

引用

IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)

作者： Hashemi, Abolfazl Shafipour, Rasoul Vikalo, Haris Mateos, Gonzalo Univ Texas Austin Dept Elect & Comp Engn Austin TX 78712 USA Univ Rochester Dept Elect & Comp Engn Rochester NY USA

ISBN: (纸本)9781538646588

We study the problem of sampling a bandlimited graph signal in the presence of noise, where the objective is to select a node subset of prescribed cardinality that minimizes the signal reconstruction mean squared error (MSE). To that end, we formulate the task at hand as the minimization of MSE subject to binary constraints, and approximate the resulting NP-hard problem via semidefinite programming (SDP) relaxation. Moreover, we provide an alternative formulation based on maximizing a monotone weak submodular function and propose a randomized-greedy algorithm to find a sub-optimal subset. We then derive a worst-case performance guarantee on the MSE returned by the randomized greedy algorithm for general non-stationary graph signals. The efficacy of the proposed methods is illustrated through numerical simulations on synthetic and real-world graphs. Notably, the randomized greedy algorithm yields an order-of-magnitude speedup over state-of-the-art greedy sampling schemes, while incurring only a marginal MSE performance loss.

关键词： graph signal processing sampling weak submodularity semidefinite programming randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

A randomized NONMONOTONE BLOCK PROXIMAL GRADIENT METHOD FOR A CLASS OF STRUCTURED NONLINEAR PROGRAMMING

引用

SIAM JOURNAL ON NUMERICAL ANALYSIS 2017年第6期55卷 2930-2955页

作者： Lu, Zhaosong Xiao, Lin Simon Fraser Univ Dept Math Burnaby BC V5A 1S6 Canada Microsoft Res Machine Learning Grp One Microsoft Way Redmond WA 98052 USA

We propose a randomized nonmonotone block proximal gradient (RNBPG) method for minimizing the sum of a smooth (possibly nonconvex) function and a block-separable (possibly nonconvex nonsmooth) function. At each iteration, this method randomly picks a block according to any prescribed probability distribution and solves typically several associated proximal subproblems that usually have a closed-form solution, until a certain progress on objective value is achieved. In contrast to the usual randomized block coordinate descent method [P. Richtarik and M. Takac, Math. Program., 144 (2014), pp. 1-38;A. Patrascu and I. Necoara, J. Global Optim., 61 (2015), pp. 19-46], our method has a nonmonotone flavor and uses variable stepsizes that can partially utilize the local curvature information of the smooth component of objective function. We show that any accumulation point of the solution sequence of the method is a stationary point of the problem almost surely and the method is capable of finding an approximate stationary point with high probability. We also establish a sublinear rate of convergence for the method in terms of the minimal expected squared norm of certain proximal gradients over the iterations. When the problem under consideration is convex, we show that the expected objective values generated by RNBPG converge to the optimal value of the problem. Under some assumptions, we further establish a sublinear and linear rate of convergence on the expected objective values generated by a monotone version of RNBPG. Finally, we conduct some preliminary experiments to test the performance of RNBPG on the l(1)-regularized least-squares problem, a dual support vector machine problem in machine learning, the l(0)-regularized least-squares problem, and a regularized matrix completion model. The computational results demonstrate that our method substantially outperforms the randomized block coordinate descent method with fixed or variable stepsizes.

关键词： nonconvex composite optimization randomized algorithms block coordinate gradient method nonmonotone line search

来源：评论

学校读者我要写书评

暂无评论

Communication-Avoiding Parallel Minimum Cuts and Connected Components 18

Communication-Avoiding Parallel Minimum Cuts and Connected C...

引用

23rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP)

作者： Gianinazzi, Lukas Kalvoda, Pavel De Palma, Alessandro Besta, Maciej Hoefler, Torsten Swiss Fed Inst Technol Dept Comp Sci Zurich Switzerland Google Inc Mountain View CA USA

ISBN: (纸本)9781450349826

We present novel scalable parallel algorithms for finding global minimum cuts and connected components, which are important and fundamental problems in graph processing. To take advantage of future massively parallel architectures, our algorithms are communication-avoiding: they reduce the costs of communication across the network and the cache hierarchy. The fundamental technique underlying our work is the randomized sparsification of a graph: removing a fraction of graph edges, deriving a solution for such a sparsified graph, and using the result to obtain a solution for the original input. We design and implement sparsification with O(1) synchronization steps. Our global minimum cut algorithm decreases communication costs and computation compared to the state-of-the-art, while our connected components algorithm incurs few cache misses and synchronization steps. We validate our approach by evaluating MPI implementations of the algorithms on a petascale supercomputer. We also provide an approximate variant of the minimum cut algorithm and show that it approximates the exact solutions well while using a fraction of cores in a fraction of time.

关键词： Parallel Computing Minimum cuts randomized algorithms Graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Markov chains and emergent behavior for problems from discrete geometry

Markov chains and emergent behavior for problems from discre...

引用

作者： Cannon, Sarah Georgia Institute of Technology

学位级别：博士

The problem of generating random samples from large, complex sets is widespread across the sciences, where such samples provide one way to begin to learn about the sets' typical properties. However, when the samples generated are unexpectedly correlated or drawn from the wrong distribution, this can produce misleading conclusions. One way to generate random samples is with Markov chains, which are widely used but often applied without careful analysis of their mixing time, how long they must run for until they are guaranteed to produce good samples. We present new mixing time bounds for two sampling problems from discrete geometry: dyadic tilings, combinatorial structures with applications in machine learning and harmonic analysis, and 3-colorings on a grid, an instance of the celebrated antiferromagnetic Potts model from statistical physics. Both of these results required the development of new techniques. In addition, we use Markov chains in a novel way to address research questions in programmable matter. Here, a main goal is to understand how simple computational elements can collectively accomplish complicated system-level goals. In an abstracted setting, we show that groups of particles executing our simple processes, based on Markov chains, can accomplish various tasks. This includes compression, a behavior exhibited by natural distributed systems such as fire ants and honey bees, and shortcut bridging, where the particles build bridges that optimize the same global trade-off as certain bridge-building ant colonies. Throughout, a key ingredient is the interplay between global properties of Markov chains, including but not limited to mixing time, and their dependence on local moves, or Markov chain transitions that change only a small part of the configuration. We call the global behavior that arises out of these local moves and their probabilities emergent behavior. In addition to understanding the relationship between local moves and mixing times in order to

关键词： Markov chains Sampling algorithms randomized algorithms Discrete geometry Dyadic tilings Programmable matter Self-organization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：