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

SIAM JOURNAL ON DISCRETE MATHEMATICS 2011年第4期25卷 1562-1588页

作者： Rubinfeld, Ronitt Shapira, Asaf MIT Comp Sci Artificial Intelligence Lab Cambridge MA 02139 USA Tel Aviv Univ Blavatnik Sch Comp Sci Tel Aviv Israel Tel Aviv Univ Sch Math IL-69978 Tel Aviv Israel Georgia Inst Technol Sch Math & Comp Sci Atlanta GA 30332 USA

sublinear time algorithms represent a new paradigm in computing, where an algorithm must give some sort of an answer after inspecting only a very small portion of the input. We discuss the types of answers that one ca... 详细信息

关键词： sublinear time algorithms approximation algorithms randomized algorithms property testing

来源：评论

学校读者我要写书评

暂无评论

sublinear time algorithms

Sublinear time algorithms

引用

25th International Congress of Mathematicians, ICM 2006

作者： Rubinfeld, Ronitt Computer Science and Artificial Intelligence Laboratory MIT Cambridge MA 02139 United States

关键词： Property testing sublinear time algorithms

来源：评论

学校读者我要写书评

暂无评论

sublinear time ESTIMATION OF DEGREE DISTRIBUTION MOMENTS: THE ARBORICITY CONNECTION

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2019年第4期33卷 2267-2285页

作者： Eden, Talya Ron, Dana Seshadhri, C. Tel Aviv Univ Sch Elect Engn IL-6948105 Tel Aviv Israel Univ Calif Santa Cruz Dept Comp Sci Santa Cruz CA 95064 USA

We revisit the classic problem of estimating the moments of the degree distribution of an undirected simple graph. Consider an undirected simple graph G = (V, E) with n (nonisolated) vertices, and define (for s > 0) M-s = Sigma(v is an element of V) d(v)(s). Our aim is to estimate M-s within a multiplicative error of (1 + epsilon) (for a given approximation parameter epsilon > 0) in sublinear time. We consider the sparse-graph model that allows access to uniform random vertices, queries for the degree of any vertex, and queries for a neighbor of any vertex. For the case of s = 1 (the average degree), O* (root n) queries suffice for any constant epsilon [U. Feige, SIAM J. Comput., 35 (2006), pp. 964-984], [O. Goldreich and D. Ron, Random Structures algorithms, 32 (2008), pp. 473-493]. (We use the O* notation to suppress dependencies in log n and 1/epsilon.) Gonen, Ron, and Shavitt [SIAM J. Discrete Math., 25 (2011), pp. 1365-1411] extended this result to all integral s > 0 by designing an algorithm that performs O* (n(1-1/(s+1))) queries. (Strictly speaking, their algorithm approximates the number of star-subgraphs of a given size, but a slight modification gives an algorithm for moments.) We design a new, significantly simpler algorithm for this problem. In the worst case, it exactly matches the bounds of Gonen, Ron, and Shavitt and has a much simpler proof. More importantly, the running time of this algorithm is connected to the arboricity of G. This is (essentially) the maximum density of an induced subgraph. For the family of graphs with arboricity at most alpha, it has a query complexity of O* (***(1/s) M-s(1/s) + min {m/M-s(1/s), m.n(s-1)/M-s) which is always upper bounded by O* (n alpha/M-s(1/s)). Thus, for the class of constant-arboricity graphs (which includes, among others, all minor-closed families and preferential attachment graphs), we can estimate the average degree in O* (1) queries, and we can estimate the variance of the degree distribution in O*

关键词： sublinear time algorithms degeneracy degree distribution approximation algorithms arboricity degree moments

来源：评论

学校读者我要写书评

暂无评论

sublinear time Low-Rank Approximation of Positive Semidefinite Matrices 58

Sublinear Time Low-Rank Approximation of Positive Semidefini...

引用

58th IEEE Annual Symposium on Foundations of Computer Science (FOCS)

作者： Musco, Cameron Woodruff, David P. MIT 77 Massachusetts Ave Cambridge MA 02139 USA Carnegie Mellon Univ Pittsburgh PA 15213 USA

ISBN: (纸本)9781538634646

We show how to compute a relative-error low-rank approximation to any positive semidefinite (PSD) matrix in sublinear time, i.e., for any n x n PSD matrix A, in (O) over tilde (n . poly(k/epsilon)) time we output a rank-k matrix B, in factored form, for which parallel to A - B parallel to(2)(F) <= (1 + c) parallel to A - A(k)parallel to(2)(F), where A(k) is the best rank-k approximation to A. When k and 1/epsilon are not too large compared to the sparsity of A, our algorithm does not need to read all entries of the matrix. Hence, we significantly improve upon previous nnz(A) time algorithms based on oblivious subspace embeddings, and bypass an nnz(A) time lower bound for general matrices (where nnz(A) denotes the number of non-zero entries in the matrix). We prove time lower bounds for low-rank approximation of PSD matrices, showing that our algorithm is close to optimal. Finally, we extend our techniques to give sublinear time algorithms for low-rank approximation of A in the (often stronger) spectral norm metric parallel to A - B parallel to(2)(2) and for ridge regression on PSD matrices.

关键词： low-rank approximation leverage score sampling sublinear time algorithms matrix sketching

来源：评论

学校读者我要写书评

暂无评论

A sublinear time Algorithm for Opinion Optimization in Directed Social Networks via Edge Recommendation 23

A Sublinear Time Algorithm for Opinion Optimization in Direc...

引用

29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD)

