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

TIGHT BOUNDS FOR randomized AND QUANTUM LOCAL SEARCH

SIAM JOURNAL ON COMPUTING 2009年第3期39卷 948-977页

作者： Zhang, Shengyu Chinese Univ Hong Kong Dept Comp Sci & Engn Shatin Hong Kong Peoples R China

The problem Local Search, which finds a local minimum of a black-box function on a given graph, is of both practical and theoretical importance to combinatorial optimization, complexity theory, and many other areas in theoretical computer science. In this paper, we study the problem in both the randomized and the quantum query models and give new lower and upper bound techniques in both models. The lower bound technique works for any graph that contains a product graph as a subgraph. Applying it to the Boolean hypercube {0, 1}(n) and the constant-dimensional grids [n](d), two particular product graphs that recently drew much attention, we get the following tight results: RLS({0, 1}(n)) = Theta(2(n)/(2)n(1/2)), QLS({0, 1}(n)) = Theta(2(n/3)n(1/6)), RLS([n](d)) = Theta(n(d/2)) for d >= 4, QLS([n](d)) = Theta(n(d/3)) for d >= 6. Here RLS(G) and QLS(G) are the randomized and quantum query complexities of Local Search on G, respectively. These improve the previous results by Aaronson [in Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, 2004, pp. 465-474], Ambainis (unpublished), and Santha and Szegedy [in Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, 2004, pp. 494-501]. Our new algorithms work well when the underlying graph expands slowly. As an application to [n](2), a new quantum algorithm using O(root n(log log n)(1.5)) queries is given. This improves the previously best known upper bound of O(n(2/3)) (see Aaronson [in Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, 2004, pp. 465-474]), and implies that Local Search on grids exhibits different properties in low dimensions.

关键词： optimization local search quantum algorithm quantum query complexity randomized algorithm randomized decision tree complexity

来源：评论

学校读者我要写书评

暂无评论

Sublinear Message Bounds for randomized Agreement 18

Sublinear Message Bounds for Randomized Agreement

引用

37th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC)

作者： Augustine, John Molla, Anisur Rahaman Pandurangan, Gopal Indian Inst Technol Madras Dept Comp Sci & Engn Chennai Tamil Nadu India Natl Inst Sci Educ & Res Bhubaneswar Sch Comp Sci Khurja Odisha India Univ Houston Dept Comp Sci Houston TX 77204 USA

ISBN: (纸本)9781450357951

This paper focuses on understanding the message complexity of randomized agreement in synchronous distributed networks. We focus on the so-called implicit agreement problem where each node starts with an input value (0 or 1) and at the end one or more nodes should decide on a common input value which should be equal to some node's input value (there can be undecided nodes). Implicit agreement is a generalization of the fundamental agreement and leader election problems. We present sublinear (in n, where n is the number of nodes) algorithms and lower bounds on the message complexity of implicit agreement in fully-connected (i. e., complete) networks. Specifically our main results are: (1) We show that for any implicit agreement algorithm that succeeds with probability at least 1-epsilon, for some suitably small constant. > 0, needs at least Omega(n(0.5)) messages with constant probability. This bound holds regardless of the number of rounds used and applies to both LOCAL and CONGEST models. This lower bound is essentially tight for complete networks, as there exists a randomized agreement algorithm that uses only (O) over tilde (n(0.5)) messages1 with high probability2 and runs in O(1) rounds and succeeds with high probability. Both the upper and lower bounds assume that nodes have access to (only) private coins. (2) In contrast to the above bounds, if nodes have access to an unbiased global (shared) coin, we present a randomized algorithm which, with high probability, achieves implicit agreement, and uses (O) over tilde (n(0.4)) messages in expectation and runs in (O) over tilde (1) rounds (deterministically). This algorithm works in the CONGEST model as well. Our result shows the power of a global coin in significantly improving (by a polynomial factor) the message complexity of agreement. As another contrast, we show that the same benefit does not apply to leader election, i. e., even with access to a global coin, (O) over tilde (n(0.5)) messages (in expectation)

