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

sublinear-time algorithms for tournament graphs

JOURNAL OF COMBINATORIAL OPTIMIZATION 2011年第3期22卷 469-481页

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

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 nlogn root log*n), that is, sublinear both in the size of the description of the graph as well as in th... 详细信息

关键词： sublinear-time algorithms Tournament Random walk

来源：评论

学校读者我要写书评

暂无评论

sublinear-time algorithms for Counting Star Subgraphs via Edge Sampling

引用

ALGORITHMICA 2018年第2期80卷 668-697页

作者： Aliakbarpour, Maryam Biswas, Amartya Shankha Gouleakis, Themis Peebles, John Rubinfeld, Ronitt Yodpinyanee, Anak MIT CSAIL 77 Massachusetts Ave Cambridge MA 02139 USA Tel Aviv Univ Blavatnik Sch Comp Sci Tel Aviv Israel

We study the problem of estimating the value of sums of the form when one has the ability to sample with probability proportional to its magnitude. When , this problem is equivalent to estimating the selectivity of a self-join query in database systems when one can sample rows randomly. We also study the special case when is the degree sequence of a graph, which corresponds to counting the number of p-stars in a graph when one has the ability to sample edges randomly. Our algorithm for a -multiplicative approximation of has query and time complexities . Here, is the number of edges in the graph, or equivalently, half the number of records in the database table. Similarly, n is the number of vertices in the graph and the number of unique values in the database table. We also provide tight lower bounds (up to polylogarithmic factors) in almost all cases, even when is a degree sequence and one is allowed to use the structure of the graph to try to get a better estimate. We are not aware of any prior lower bounds on the problem of join selectivity estimation. For the graph problem, prior work which assumed the ability to sample only vertices uniformly gave algorithms with matching lower bounds (Gonen et al. in SIAM J Comput 25:1365-1411, 2011). With the ability to sample edges randomly, we show that one can achieve faster algorithms for approximating the number of star subgraphs, bypassing the lower bounds in this prior work. For example, in the regime where , and , our upper bound is , in contrast to their lower bound when no random edge queries are available. In addition, we consider the problem of counting the number of directed paths of length two when the graph is directed. This problem is equivalent to estimating the selectivity of a join query between two distinct tables. We prove that the general version of this problem cannot be solved in sublinear time. However, when the ratio between in-degree and out-degree is bounded-or equivalently, when the ratio between

关键词： Subgraphs Approximate counting Randomized algorithms sublinear-time algorithms

来源：评论

学校读者我要写书评

暂无评论

sublinear-time algorithms for Compressive Phase Retrieval

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2020年第11期66卷 7302-7310页

作者： Li, Yi Nakos, Vasileios Nanyang Technol Univ Sch Phys & Math Sci Singapore 637371 Singapore Saarland Univ D-66123 Saarbrucken Germany

In the problem of compressed phase retrieval, the goal is to reconstruct a sparse or approximately k-sparse vector x epsilon C-n given access to y = | phi x|, where |v| denotes the vector obtained from taking the absolute value of v epsilon Cn coordinate-wise. In this paper we present sublinear-time algorithms for a few for-each variants of the compressive phase retrieval problem which are akin to the variants considered for the classical compressive sensing problem in theoretical computer science. Our algorithms use pure combinatorial techniques and near-optimal number of measurements.

关键词： Signal processing algorithms Phase measurement time measurement Decoding Approximation algorithms Compressed sensing Computer science Phase retrieval compressive sensing sparse recovery sublinear-time algorithms combinatorial algorithms

来源：评论

学校读者我要写书评

暂无评论

sublinear-time algorithms for Tournament Graphs

Sublinear-Time Algorithms for Tournament Graphs

引用

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

来源：评论

学校读者我要写书评

暂无评论

Sparse Harmonic Transforms: A New Class of sublinear-time algorithms for Learning Functions of Many Variables

引用

FOUNDATIONS OF COMPUTATIONAL MATHEMATICS 2021年第2期21卷 275-329页

作者： Choi, Bosu Iwen, Mark A. Krahmer, Felix UT Austin Oden Inst Computat Engn & Sci Austin TX 78712 USA Michigan State Univ Dept Math E Lansing MI 48824 USA Michigan State Univ Dept Computat Math Sci & Engn CMSE E Lansing MI 48824 USA Tech Univ Munich Dept Math Munich Germany

In this paper we develop fast and memory efficient numerical methods for learning functions of many variables that admit sparse representations in terms of general bounded orthonormal tensor product bases. Such functions appear in many applications including, e.g., various Uncertainty Quantification (UQ) problems involving the solution of parametric PDE that are approximately sparse in Chebyshev or Legendre product bases (Chkifa et al. in Polynomial approximation via compressed sensing of high-dimensional functions on lower sets., 2016;Rauhut and Schwab in Math Comput 86(304):661-700, 2017). We expect that our results provide a starting point for a new line of research on sublinear-time solution techniques for UQ applications of the type above which will eventually be able to scale to significantly higher-dimensional problems than what are currently computationally feasible. More concretely, let B be a finite Bounded Orthonormal Product Basis (BOPB) of cardinality vertical bar B vertical bar = N. Herein we will develop methods that rapidly approximate any functionfthat is sparse in the BOPB, that is,f: D subset of R-D -> C of the form f(x)= Sigma(b is an element of S) c(b)center dot b(x) with S subset of B of cardinality vertical bar S vertical bar = s << N. Our method adapts the CoSaMP algorithm (Needell and Tropp in Appl Comput Harmon Anal 26(3):301-321, 2009) to use additional function samples fromfalong a randomly constructed grid G subset of R-D with universal approximation properties in order to rapidly identify the multi-indices of the most dominant basis functions in S component by component during each CoSaMP iteration. It has a runtime of just(slogN)O(1), uses only(slogN)O(1) function evaluations on the fixed and nonadaptive grid G, and requires not more than(slogN)O(1) bits of memory. We emphasize that nothing about S or any of the coefficientscb is an element of Cis assumed in advance other than that S subset of B has |S| <= s. Both S and its related coe