作者： Zhou, Xiaotian Zhu, Liwang Li, Wei Zhang, Zhongzhi Fudan Univ Shanghai Key Lab Intelligent Informat Proc Sch Comp Sci Shanghai 200433 Peoples R China Fudan Univ Res Inst Intelligent Complex Syst Shanghai 200433 Peoples R China Fudan Univ Shanghai Engn Res Inst Blockchain Shanghai 200433 Peoples R China Fudan Univ Acad Engn & Technol Shanghai 200433 Peoples R China

ISBN: (纸本)9798400701030

In this paper, we study the opinion maximization problem for the leader-follower DeGroot model of opinion dynamics in a social network modelled by a directed graph with n nodes, where a small number of nodes are competing leader nodes with binary opposing opinions 0 or 1, and the rest are follower nodes. We address the problem of maximizing the overall opinion by adding k << n new edges, where each edge is incident to a 1-leader and a follower. We prove that the objective function is monotone and submodular, and then propose a deterministic greedy algorithm with an approximation ratio (1 - 1/e) and O(n(3)) running time. We then develop a fast sampling algorithm based on l-truncated absorbing random walks and sample-materialization techniques, which has sublinear time complexity O(kn(1/2)l log(3/2) n/epsilon(3)) for any error parameter epsilon > 0. We provide extensive experiments on real networks to evaluate the performance of our algorithms. The results show that for undirected graphs our fast sampling algorithm outperforms the state-of-the-art method in terms of efficiency and effectiveness. While for directed graphs our fast sampling algorithm is as effective as our deterministic greedy algorithm, both of which are much better than the baseline strategies. Moreover, our fast algorithm is scalable to large directed graphs with over 41 million nodes.

关键词： Social network graph algorithms sublinear time algorithms data mining discrete optimization

来源：评论

学校读者我要写书评

暂无评论

An Adaptive sublinear-time Block Sparse Fourier Transform 2017

An Adaptive Sublinear-Time Block Sparse Fourier Transform

引用

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

作者： Cevher, Volkan Kapralov, Michael Scarlett, Jonathan Zandieh, Amir Ecole Polytech Fed Lausanne Lausanne Switzerland

ISBN: (纸本)9781450345286

