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

Approximating the distance to monotonicity of Boolean functions

RANDOM STRUCTURES & algorithms 2022年第2期60卷 233-260页

作者： Pallavoor, Ramesh Krishnan S. Raskhodnikova, Sofya Waingarten, Erik Boston Univ Dept Comp Sci 111 Cummington St Boston MA 02215 USA Columbia Univ Dept Comp Sci New York NY 10027 USA

We design a nonadaptive algorithm that, given oracle access to a function f:{0,1}(n) -> {0,1} which is alpha-far from monotone, makes poly(n,1/alpha) queries and returns an estimate that, with high probability, is an (O) over tilde(root n)-approximation to the distance of f to monotonicity. The analysis of our algorithm relies on an improvement to the directed isoperimetric inequality of Khot, Minzer, and Safra (SIAM J. Comput., 2018). Furthermore, we rule out a poly(n,1/alpha)-query nonadaptive algorithm that approximates the distance to monotonicity significantly better by showing that, for all constant kappa>0, every nonadaptive n(1/2-kappa)-approximation algorithm for this problem requires 2(n kappa) queries. This answers a question of Seshadhri (Property Testing Review, 2014) for the case of nonadaptive algorithms. We obtain our lower bound by proving an analogous bound for erasure-resilient (and tolerant) testers. Our method also yields the same lower bounds for unateness and being a k-junta.

关键词： analysis of Boolean functions property testing sublinear algorithms tolerant and erasure-resilient testing

来源：评论

学校读者我要写书评

暂无评论

Testing Monotone High-Dimensional Distributions

引用

RANDOM STRUCTURES & algorithms 2009年第1期34卷 24-44页

作者： Rubinfeld, Ronitt Servedio, Rocco A. Columbia Univ Dept Comp Sci New York NY 10027 USA MIT Comp Sci & Artificial Intelligence Lab Cambridge MA 02139 USA

A monotonedistribution Pover a (partially) ordered domain has P(y) >= P(x) if y >= x in the order. We study several natural Problems of testing properties of monotone distributions over the n-dimensional Boolean cube, given access to random draws front the distribution being tested. We give a poly(n)-time algorithm for testing whether a monotone distribution is equivalent to or C-far (in the L, norm) from the uniform distribution. A key ingredient of the algorithm is a generalization of a known isoperimetric inequality for the Boolean cube. We also introduce a method for proving lower bounds on testing monotone distributions over the n-dimensional Boolean cube. based on a new decomposition technique for monotone distributions. We use this method to show that Our uniformity testing algorithm is optimal LIP to polylog(n) factors. and also to give exponential lower bounds on the complexity of several other problems (testing whether a monotone distribution is identical to or is an element of-far from I fixed known monotone product distribution and approximating the entropy of an unknown monotone distribution). (c) 2008 Wiley Periodicals. Inc. Random Struct. Alg., 34. 24-44, 2009

关键词： sublinear algorithms property testing distribution testing monotone distributions

来源：评论

学校读者我要写书评

暂无评论

ESTIMATING THE LONGEST INCREASING SEQUENCE IN POLYLOGARITHMIC TIME

引用

SIAM JOURNAL ON COMPUTING 2017年第2期46卷 774-823页

作者： Saks, M. Seshadhri, C. Rutgers State Univ Dept Math Piscataway NJ 08854 USA Univ Calif Santa Cruz Dept Comp Sci Santa Cruz CA 95064 USA

Finding the length of the longest increasing subsequence (LIS) is a classic algorithmic problem. Let n denote the size of the array. Simple O(n log n) algorithms are known for this problem. We develop a polylogarithmic time randomized algorithm that for any constant delta > 0, estimates the length of the LIS of an array to within an additive error of delta n. More precisely, the running time of the algorithm is (log n)(c)(1/delta)(O(1/delta)), where the exponent c is independent of delta. Previously, the best known polylogarithmic time algorithms could only achieve an additive n/2 approximation. With a suitable choice of parameters, our algorithm also gives, for any fixed tau > 0, a multiplicative (1 + tau)-approximation to the distance to monotonicity epsilon(f) (the fraction of entries not in the LIS), whose running time is polynomial in log(n) and 1/epsilon(f). The best previously known algorithm could only guarantee an approximation within a factor (arbitrarily close to) 2.

关键词： longest increasing sequence sublinear algorithms property testing

来源：评论

学校读者我要写书评

暂无评论

Approximating the weight of the Euclidean minimum spanning tree in sublinear time

引用

SIAM JOURNAL ON COMPUTING 2005年第1期35卷 91-109页

