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

15th Annual International Conference on Computing and Combinatorics (COCOON 2009)

作者： Dantchev, Stefan Friedetzky, Tom Nagel, Lars Univ Durham Dept Comp Sci Durham DH1 3LE England

ISBN: (纸本)9783642028816

We show that a random walk on a tournament on n vertices finds either a sink or a 3-cycle in expected time O(root n . log n . root log*n), that is, sublinear both in the size of the description of the graph as well as in the number of vertices. This result is motivated by the search of a generic algorithm for solving a large class of search problems called Local Search, LS. LS is defined by us as a generalisation of the well-known class PLS.

关键词： sublinear-time algorithms tournament random walk

来源：评论

学校读者我要写书评

暂无评论

TESTING SIMILAR MEANS

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2014年第4期28卷 1699-1724页

作者： Levi, Reut Ron, Dana Rubinfeld, Ronitt Tel Aviv Univ Sch Comp Sci IL-69978 Tel Aviv Israel Tel Aviv Univ Sch Elect Engn IL-69978 Tel Aviv Israel MIT CSAIL Cambridge MA 02139 USA Tel Aviv Univ Blavatnik Sch Comp Sci IL-69978 Tel Aviv Israel

We consider the problem of testing a basic property of collections of distributions: having similar means. Namely, the algorithm should accept collections of distributions in which all distributions have means that do not differ by more than some given parameter and should reject collections that are relatively far from having this property. By "far" we mean that it is necessary to modify the distributions in a relatively significant manner (according to some predetermined distance measure) so as to obtain the property. We study this problem in two models. In the first model (the query model) the algorithm may ask for samples from any distribution of its choice, and in the second model (the sampling model) the distributions from which it gets samples are selected randomly. We provide upper and lower bounds in both models. In particular, in the query model, the complexity of the problem is polynomial in 1/is an element of (where is an element of is the given distance parameter), while in the sampling model, the complexity grows roughly as m(1- poly(is an element of)), where m is the number of distributions.

关键词： sublinear-time algorithms property testing of distributions

来源：评论

学校读者我要写书评

暂无评论

Compressed sensing with sparse binary matrices: Instance optimal error guarantees in near-optimal time

引用

JOURNAL OF COMPLEXITY 2014年第1期30卷 1-15页

作者： Iwen, M. A. Michigan State Univ Dept Math E Lansing MI 48824 USA

A compressed sensing method consists of a rectangular measurement matrix, M is an element of R-mxN with m R-m -> R-N. Compressed sensing methods aim to construct a high quality approximation to any given input vec... 详细信息

A compressed sensing method consists of a rectangular measurement matrix, M is an element of R-mxN with m << N, together with an associated recovery algorithm, A : > R-m -> R-N. Compressed sensing methods aim to construct a high quality approximation to any given input vector X E RN using only Mx is an element of R'n as input. In particular, we focus herein on instance optimal nonlinear approximation error bounds for M and A, of the form parallel to x A (Mx)parallel to <= parallel to x - x(k)(opt)parallel to + Ck(1/p-1/q) parallel to x - x(k)(opt)parallel to for X is an element of RN, where x(k)(opt) is the best possible k-term approximation to x. In this paper we develop a compressed sensing method whose associated recovery algorithm, A, runs in O ((k log k) log N)-time, matching a lower bound up to a O (log k) factor. This runtime is obtained by using a new class of sparse binary compressed sensing matrices of near optimal size in combination with sublinear-time recovery techniques motivated by sketching algorithms for highvolume data streams. The new class of matrices is constructed by randomly subsampling rows from well-chosen incoherent matrix constructions which already have a sub-linear number of rows. As a consequence, fewer random bits than previously required are needed in order to select the rows utilized by the fast reconstruction algorithms considered herein. (C) 2013 Elsevier Inc. All rights reserved.

关键词： Compressed sensing sublinear-time algorithms Sparse matrices

来源：评论

学校读者我要写书评

暂无评论

High-Rate Codes with sublinear-time Decoding

引用

JOURNAL OF THE ACM 2014年第5期61卷 28-28页