The problem of approximately computing the k dominant Fourier coeficients of a vector X quickly, and using few samples in time domain, is known as the Sparse Fourier Transform (sparse FFT) problem. A long line of work on the sparse FFT has resulted in algorithms with O(k logn log(n/k)) runtime [Hassanieh et al., STOC' 12] and O(k logn) sample complexity [Indyk et al., FOCS' 14]. This paper revisits the sparse FFT problem with the added twist that the sparse coeficients approximately obey a (k(0), k(1))-block sparse model. In this model, signal frequencies are clustered in k(0) intervals with width k(1) in Fourier space, and k = k(0)k(1) is the total sparsity. Our main result is the first sparse FFT algorithm for (k(0);k(1))-block sparse signals with a sample complexity of O*(k(0)k(1) + k(0) log(1 + k(0)) log n) at constant signal-to-noise ratios, and sublinear runtime. Our algorithm crucially uses adaptivity to achieve the improved sample complexity bound, and we provide a lower bound showing that this is essential in the Fourier setting: Any non-adaptive algorithm must use Omega(k(0)k(1) log n/k(0) k(1)) samples for the (k(0);k(1))-block sparse model, ruling out improvements over the vanilla sparsity assumption. Our main technical innovation for adaptivity is a new randomized energy-based importance sampling technique that may be of independent interest.

关键词： Sparse Fourier transform sublinear time algorithms adaptive sampling energy-based importance sampling lower bounds

来源：评论

学校读者我要写书评

暂无评论

OPTIMAL TESTING OF MULTIVARIATE POLYNOMIALS OVER SMALL PRIME FIELDS

引用

SIAM JOURNAL ON COMPUTING 2013年第2期42卷 536-562页

作者： Haramaty, Elad Shpilka, Amir Sudan, Madhu Technion Israel Inst Technol Fac Comp Sci Haifa Israel Microsoft Res Cambridge MA 02142 USA

We consider the problem of testing whether a given function f : F-q(n) -> F-q is close to an n-variate degree d polynomial over the finite field F-q of q elements. The natural, low-query test for this property would be to first pick the smallest dimension t = t(q,d) approximate to d/q such that every function of degree greater than d reveals this aspect on some t-dimensional affine subspace of F-q(n). Then, one would test that f when restricted to a random t-dimensional affine subspace is a polynomial of degree at most d on this subspace. Such a test makes only q(t) queries, independent of n. Previous works, by Alon et al. [IEEE Trans. Inform. Theory, 51 (2005), pp. 4032-4039], Kaufman and Ron [SIAM J. Comput., 36 (2006), pp. 779-802], and Jutla et al. [Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, 2004, pp. 423-432], showed that this natural test rejected functions that were Omega(1)-far from degree d-polynomials with probability at least Omega(q(-t)). (The initial work [IEEE Trans. Inform. Theory, 51 (2005), pp. 4032-4039] considered only the case of q = 2, while the work [Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, 2004, pp. 423-432] considered only the case of prime q. The results in [SIAM J. Comput., 36 (2006), pp. 779-802] hold for all fields.) Thus to get a constant probability of detecting functions that are at a constant distance from the space of degree d polynomials, the tests made q(2t) queries. Kaufman and Ron also noted that when q is prime, then q(t) queries are necessary. Thus these tests were off by at least a quadratic factor from known lower bounds. Bhattacharyya et al. [Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science, 2010, pp. 488-497] gave an optimal analysis of this test for the case of the binary field and showed that the natural test actually rejects functions that were Omega(1)-far from degree d-polynomials with probability Omega(1). I

关键词： property testing low-degree polynomials Reed-Muller sublinear time algorithms

来源：评论

学校读者我要写书评

暂无评论

Nearly Optimal Deterministic Algorithm for Sparse Walsh-Hadamard Transform

引用

ACM TRANSACTIONS ON algorithms 2017年第3期13卷 1–36页

作者： Cheraghchi, Mahdi Indyk, Piotr Imperial Coll London Dept Comp London England MIT Comp Sci & Artificial Intelligence Lab Cambridge MA 02139 USA