作者： Czumaj, A Ergün, F Fortnow, L Magen, A Newman, I Rubinfeld, R Sohler, C New Jersey Inst Technol Dept Comp Sci Newark NJ 07102 USA Simon Fraser Univ Sch Comp Sci Burnaby BC V5A 1S6 Canada NEC Res Princeton NJ 08540 USA Univ Chicago Dept Comp Sci Chicago IL 60637 USA Univ Toronto Dept Comp Sci Toronto ON M5S 3G4 Canada Univ Haifa Dept Comp Sci IL-31999 Haifa Israel MIT CSAIL Cambridge MA 02139 USA Univ Paderborn Heinz Nixdorf Inst D-33102 Paderborn Germany Univ Paderborn Fac Comp Sci Elect Engn & Math D-33102 Paderborn Germany

We consider the problem of computing the weight of a Euclidean minimum spanning tree for a set of n points in R-d. We focus on the setting where the input point set is supported by certain basic ( and commonly used) geometric data structures that can provide efficient access to the input in a structured way. We present an algorithm that estimates with high probability the weight of a Euclidean minimum spanning tree of a set of points to within 1+epsilon using only (O) over tilde(root n poly(1/epsilon)) queries for constant d. The algorithm assumes that the input is supported by a minimal bounding cube enclosing it, by orthogonal range queries, and by cone approximate nearest neighbor queries.

关键词： sublinear algorithms minimum spanning tree

来源：评论

学校读者我要写书评

暂无评论

An average-case sublinear forward algorithm for the haploid Li and Stephens model

引用

algorithms FOR MOLECULAR BIOLOGY 2019年第1期14卷 11-11页

作者： Rosen, Yohei M. Paten, Benedict J. UCSC Genom Inst 1156 High St Santa Cruz CA 95064 USA NYU Sch Med 550 First Ave New York NY 10016 USA

BackgroundHidden Markov models of haplotype inheritance such as the Li and Stephens model allow for computationally tractable probability calculations using the forward algorithm as long as the representative reference panel used in the model is sufficiently small. Specifically, the monoploid Li and Stephens model and its variants are linear in reference panel size unless heuristic approximations are used. However, sequencing projects numbering in the thousands to hundreds of thousands of individuals are underway, and others numbering in the millions are *** make the forward algorithm for the haploid Li and Stephens model computationally tractable for these datasets, we have created a numerically exact version of the algorithm with observed average case sublinear runtime with respect to reference panel size k when tested against the 1000 Genomes *** show a forward algorithm which avoids any tradeoff between runtime and model complexity. Our algorithm makes use of two general strategies which might be applicable to improving the time complexity of other future sequence analysis algorithms: sparse dynamic programming matrices and lazy evaluation.

关键词： Forward algorithm Haplotype Complexity sublinear algorithms

来源：评论

学校读者我要写书评

暂无评论

Efficient and Near-optimal algorithms for Sampling Small Connected Subgraphs

引用

ACM TRANSACTIONS ON algorithms 2023年第3期19卷 1-40页

作者： Bressan, Marco Univ Milan Dipartimento Informat Via Celoria 18 I-20133 Milan Italy

We study the following problem: Given an integer k >= 3 and a simple graph G, sample a connected induced k-vertex subgraph ofG uniformly at random. This is a fundamental graph mining primitive with applications in social network analysis, bioinformatics, and more. Surprisingly, no efficient algorithm is known for uniform sampling;the only somewhat efficient algorithms available yield samples that are only approximately uniform, with running times that are unclear or suboptimal. In this work, we provide: (i) a near-optimal mixing time bound for a well-known random walk technique, (ii) the first efficient algorithm for truly uniform graphlet sampling, and (iii) the first sublinear-time algorithm for e-uniform graphlet sampling.

关键词： Subgraph sampling random walks sublinear algorithms

来源：评论

学校读者我要写书评

暂无评论

On Approximating the Stationary Distribution of Time-reversible Markov Chains 35

On Approximating the Stationary Distribution of Time-reversi...

引用

35th Symposium on Theoretical Aspects of Computer Science (STACS)

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

ISBN: (纸本)9783959770620

Approximating the stationary probability of a state in a Markov chain through Markov chain Monte Carlo techniques is, in general, inefficient. Standard random walk approaches require (O) over tilde(tau/pi(v)) operations to approximate the probability pi(v) of a state v in a chain with mixing time T, and even the best available techniques still have complexity (O) over tilde (tau(1.5)/pi(v)(0.5));and since these complexities depend inversely on pi(v), they can grow beyond any bound in the size of the chain or in its mixing time. In this paper we show that, for time-reversible Markov chains, there exists a simple randomized approximation algorithm that breaks this "small-pi(v) barrier".

关键词： Markov Chains MCMC Sampling Large Graph algorithms Randomized algorithms sublinear algorithms

来源：评论

学校读者我要写书评