关键词： Distributed algorithm randomized algorithm Agreement Leader Election Global Coin Shared Randomness

来源：评论

学校读者我要写书评

暂无评论

randomized ROBUST SUBSPACE RECOVERY FOR BIG DATA 25

RANDOMIZED ROBUST SUBSPACE RECOVERY FOR BIG DATA

引用

IEEE International Workshop on Machine Learning for Signal Processing

作者： Rahmani, Mostafa Atia, George K. Univ Cent Florida Dept Elect Engn & Comp Sci Orlando FL 32816 USA

ISBN: (纸本)9781467374545

In this paper, a randomized PCA algorithm that is robust to the presence of outliers and whose complexity is independent of the dimension of the given data matrix is proposed. Using random sampling and random embedding techniques, the given data matrix is turned to a small compressed data. A subspace learning approach is proposed to extract the columns subspace of the low rank matrix from the compressed data. Two ideas for robust subspace learning are proposed to work under two different model assumptions. The first idea is based on the linear dependence between the columns of the low rank matrix, and the second is based on the independence between the columns subspace of the low rank matrix and the subspace spanned by the outlying columns. We derive sufficient conditions to guarantee the performance of the proposed approach with high probability. It is shown that the proposed algorithm can successfully identify the outliers just by using roughly O(r(2)) random linear data observations, where r is the rank of the low rank matrix, and provably achieve notable speedups in comparison to existing approaches.

关键词： Robust PCA randomized algorithm Low Rank Matrix Subspace Learning Big Data Outlier Detection Random Embedding

来源：评论

学校读者我要写书评

暂无评论

Classification and Applications of randomized Functional Numerical algorithms for the Solution of Second-Kind Fredholm Integral Equations

引用

Journal of Mathematical Sciences (United States) 2021年第5期254卷 589-605页

作者： Voytishek, A.V. Institute of Computational Mathematics and Mathematical Geophysics Siberian Branch of the Russian Academy of Sciences Novosibirsk Russian Federation Novosibirsk State University Novosibirsk Russian Federation

Systematization of numerical randomized functional algorithms for approximation of solutions to second-kind Fredholm integral equation is performed in this paper. Three types of algorithms are emphasized: projection algorithms, grid algorithms, and projection-grid algorithms. Disadvantages of grid algorithms that require calculation of values of the kernel of integral equations at fixed points are revealed (practically, the kernels of equation have integrable singularities and this calculation is impossible). Thus, for applied problems related to the solution of second-kind Fredholm integral equations, projection or projection-grid randomized algorithms are more convenient. © 2021, Springer Science+Business Media, LLC, part of Springer Nature.

关键词： 45B05 65C05 65C40 computational kernel grid algorithm numerical solution projection algorithm randomized algorithm second-kind Fredholm integral equation

来源：评论

学校读者我要写书评

暂无评论

randomized Strategies for Non-additive 3-Slope Ski Rental 1

引用

29th International Colloquium on Structural Information and Communication Complexity (SIROCCO)

作者： Bohnlein, Toni Erlich, Sapir Lotker, Zvi Rawitz, Dror Weizmann Inst Sci Rehovot Israel Bar Ilan Univ Ramat Gan Israel

ISBN: (数字)9783031099939

ISBN: (纸本)9783031099939;9783031099922

The SKI RENTAL problem captures the dilemma of choosing between renting and buying, and it is one of the fundamental problems in online computation. In many realistic scenarios there may be several intermediate lease options which are modelled by the MULTISLOPE SKI RENTAL problem. An instance consists of k states where each state i is an element of {0,..., k - 1} is characterized by a buying cost b(i) and a rental rate ri. Previous work on instance-dependent strategies for MULTI-SLOPE SKI RENTAL dealt with deterministic strategies or strategies for additive instances (instance where going from state i to state j costs b(j) - b(i)). However, obtaining instance-dependent randomized strategies for non-additive instances remains open. In this paper, we advance towards answering this open question by characterizing optimal randomized strategies in the non-additive case, and providing an algorithm that computes near-optimal instance-dependent randomized strategies for MULTI-SLOPE SKI RENTAL with three slopes (k = 2). The algorithm uses parametric search and a decision algorithm which is based on the characterization of optimal randomized strategies.

