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

sublinear Random Access Generators for Preferential Attachment Graphs

ACM TRANSACTIONS ON algorithms 2021年第4期17卷 1–26页

作者： Even, Guy Levi, Reut Medina, Moti Rosen, Adi Tel Aviv Univ IL-69978 Tel Aviv Israel Interdisciplinary Ctr Herzliya IDC POB 167 IL-46150 Herzliyya Israel Bar Ilan Univ Fac Engn IL-5290002 Ramat Gan Israel CNRS F-75205 Paris 13 France Univ Paris F-75205 Paris 13 France

We consider the problem of sampling from a distribution on graphs, specifically when the distribution is defined by an evolving graph model, and consider the time, space, and randomness complexities of such samplers. In the standard approach, the whole graph is chosen randomly according to the randomized evolving process, stored in full, and then queries on the sampled graph are answered by simply accessing the stored graph. This may require prohibitive amounts of time, space, and random bits, especially when only a small number of queries are actually issued. Instead, we propose a setting where one generates parts of the sampled graph on-the-fly, in response to queries, and therefore requires amounts of time, space, and random bits that are a function of the actual number of queries. Yet, the responses to the queries correspond to a graph sampled from the distribution in question. Within this framework, we focus on two random graph models: the Barabasi-Albert Preferential Attachment model (BA-graphs) (Science, 286 (5439):509-512) (for the special case of out-degree 1) and the random recursive tree model (Theory of Probability and Mathematical Statistics, (51):1-28). We give on-the-fly generation algorithms for both models. With probability 1 - 1/poly(n), each and every query is answered in polylog(n) time, and the increase in space and the number of random bits consumed by any single query are both polylog(n), where n denotes the number of vertices in the graph. Our work thus proposes a new approach for the access to huge graphs sampled from a given distribution, and our results show that, although the BA random graph model is defined by a sequential process, efficient random access to the graph's nodes is possible. In addition to the conceptual contribution, efficient on-the-fly generation of random graphs can serve as a tool for the efficient simulation of sublinear algorithms over large BA-graphs, and the efficient estimation of their on such graphs.

关键词： Random Graph Generator preferential attachment graphs local computation algorithms sublinear algorithms

来源：评论

学校读者我要写书评

暂无评论

sublinear approximation of signals

Sublinear approximation of signals

引用

Conference on Intelligent Integrated Microsystems

作者： Gilbert, Anna C. Strauss, Martin J. Tropp, Joel A. Vershynin, Roman Univ Michigan Dept Math Ann Arbor MI 48109 USA Univ Michigan Dept Elect Engn Ann Arbor MI 48109 USA Univ Calif Davis Dept Math Davis CA 95616 USA

ISBN: (纸本)0819462888

It has recently been observed that sparse and compressible signals call be sketched using very few nonadaptive linear measurements in comparison with the length of the signal. This sketch can be viewed as an embedding of an entire class of compressible signals into a low-dimensional space. In particular, d-dimensional signals with m nonzero entries (m-sparse signals) can be embedded in O(m log d) dimensions. To date, most algorithms for approximating or reconstructing the signal from the sketch, such as the linear programming approach proposed by Candes-Tao and Donoho, require time polynomial in the signal length. This paper develops a new method, called Chaining Pursuit, for sketching both m-sparse and compressible signals with O(m polylog d) nonadaptive linear measurements. The algorithm can reconstruct the original signal in time O(m polylog d) with an error proportional to the optimal m-term approximation error. In particular, m-sparse signals are recovered perfectly and compressible signals are recovered with polylogarithmic distortion. Moreover, the algorithm can operate in small space O(m polylog d), so it is appropriate for streaming data.

关键词： approximation embedding group testing sketching sparse approximation sublinear algorithms

来源：评论

学校读者我要写书评

暂无评论

Sparse Fourier Transform in Any Constant Dimension with Nearly-Optimal Sample Complexity in sublinear Time 16

Sparse Fourier Transform in Any Constant Dimension with Near...

引用

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

作者： Kapralov, Michael Ecole Polytech Fed Lausanne Lausanne Switzerland

ISBN: (纸本)9781450341325