关键词： High-dimensional function approximation sublinear-time algorithms Function learning Sparse approximation Compressive sensing

来源：评论

学校读者我要写书评

暂无评论

sublinear time algorithms for Earth Mover's Distance

引用

THEORY OF COMPUTING SYSTEMS 2011年第2期48卷 428-442页

作者： Do Ba, Khanh Nguyen, Huy L. Nguyen, Huy N. Rubinfeld, Ronitt MIT CSAIL Cambridge MA 02139 USA

We study the problem of estimating the Earth Mover's Distance (EMD) between probability distributions when given access only to samples of the distribution. We give closeness testers and additive-error estimators over domains in [0,1] (d) , with sample complexities independent of domain size-permitting the testability even of continuous distributions over infinite domains. Instead, our algorithms depend on the dimension of the domain space and the quality of the result required. We also prove lower bounds for closeness testing, showing the dependencies on these parameters to be essentially optimal. Additionally, we consider whether natural classes of distributions exist for which there are algorithms with better dependence on the dimension, and show that for highly clusterable data, this is indeed the case. Lastly, we consider a variant of the EMD, defined over tree metrics instead of the usual a"" (1) metric, and give tight upper and lower bounds.

关键词： sublinear-time algorithms Property testing Earth Mover's Distance

来源：评论

学校读者我要写书评

暂无评论

Quantum Meets Fine-Grained Complexity: sublinear time Quantum algorithms for String Problems

引用

ALGORITHMICA 2023年第5期85卷 1251-1286页

作者： Le Gall, Francois Seddighin, Saeed Nagoya Univ Grad Sch Math Chikusa Ku Furocho Nagoya Aichi 4648602 Japan Toyota Technol Inst Chicago 6045 S Kenwood Ave Chicago IL 60637 USA

Longest common substring (LCS), longest palindrome substring (LPS), and Ulam distance (UL) are three fundamental string problems that can be classically solved in near linear time. In this work, we present sublinear time quantum algorithms for these problems along with quantum lower bounds. Our results shed light on a very surprising fact: Although the classic solutions for LCS and LPS are almost identical (via suffix trees), their quantum computational complexities are different. While we give an exact o (root n) time algoritham for LPS, we prove that LCS needs at least time omega(sic) (n(2/3 )) even for 0/1 strings.

关键词： String algorithms Quantum algorithms sublinear-time algorithms Fine-grained complexity

来源：评论

学校读者我要写书评

暂无评论

sublinear time algorithms for the Sparse Recovery Problem

Sublinear Time Algorithms for the Sparse Recovery Problem

引用

作者： Li, Yi University of Michigan

学位级别：doctor

In the sparse recovery problem, we have a signal x in R^N that is sparse; i.e., it consists of k significant entries (heavy hitters) while the rest of the entries are essentially negligible. Let x_[k] in R^N consist of the k largest coefficients (in magnitude, i.e., absolute value) of x, zeroing out all other entries. We want to recover x_[k], the positions and values of only the heavy hitters, as the rest of the signal is not of interest. The Fourier case of this problem concerns the signal with a sparse Fourier transform and asks to recover the significant frequencies and the corresponding coefficients. This thesis investigates two cases of the sparse recovery problem of different error metrics and a generalization of the Fourier case that allows the frequencies to be real numbers instead of lattice points

关键词： sublinear-time algorithms Sparse Recovery Problem Off-the-Grid Fourier Sampling Computer Science Engineering

来源：评论

学校读者我要写书评

暂无评论

sublinear Computation Paradigm: Constant-time algorithms and sublinear Progressive algorithms

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2022年第3期E105A卷 131-141页

作者： Chiba, Kyohei Ito, Hiro Univ Electrocommun Sch Informat & Engn Chofu Tokyo 1828585 Japan

The challenges posed by big data in the 21st Century are complex: Under the previous common sense, we considered that polynomial-time algorithms are practical;however, when we handle big data, even a linear-time algorithm may be too slow. Thus, sublinear- and constant-time algorithms are required. The academic research project, "Foundations of Innovative algorithms for Big Data," which was started in 2014 and will finish in September 2021, aimed at developing various techniques and frameworks to design algorithms for big data. In this project, we introduce a "sublinear Computation Paradigm." Toward this purpose, we first provide a survey of constant-time algorithms, which are the most investigated framework of this area, and then present our recent results on sublinear progressive algorithms. A sublinear progressive algorithm first outputs a temporary approximate solution in constant time, and then suggests better solutions gradually in sublinear-time, finally finds the exact solution. We present sublinear Progressive Algorithm Theory (SPA Theory, for short), which enables to make a sublinear progressive algorithm for any property if it has a constant-time algorithm and an exact algorithm (an exponential-time one is allowed) without losing any computation time in the big-O sense.

关键词： sublinear computation paradigm big data sublinear-time algorithms constant-time algorithms tester progressive algorithms

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：