关键词： Online algorithms Competitive analysis randomized algorithm Ski-rental

来源：评论

学校读者我要写书评

暂无评论

Efficient randomized routing algorithms on the two-dimensional mesh of buses 4th

Efficient randomized routing algorithms on the two-dimension...

引用

4th Annual International Computing and Combinatorics Conference (COCOON 98)

作者： Iwama, K Miyano, E Tajima, S Tamaki, H Kyushu Inst Design Fukuoka 8158540 Japan Kyoto Univ Sch Informat Kyoto 6068501 Japan Toshiba Co Ltd Ctr Res & Dev Syst & Software Res Labs Kawasaki Kanagawa 2108501 Japan Meiji Univ Dept Comp Sci Kawasaki Kanagawa 2148571 Japan

ISBN: (纸本)3540648240

The mesh of buses (MBUS) is a parallel computation model which consists of n x n processors, II row buses and n column buses but no local connections between two neighboring processors. As for deterministic (permutation) routing on MBUSs, the known 1.5n upper bound appears to be hard to improve. Also, the information theoretic lower bound for any type of MBUS routing is 1.0n. In this paper, we present two randomized algorithms for MBUS routing. One of them runs in 1.4375n + o(n) steps with high probability. The other runs 1.25n + o(n) steps also with high probability but needs more local computation. (C) 2001 Elsevier Science B.V. All rights reserved.

关键词： permutation routing mesh of buses randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

randomized methods for higher-order subspace separation 24

Randomized methods for higher-order subspace separation

引用

24th European Signal Processing Conference (EUSIPCO)

作者： da Costa, Michele N. Lopes, Renato R. Romano, Joao Marcos T. Univ Campinas UNICAMP DSPCom Lab Campinas SP Brazil

ISBN: (纸本)9780992862657

This paper presents an algorithm for signal subspace separation in the context of multidimensional data. The proposal is an extension of the randomized Singular Value Decomposition (SVD) for higher-order tensors. From a set derived from random sampling, we construct an orthogonal basis associated with the range of each mode-space of the input data tensor. Multilinear projection of the input data onto each mode-space then transforms the data to a low-dimensional representation. Finally, we compute the Higher-Order Singular Value Decomposition (HOSVD) of the reduced tensor. Furthermore, we propose an algorithm for computing the randomized HOSVD based on the row-extraction technique. The results reveal a relevant improvement from the standpoint of computational complexity.

关键词： higher-order singular value decomposition randomized algorithm signal subspace method tensor decomposition dimension reduction row-extraction technique

来源：评论

学校读者我要写书评

暂无评论

randomized Polynomial Time Identity Testing for Noncommutative Circuits 2017

Randomized Polynomial Time Identity Testing for Noncommutati...

引用

49th Annual ACM-SIGACT Symposium on Theory of Computing (STOC)

作者： Arvind, V. Joglekar, Pushkar S. Mukhopadhyay, Partha Raja, S. Inst Math Sci HBNI Madras Tamil Nadu India Vishwakarma Inst Technol Pune Maharashtra India Chennai Math Inst Madras Tamil Nadu India

In this paper we show that black-box polynomial identity testing for noncommutative polynomials f is an element of F of degree D and sparsity t, can be done in randomized poly(n, log t, log D) time. As a consequence,... 详细信息

ISBN: (纸本)9781450345286