暂无评论

Estimating the Longest Increasing Subsequence in Nearly Optimal Time 63

Estimating the Longest Increasing Subsequence in Nearly Opti...

引用

63rd Annual IEEE Symposium on Foundations of Computer Science (FOCS)

作者： Andoni, Alexandr Nosatzki, Negev Shekel Sinha, Sandip Stein, Clifford Columbia Univ New York NY 10027 USA

ISBN: (纸本)9781665455190

Longest Increasing Subsequence (LIS) is a fundamental statistic of a sequence, and has been studied for decades. While the LIS of a sequence of length n can be computed exactly in time O(n log n), the complexity of estimating the (length of the) LIS in sublinear time, especially when LIS << n, is still open. We show that for any n is an element of N and lambda = o(1), there exists a (randomized) non-adaptive algorithm that, given a sequence of length n with LIS >= lambda n, approximates the LIS up to a factor of 1/lambda(o(1)) in n(o(1))/lambda time. Our algorithm improves upon prior work substantially in terms of both approximation and run-time: (i) we provide the first sub-polynomial approximation for LIS in sub-linear time;and (ii) our run-time complexity essentially matches the trivial sample complexity lower bound of Omega(1/lambda), which is required to obtain any non-trivial approximation of the LIS. As part of our solution, we develop two novel ideas which may be of independent interest. First, we define a new Genuine-LIS problem, in which each sequence element may be either genuine or corrupted. In this model, the user receives unrestricted access to the actual sequence, but does not know a priori which elements are genuine. The goal is to estimate the LIS using genuine elements only, with the minimal number of tests for genuineness. The second idea, Precision Tree, enables accurate estimations for composition of general functions from "coarse" (sub-)estimates. Precision Tree essentially generalizes classical precision sampling, which works only for summations. As a central tool, the Precision Tree is pre-processed on a set of samples, which thereafter is repeatedly used by multiple components of the algorithm, improving their amortized complexity.

关键词： sublinear algorithms approximation algorithms randomized algorithms longest increasing subsequence string algorithms

来源：评论

学校读者我要写书评

暂无评论

Edit Distance in Near-Linear Time: it's a Constant Factor 61

Edit Distance in Near-Linear Time: it's a Constant Factor

引用

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

作者： Andoni, Alexandr Nosatzki, Negev Shekel Columbia Univ New York NY 10027 USA

ISBN: (纸本)9781728196213

We present an algorithm for approximating the edit distance between two strings of length n in time n(1+epsilon), for any epsilon > 0, up to a constant factor. Our result completes a research direction set forth in the recent breakthrough paper [1], which showed the first constant-factor approximation algorithm with a (strongly) sub-quadratic running time. The recent results [2], [3] have shown near-linear complexity only under the restriction that the edit distance is close to maximal (equivalently, there is a near-linear additive approximation). In contrast, our algorithm obtains a constant-factor approximation in near-linear running time for any input strings.

关键词： edit distance sublinear algorithms fine-grained complexity

来源：评论

学校读者我要写书评

暂无评论

Exponential Quantum Space Advantage for Approximating Maximum Directed Cut in the Streaming Model 2024

Exponential Quantum Space Advantage for Approximating Maximu...

引用

56th Annual ACM Symposium on Theory of Computing (STOC)

作者： Kallaugher, John Parekh, Ojas Voronova, Nadezhda Sandia Natl Labs Albuquerque NM 87123 USA Boston Univ Boston MA USA

ISBN: (纸本)9798400703836

While the search for quantum advantage typically focuses on speed-ups in execution time, quantum algorithms also offer the potential for advantage in space complexity. Previous work has shown such advantages for data stream problems, in which elements arrive and must be processed sequentially without random access, but these have been restricted to specially-constructed problems [Le Gall, SPAA '06] or polynomial advantage [Kallaugher, FOCS '21]. We show an exponential quantum space advantage for the maximum directed cut problem. This is the first known exponential quantum space advantage for any natural streaming problem. This also constitutes the first unconditional exponential quantum resource advantage for approximating a discrete optimization problem in any setting. Our quantum streaming algorithm 0.4844-approximates the value of the largest directed cut in a graph stream with n vertices using polylog(n) space, while previous work by Chou, Golovnev, and Velusamy [FOCS '20] implies that obtaining an approximation ratio better than 4/9 approximate to 0.4444 requires Omega(root n) space for any classical streaming algorithm. Our result is based on a recent ($) over tilde(root n) space classical streaming approach by Saxena, Singer, Sudan, and Velusamy [FOCS '23], with an additional improvement in the approximation ratio due to recent work by Singer [APPROX '23].

关键词： approximation algorithms graph algorithms quantum computing streaming and sketching sublinear algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：