作者： Kopparty, Swastik Saraf, Shubhangi Yekhanin, Sergey Inst Adv Study Princeton NJ 08540 USA MIT Cambridge MA 02139 USA Microsoft Res Silicon Valley San Jose CA USA

Locally decodable codes are error-correcting codes that admit efficient decoding algorithms;any bit of the original message can be recovered by looking at only a small number of locations of a corrupted codeword. The tradeoff between the rate of a code and the locality/efficiency of its decoding algorithms has been well studied, and it has widely been suspected that nontrivial locality must come at the price of low rate. A particular setting of potential interest in practice is codes of constant rate. For such codes, decoding algorithms with locality O(k(epsilon)) were known only for codes of rate c(Omega(1/epsilon)), where k is the length of the message. Furthermore, for codes of rate > 1/2, no nontrivial locality had been achieved. In this article, we construct a new family of locally decodable codes that have very efficient local decoding algorithms, and at the same time have rate approaching 1. We show that for every epsilon > 0 and alpha > 0, for infinitely many k, there exists a code C which encodes messages of length k with rate 1 -alpha, and is locally decodable from a constant fraction of errors using O(k(epsilon)) queries and time. These codes, which we call multiplicity codes, are based on evaluating multivariate polynomials and their derivatives. Multiplicity codes extend traditional multivariate polynomial codes;they inherit the local-decodability of these codes, and at the same time achieve better tradeoffs and flexibility in the rate and minimum distance.

关键词： algorithms Reliability Theory Multiplicity codes sublinear-time algorithms locally correctable codes locally decodable codes polynomials derivatives

来源：评论

学校读者我要写书评

暂无评论

COUNTING STARS AND OTHER SMALL SUBGRAPHS IN sublinear-time

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2011年第3期25卷 1365-1411页

作者： Gonen, Mira Ron, Dana Shavitt, Yuval Bar Ilan Univ Dept Math IL-52100 Ramat Gan Israel Tel Aviv Univ Sch Elect Engn Tel Aviv Israel

Detecting and counting the number of copies of certain subgraphs (also known as network motifs or graphlets) is motivated by applications in a variety of areas ranging from biology to the study of the World Wide Web. Several polynomial-time algorithms have been suggested for counting or detecting the number of occurrences of certain network motifs. However, a need for more efficient algorithms arises when the input graph is very large, as is indeed the case in many applications of motif counting. In this paper we design sublinear-time algorithms for approximating the number of copies of certain constant-size subgraphs in a graph G. That is, our algorithms do not read the whole graph, but rather query parts of the graph. Specifically, we consider algorithms that may query the degree of any vertex of their choice and may ask for any neighbor of any vertex of their choice. The main focus of this work is on the basic problem of counting the number of length-2 paths and more generally on counting the number of stars of a certain size. Specifically, we design an algorithm that, given an approximation parameter 0 < epsilon < 1 and query access to a graph G, outputs an estimate (nu) over cap (s) such that with high constant probability, (1 - epsilon)nu(s)(G) <= (nu) over cap (s) <= (1 + epsilon) (nu) over cap (s)(G), where (nu) over cap (s)(G) denotes the number of stars of size s + 1 in the graph. The expected query complexity and running time of the algorithm are O(n/((nu) over cap (s)(G))(1/s+1) + min {(n1-1/s), n(s 1/s)/((nu) over cap (s)(G))(1 1/s)}) . poly(log n, 1/epsilon). We also prove lower bounds showing that this algorithm is tight up to polylogarithmic factors in n and the dependence on.. Our work extends the work of Feige [SIAM J. Comput., 35 (2006), pp. 964-984] and Goldreich and Ron [Random Structures algorithms, 32 (2008), pp. 473-493] on approximating the number of edges (or average degree) in a graph. Combined with these results, our result can be used to

关键词： sublinear-time algorithms approximate counting subgraphs

来源：评论

学校读者我要写书评

暂无评论

High-Rate Codes with sublinear-time Decoding 11

High-Rate Codes with Sublinear-Time Decoding