In this paper we show that black-box polynomial identity testing for noncommutative polynomials f is an element of F < z(1), z(2), ... z(n)> of degree D and sparsity t, can be done in randomized poly(n, log t, log D) time. As a consequence, given a circuitC of size s computing a polynomial f is an element of F < z(1), z(2), ...z(n)> with at most t non-zero monomials, then testing if f is identically zero can be done by a randomized algorithm with running time polynomial in s and n and log t. This makes significant progress on a question that has been open for over ten years. Our algorithm is based on automata-theoretic ideas that can efficiently isolate a monomial in the given polynomial. In particular, we carry out the monomial isolation using nondeterministic automata. In general, noncommutative circuits of size s can compute polynomials of degree exponential in s and number of monomials double-exponential in s. In this paper, we consider a natural class of homogeneous noncommutative circuits, that we call +-regular circuits, and give a white-box polynomial time deterministic polynomial identity test. These circuits can compute noncommutative polynomials with number of monomials double-exponential in the circuit size. Our algorithm combines some new structural results for +-regular circuits with known results for noncommutative ABP identity testing, rank bound of commutative depth three identities, and equivalence testing problem for words. Finally, we consider the black-box identity testing problem for depth three +-regular circuits and give a randomized polynomial time identity test. In particular, we show if f 2 F < Z > is a nonzero noncommutative polynomial computed by a depth three +-regular circuit of size s, then f cannot be a polynomial identity for the matrix algebra M-s(F) when F is sufficiently large depending on the degree of f.

关键词： Algebraic Complexity Non-commutative Computation Polynomial Identity Testing randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

A Message-Passing and Adaptive Implementation of the randomized Test-and-Set Object 14

A Message-Passing and Adaptive Implementation of the Randomi...

引用

IEEE 14th International Symposium on Network Computing and Applications NCA

作者： Anceaume, Emmanuelle Castella, Francois Mostefaoui, Achour Sericola, Bruno CNRS IRISA F-75700 Paris France Univ Rennes 1 IRMAR F-35014 Rennes France Univ Nantes LINA F-44035 Nantes France INRIA Rennes Atlantique Rennes France

ISBN: (纸本)9781509018499

This paper presents a solution to the well-known Test-and-Set operation in asynchronous systems prone to process crashes. Test-and-Set is a synchronization operation that, when invoked by a set of processes, returns "yes" to a unique process and returns "no" to all the others. Recently many advances in implementing Test and Set objects have been achieved, however all of them uniquely target the shared memory model. In this paper we propose an implementation of a Test-and-Set object for message passing distributed systems. This implementation can be invoked by any number p of processes. It has an expected step complexity in O(p) and an expected message complexity in O(np), where n is the total number of processes in the system. The proposed Test and Set object is built atop a new basic building block that allows to select a winning group among two groups of processes.

关键词： Test&Set synchronization asynchronous message-passing system crash failures randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

A randomized satisfiability procedure for arithmetic and uninterpreted function symbols

引用

19th International Conference on Automated Deduction (CADE-19)

作者： Gulwani, S Necula, GC Univ Calif Berkeley Dept Comp Sci Berkeley CA 94720 USA

ISBN: (纸本)3540405593

We present a new randomized algorithm for checking the satisfiability of a conjunction of literals in the combined theory of linear equalities and uninterpreted functions. The key idea of the algorithm is to process the literals incrementally and to maintain at all times a set of random variable assignments that satisfy the literals seen so far. We prove that this algorithm is complete (i.e., it identifies all unsatisfiable conjunctions) and is probabilistically sound (i.e., the probability that it fails to identify satisfiable conjunctions is very small). The algorithm has the ability to retract assumptions incrementally with almost no additional space overhead. The algorithm can also be easily adapted to produce proofs for its output. The key advantage of the algorithm is its simplicity. We also show experimentally that the randomized algorithm has performance competitive with the existing deterministic symbolic algorithms. (c) 2005 Elsevier Inc. All rights reserved.

关键词： randomized algorithm satisfiability procedure linear arithmetic uninterpreted function symbols

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：