For every fixed constant alpha > 0, we design an algorithm for computing the k-sparse Walsh-Hadamard transform (i.e., Discrete Fourier Transform over the Boolean cube) of an N-dimensional vector x is an element of R-N in time k(1+alpha) (log N)(O(1)). Specifically;the algorithm is given query access to x and computes a k -sparse (x) over tilde is an element of R-N satisfying parallel to(x) over tilde - (x) over cap parallel to(1) <= parallel to(x) over cap - H-k((x) over cap)parallel to(1) for an absolute constant c > 0, where (x) over cap is the transform of x and H-K(x) over cap is its best k -sparse approximation. Our algorithm is fully deterministic and only uses nonadaptive queries to x (i.e., all queries are determined and performed in parallel when the algorithm starts). An important technical tool that we use is a construction of nearly optimal and linear lossless condensers, which is a careful instantiation of the GUV condenser (Guruswami et al. [2009]). Moreover;we design a deterministic and nonadaptive l(1)/l(1) compressed sensing scheme based on general lossless condensers that is equipped with a fast reconstruction algorithm running in time k(1+alpha)(log N)(O(1)) (for the GUV-based condenser) and is of independent interest. Our scheme significantly simplifies and improves an earlier expander -based construction due to Berinde, Gilbert, Indyk, Karloft;and Strauss [Berinde et al. 2008]. Our methods use linear lossless condensers in a black box fashion;therefore, any future improvement on explicit constructions of such condensers would immediately translate to improved parameters in our framework (potentially leading to k(log N)(O(1)) reconstruction time with a reduced exponent in the poly logarithmic factor, and eliminating the extra parameter alpha). By allowing the algorithm to use randomness while still using nonadaptive queries, the runtime of the algorithm can be improved to O(k log(3) N).

关键词： Sparse recovery sparse Fourier transform explicit constructions pseudorandomness sublinear time algorithms sketching

来源：评论

学校读者我要写书评

暂无评论

On ultrametric 1-median selection

引用

THEORETICAL COMPUTER SCIENCE 2020年 828卷 65-69页

作者： Chang, Ching-Lueh Yuan Ze Univ Dept Comp Sci & Engn Taoyuan Taiwan

Consider the problem of finding a point in a finite ultrametric space with the minimum average distance to all points. We give this problem a Monte Carlo O ((log(2)(1/epsilon))/epsilon(3))-time (1 + epsilon)-approximation algorithm with success probability 1 - 0 (epsilon), for all epsilon > 0. (C) 2020 Elsevier B.V. All rights reserved.

关键词： 1-median selection sublinear time algorithms Ultrametric spaces Metric spaces Closeness centrality

来源：评论

学校读者我要写书评

暂无评论

Non-Abelian homomorphism testing, and distributions close to their self-convolutions

引用

RANDOM STRUCTURES & algorithms 2008年第1期32卷 49-70页

作者： Ben-or, Michael Coppersmith, Don Luby, Mike Rubinfeld, Ronitt MIT Comp Sci & Artificial Intelligence Lab Cambridge MA 02139 USA Digital Fountain Fremont CA 94538 USA IDA CCR Princeton NJ 08540 USA Hebrew Univ Jerusalem Sch Engn & Comp Sci IL-91904 Jerusalem Israel

In this paper, we Study two questions related to the problem of testing whether a function is close to a homomorphism. For two finite groups G,H (not necessarily Abelian), an arbitrary map f : G -> H, and a parameter 0 < is an element of < 1, say that f is is an element of-close to a homomorphism if there is some homomorphism g such that g and f differ on at most is an element of vertical bar G vertical bar elements of G, and say that f is is an element of-far otherwise. For a given f and is an element of, a homomorphism tester should distinguish whether f is a homomorphism, or if f is is an element of-far from a homornorphism. When G is Abelian, it was known that the test which picks O(1/is an element of) random pairs x,y and tests that f (x) + f (y) = f (x + y) gives a homomorphism tester. Our first result shows that such a test works for all groups G. Next, we consider functions that are close to their self-convolutions. Let A = (ag vertical bar g is an element of G) be a distribution on G. The self-convolution of A, A' = (a(g)'vertical bar g is an element of G), is defined by a(x)' = Sigma a(y)a(z). y,z is an element of G;yz=x It is known that A = A' exactly when A is the uniform distribution over a subgroup of G. We show that there is a sense in which this characterization is robust-that is, if A is close in statistical distance to A', then A must be close to uniform over some subgroup of G. Finally, we show a relationship between the question of testing whether a function is close to a homomorphism via the above test and the question of characterizing functions that are close to their self-convolutions. (c) 2007 Wiley Periodicals, Inc.

关键词： sublinear time algorithms linearity testing convolutions of distributions

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：