引用

43rd ACM Symposium on Theory of Computing

作者： Kopparty, Swastik Saraf, Shubhangi Yekhanin, Sergey Institute for Advanced Study Princeton NJ USA MIT Cambridge MA USA Microsoft Research Silicon Valley Mountain View CA USA

ISBN: (纸本)9781450306911

Locally decodable codes are error-correcting codes that admit efficient decoding algorithms;any bit of the original message can be recovered by looking at only a small number of locations of a corrupted codeword. The tradeoff between the rate of a code and the locality/efficiency of its decoding algorithms has been well studied, and it has widely been suspected that nontrivial locality must come at the price of low rate. A particular setting of potential interest in practice is codes of constant rate. For such codes, decoding algorithms with locality O(K-epsilon) were known only for codes of rate exp(1/epsilon), where k is the length of the message. Furthermore, for codes of rate > 1/2, no nontrivial locality has been achieved. In this paper we construct a new family of locally decodable codes that have very efficient local decoding algorithms, and at the same time have rate approaching 1. We show that for every epsilon > 0 and alpha > 0, for infinitely many k, there exists a code C which encodes messages of length k with rate 1 - alpha, and is locally decodable from a constant fraction of errors using O(k(epsilon)) queries and time. The high rate and local decodability are evident even in concrete settings (and not just in asymptotic behavior), giving hope that local decoding techniques may have practical implications. These codes, which we call multiplicity codes, are based on evaluating high degree multivariate polynomials and their derivatives. Multiplicity codes extend traditional multivariate polynomial based codes;they inherit the local-decodability of these codes, and at the same time achieve better tradeoffs and flexibility in their rate and distance.

关键词： Error-correcting codes sublinear-time algorithms locally decodable codes polynomials derivatives multiplicity codes

来源：评论

学校读者我要写书评

暂无评论

A Nearly-Quadratic Gap between Adaptive and Non-adaptive Property Testers (Extended Abstract) 1

引用

22nd International Symposium on algorithms and Computation (ISAAC)

作者： Hurwitz, Jeremy CALTECH Dept Comp & Math Sci Pasadena CA 91125 USA

ISBN: (数字)9783642255915

ISBN: (纸本)9783642255908

We show that for all integers t >= 8 and arbitrarily small epsilon > 0, there exists a graph property Pi (which depends on epsilon) such that epsilon-testing Pi has non-adaptive query complexity Q = (Theta) over tilde (q(2-2/t)), where q = (Theta) over tilde(epsilon(-1)) is the adaptive query complexity. This resolves the question of how beneficial adaptivity is, in the context of proximity-dependent properties. This also gives evidence that the canonical transformation of Goldreich and Trevisan is essentially optimal when converting an adaptive property tester to a non-adaptive property tester. To do so, we provide optimal adaptive and non-adaptive testers for the combined property of having maximum degree O(epsilon N) and being a blow-up collection of an arbitrary base graph H.

关键词： sublinear-time algorithms Property Testing Dense-Graph Model Adaptive vs Non-adaptive Queries Hierarchy Theorem

来源：评论

学校读者我要写书评

暂无评论

Small Space Representations for Metric Min-sum k-Clustering and Their Applications

引用

THEORY OF COMPUTING SYSTEMS 2010年第3期46卷 416-442页

作者： Czumaj, Artur Sohler, Christian Univ Warwick Dept Comp Sci Coventry CV4 7AL W Midlands England Univ Warwick Ctr Discrete Math & Applicat Coventry CV4 7AL W Midlands England TU Dortmund Dept Comp Sci D-44221 Dortmund Germany