We consider the problem of computing a k-sparse approximation to the Fourier transform of a length N signal. Our main result is a randomized algorithm for computing such an approximation (i.e. achieving l(2)/l(2) sparse recovery guarantees using Fourier measurements) using O-d (k log N log log N) samples of the signal in time domain and O-d (k log(d+3) N) runtime, where d >= 1 is the dimensionality of the Fourier transform. The sample complexity matches the Omega(k log(N/k)) lower bound for non-adaptive algorithms due to Do Ba et al (SODA'10) for any k <= N1-delta for a constant delta > 0 up to an O(log log N) factor. Prior to our work a result with comparable sample complexity k log N log(O(1)) log N and sublinear runtime was known for the Fourier transform on the line, but for any dimension d >= 2 previously known techniques either suffered from a poly (log N) factor loss in sample complexity or required Omega(N) runtime.

关键词： sublinear algorithms Sparse Fourier Transform

来源：评论

学校读者我要写书评

暂无评论

Spanning Adjacency Oracles in sublinear Time 15

Spanning Adjacency Oracles in Sublinear Time

引用

15th Innovations in Theoretical Computer Science Conference (ITCS)

作者： Bodwin, Greg Fleischmann, Henry Univ Michigan Dept Elect Engn & Comp Sci Ann Arbor MI 48109 USA Univ Cambridge Dept Pure Math & Math Stat Cambridge England

ISBN: (纸本)9783959773096

Suppose we are given an n-node, m-edge input graph G, and the goal is to compute a spanning subgraph H on O(n) edges. This can be achieved in linear O(m + n) time via breadth-first search. But can we hope for sublinear runtime in some range of parameters - for example, perhaps O(n(1.9)) worst-case runtime, even when the input graph has n(2) edges? If the goal is to return H as an adjacency list, there are simple lower bounds showing that Omega(m + n) runtime is necessary. If the goal is to return H as an adjacency matrix, then we need Omega(n(2)) time just to write down the entries of the output matrix. However, we show that neither of these lower bounds still apply if instead the goal is to return H as an implicit adjacency matrix, which we call an adjacency oracle. An adjacency oracle is a data structure that gives a user the illusion that an adjacency matrix has been computed: it accepts edge queries (u, v), and it returns in near-constant time a bit indicating whether or not (u, v)is an element of E(H). Our main result is that, for any 0 < epsilon < 1, one can construct an adjacency oracle for a spanning subgraph on at most (1 + epsilon) n edges, in (O) over tilde (n epsilon(-1)) time (hence sublinear time on input graphs with m >> n edges), and that this construction time is near-optimal. Additional results include constructions of adjacency oracles for k-connectivity certificates and spanners, which are similarly sublinear on dense-enough input graphs. Our adjacency oracles are closely related to Local Computation algorithms (LCAs) for graph sparsifiers;they can be viewed as LCAs with some computation moved to a preprocessing step, in order to speed up queries. Our oracles imply the first LCAs for computing sparse spanning subgraphs of general input graphs in (O) over tilde (n) query time, which works by constructing our adjacency oracle, querying it once, and then throwing the rest of the oracle away. This addresses an open problem of Rubinfeld [CSR '17].

关键词： Graph algorithms sublinear algorithms Data structures Graph theory

来源：评论

学校读者我要写书评

暂无评论

Almost-Optimal sublinear-Time Edit Distance in the Low Distance Regime 2022

Almost-Optimal Sublinear-Time Edit Distance in the Low Dista...

引用

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

作者： Bringmann, Karl Cassis, Alejandro Fischer, Nick Nakos, Vasileios Saarland Univ Max Planck Inst Informat Saarbrucken Germany RelationalAI Berkeley CA USA

ISBN: (纸本)9781450392648

We revisit the task of computing the edit distance in sublinear time. In the (k, K)-gap edit distance problem we are given oracle access to two strings of length n and the task is to distinguish whether their edit distance is at most k or at least K. It has been established by Goldenberg, Krauthgamer and Saha (FOCS '19), with improvements by Kociumaka and Saha (FOCS '20), that the (k, k(2))-gap problem can be solved in time (O) over tilde (n/ k + poly(k)). One of the most natural questions in this line of research is whether the (k, k(2))-gap is best-possible for the running time (O) over tilde (n/ k + poly(k)). In this work we answer this question by significantly improving the gap. Specifically, we show that in time O(n/ k + poly(k)) we can even solve the (k, k(1+o(1)))-gap problem. This is the first algorithm that breaks the (k, k(2))-gap in this running time. Our algorithm is almost optimal in the following sense: In the low distance regime (k <= n(0.19)) our running time becomes O(n/ k), which matches a known n/k(1+o (1) )lower bound for the (k, k(1+o (1)))-gap problem up to lower order factors. Our result also reveals a surprising similarity of Hamming distance and edit distance in the low distance regime: For both, the (k, k(1+o (1)))-gap problem has time complexity n/k(1+o (1)) for small k. In contrast to previous work, which employed a subsampled variant of the Landau-Vishkin algorithm, we instead build upon the algorithm of Andoni, Krauthgamer and Onak (FOCS '10) which approximates the edit distance in almost-linear time O(n(1+epsilon)) within a polylogarithmic factor. We first simplify their approach and then show how to to effectively prune their computation tree in order to obtain a sublinear-time algorithm in the given time bound. Towards that, we use a variety of structural insights on the (local and global) patterns that can emerge during this process and design appropriate property testers to effectively detect these patterns.

关键词： Edit Distance sublinear algorithms Precision Sampling

来源：评论

学校读者我要写书评

暂无评论

Achieving sublinear Complexity under Constant T in T-interval Dynamic Networks 22

Achieving Sublinear Complexity under Constant T in T-interva...

引用

34th ACM Symposium on Parallelism in algorithms and Architectures (SPAA)

作者： Hou, Ruomu Jahja, Irvan Sun, Yucheng Wu, Jiyan Yu, Haifeng Natl Univ Singapore Singapore Singapore

ISBN: (纸本)9781450391467

This paper considers standard T-interval dynamic networks, where the N nodes in the network proceed in lock-step rounds, and where the topology of the network can change arbitrarily from round to round, as determined by an adversary. The adversary promises that in every T consecutive rounds, the T (potentially different) topologies in those.. rounds contain a common connected subgraph that spans all nodes. Within such a context, we propose novel algorithms for solving some fundamental distributed computing problems such as Count/Consensus/Max. Our algorithms are the first algorithms whose complexities do not contain an Omega(N) term, under constant T values. Previous sublinear algorithms require significantly larger T values.

关键词： distributed algorithms T-interval dynamic networks sublinear algorithms

来源：评论

学校读者我要写书评

暂无评论

Brief Announcement: On Approximating PageRank Locally with sublinear Query Complexity 18

Brief Announcement: On Approximating PageRank Locally with S...

引用

30th ACM Symposium on Parallelism in algorithms and Architectures (SPAA)

作者： Bressan, Marco Peserico, Enoch Pretto, Luca Sapienza Univ Roma Rome Italy Univ Padua Padua Italy

ISBN: (纸本)9781450357999

Can one compute the PageRank score of a single, arbitrary node in a graph, exploring only a vanishing fraction of the graph? We provide a positive answer to this extensively researched open question. We develop the first algorithm that, for any n -node graph, returns a multiplicative (1 c) -approximation of the score of any given node with probability (1-6), using at most 0 (n2I3 how 3 in(1i 6)2/3 6-2/3) = O(n213) queries which return either a node chosen uniformly at random, or the list of neighbours of a given node. Alternatively, we show that the same guarantees can be attained by fetching at most 0 (E4/5c/-315 111(01/5 ino /6)3/5 6-6/5) = (E4/5) arcs, where E is the total number of arcs in the graph and d is its average degree.

关键词： PageRank query complexity local computation sublinear algorithms random walks

来源：评论

学校读者我要写书评

暂无评论

Interactive Proofs of Proximity: Delegating Computation in sublinear Time 13

Interactive Proofs of Proximity: Delegating Computation in S...

引用

45th Annual ACM Symposium on the Theory of Computing (STOC)

作者： Rothblum, Guy N. Vadhan, Salil Wigderson, Avi Microsoft Res Redmond WA USA Harvard Univ Ctr Res Computat & Soc Cambridge MA 02138 USA Harvard Univ Sch Engn & Appl Sci Cambridge MA 02138 USA Inst Adv Study Princeton NJ 08540 USA

ISBN: (纸本)9781450320290

We study interactive proofs with sublinear-time verifiers. These proof systems can be used to ensure approximate correctness for the results of computations delegated to an untrusted server. Following the literature on property testing, we seek proof systems where with high probability the verifier accepts every input in the language, and rejects every input that is far from the language. The verifier's query complexity (and computation complexity), as well as the communication, should all be sublinear. We call such a proof system an Interactive Proof of Proximity (IPP). " On the positive side, our main result is that all languages in NC have Interactive Proofs of Proximity with roughly \Fn query and communication and complexities, and polylog(n) communication rounds. This is achieved by identifying a natural language, membership in an affine subspace (for a structured class of subspaces), that is complete for constructing interactive proofs of proximity, and providing efficient protocols for it. In building an IPP for this complete language, we show a tradeoff between the query and communication complexity and the number of rounds. For example, we give a 2 -round protocol with roughly n3/4 queries and communication. " On the negative side, we show that there exist natural languages in NCI-, for which the sum of queries and communication in any constant-round interactive proof of proximity must be polynomially related to n. In particular, for any 2 -round protocol, the sum of queries and communication must be at least S2( \/7n). Finally, we construct much better IPPs for specific functions, such as bipartiteness on random or wellmixing graphs, and the majority function. The query complexities of these protocols are provably better (by exponential or polynomial factors) than what is possible in the standard property testing model, i.e. without a prover.

关键词： Interactive Proofs sublinear algorithms

来源：评论

学校读者我要写书评

暂无评论

sublinear Optimization for Machine Learning

Sublinear Optimization for Machine Learning

引用

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

作者： Clarkson, Kenneth L. Hazan, Elad Woodruff, David P. IBM Almaden Res Ctr San Jose CA 95120 USA Technion Israel Inst Technol Dept Ind Engn IL-32000 Haifa Israel

ISBN: (纸本)9780769542447

We give sublinear-time approximation algorithms for some optimization problems arising in machine learning, such as training linear classifiers and finding minimum enclosing balls. Our algorithms can be extended to some kernelized versions of these problems, such as SVDD, hard margin SVM, and L-2-SVM, for which sublinear-time algorithms were not known before. These new algorithms use a combination of a novel sampling techniques and a new multiplicative update algorithm. We give lower bounds which show the running times of many of our algorithms to be nearly best possible in the unit-cost RAM model. We also give implementations of our algorithms in the semi-streaming setting, obtaining the first low pass polylogarithmic space and sublinear time algorithms achieving arbitrary approximation factor.

关键词： SVM arbitrary approximation factor classification computational complexity learning (artificial intelligence) linear classifier machine learning machine learning multiplicative update algorithm optimisation optimization pattern classification polylogarithmic space polynomial approximation sampling technique sublinear algorithms sublinear optimization sublinear time approximation support vector machine support vector machines

来源：评论

学校读者我要写书评

暂无评论

sublinear Graph Augmentation for Fast Query Implementation 16th

Sublinear Graph Augmentation for Fast Query Implementation

引用

16th International Workshop on Approximation and Online algorithms (WAOA)

作者： Czumaj, Artur Mansour, Yishay Vardi, Shai Univ Warwick Coventry W Midlands England Tel Aviv Univ Tel Aviv Israel Purdue Univ W Lafayette IN 47907 USA

ISBN: (纸本)9783030046934;9783030046927

We introduce the problem of augmenting graphs with sublinear memory in order to speed up replies to queries. As a concrete example, we focus on the following problem: the input is an (unpartitioned) bipartite graph G = (V, E). Given a query q is an element of V, the algorithm's goal is to output q's color in some legal 2-coloring of G, using few probes to the graph. All replies have to be consistent with the same 2-coloring. We show that if a linear amount of preprocessing is allowed, there is a randomized algorithm that, for any alpha, uses (m/alpha) probes and (O) over tilde(alpha) memory, where m is the number of edges in the graph. On the negative side, we show that for a natural family of algorithms that we call probe-first local computation algorithms, this trade-off is optimal even with unbounded preprocessing. We describe a randomized algorithm that replies to queries using (O) over tilde (root n/Phi(2)) probes with no additional memory on regular graphs with conductance Phi (n is the number of vertices in G). In contrast, we show that any deterministic algorithm for regular graphs that uses no memory augmentation requires a linear (in n) number of probes, even if the conductance is the largest possible. We give an algorithm for grids and tori that uses a sublinear number of probes and no memory. Last, we give an algorithm for trees that errs on a sublinear number of edges (i.e., a sublinear number of edges are monochromatic under this coloring) that uses sublinear preprocessing, memory and probes per query.

关键词： sublinear algorithms Graph augmentation Local computation algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：