The min-sum k-clustering problem is to partition a metric space ( P, d) into k clusters C-1,..., C-k subset of P such that Sigma(k)(i=1) Sigma(p,q is an element of Ci) d(p, q) is minimized. We show the first efficient construction of a coreset for this problem. Our coreset construction is based on a new adaptive sampling algorithm. With our construction of coresets we obtain two main algorithmic results. The first result is a sublinear-time ( 4 + epsilon)-approximation algorithm for the minsum k-clustering problem in metric spaces. The running time of this algorithm is O( n) for any constant k and epsilon, and it is o( n2) for all k = o( log n/ log log n). Since the full description size of the input is Theta(n(2)), this is sublinear in the input size. The fastest previously known o( log n)-factor approximation algorithm for k > 2 achieved a running time of Omega(nk), and no non-trivial o(n(2))-time algorithm was known before. Our second result is the first pass-efficient data streaming algorithm for min-sum k-clustering in the distance oracle model, i.e., an algorithm that uses poly( log n, k) space and makes 2 passes over the input point set, which arrives in form of a data stream in arbitrary order. It computes an implicit representation of a clustering of ( P, d) with cost at most a constant factor larger than that of an optimal partition. Using one further pass, we can assign each point to its corresponding cluster. To develop the coresets, we introduce the concept of alpha-preserving metric embeddings. Such an embedding satisfies properties that the distance between any pair of points does not decrease and the cost of an optimal solution for the considered problem on input ( P, d')is within a constant factor of the optimal solution on input ( P, d). In other words, the goal is to find a metric embedding into a ( structurally simpler) metric space that approximates the original metric up to a factor of a with respect to a given problem. We believe that this con

关键词： sublinear-time algorithms sublinear-space algorithms Clustering Min-sum k-clustering Balanced k-median Streaming algorithms Coresets

来源：评论

学校读者我要写书评

暂无评论

Optimal Testing of Reed-Muller Codes

Optimal Testing of Reed-Muller Codes

引用

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

作者： Bhattacharyya, Arnab Kopparty, Swastik Schoenebeck, Grant Sudan, Madhu Zuckerman, David MIT Comp Sci & Artificial Intelligence Lab 77 Massachusetts Ave Cambridge MA 02139 USA Univ Calif Berkeley Dept Comp Sci Berkeley CA USA Microsoft Res Cambridge MA USA Univ Texas Austin Dept Comp Sci Austin TX USA

ISBN: (纸本)9780769542447

We consider the problem of testing if a given functions f : F-2(n) -> F-2 is close to any degree d polynomial in n variables, also known as the Reed-Muller testing problem. Alon et al . [1] proposed and analyzed a natural 2(d+1)-query test for this problem. this test turned out to be intimately related to the Gowers norm. Alon et. al. showed that this test accepts every degree d polynomial with probability 1, while it rejects functions that are Omega(1)-far with probability Omega(1/(d2(d))). We give an asymptotically optimal analysis of this test, and show that it rejects functions that are (even only) Omega(2(-d))-far with Omega(1)-probability (so the rejection probability is a universal constant independent of d and n). This implies a tight relationship between the (d + 1)(st)-Gowers norm of a function and its maximal correlation with degree d polynomials, when the correlation is close to 1. Our proof works by inductions on n and yields a new analysis of even the classical Blum-Luby-Rubinfeld [2] linearity test, for the setting of functions mapping F-2(n) to F-2. The optimality follows from a tighter analysis of counterexamples to the "inverse conjecture for the Gowers norm" constructed by [3], [4]. Our results has several implications. First, it shows that the Gowers norm test is tolerant, in that it also accepts close codewords. Second, it improves the parameters of an XOR lemma for polynomials given by Viola and Wigderson [5]. Third, it implies a "query hierarchy" result for property testing of affine-invariant properties. That is, for every functions q(n), it gives an affine-invariant property that is testable with O(q(n))-queries, but not with o(q(n))-queries, complementing an analogous result of [6] for graph properties.

关键词： sublinear-time algorithms Property testing Reed-Muller codes Gowers norm Low-degree tests

来源：评论

学校读者我要写书评

暂无评论

Small Space Representations for Metric Min-sum k-Clustering and Their Applications

引用

24th Annual Symposium on Theoretical Aspects of Computer Science

ISBN: (纸本)9783540709176

关键词： sublinear-time algorithms sublinear-space algorithms Clustering Min-sum k-clustering Balanced k-median Streaming algorithms Coresets

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：