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

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

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

ISBN: (纸本)9781538634646

The problem of computing the Fourier Transform of a signal whose spectrum is dominated by a small number k of frequencies quickly and using a small number of samples of the signal in time domain (the Sparse FFT problem) has received significant attention recently. It is known how to approximately compute the k-sparse Fourier transform in approximate to k log(2) n time [Hassanieh et al'STOC'12], or using the optimal number O(k log n) of samples [Indyk et al'FOCS'14] in time domain, or come within (log log n)(O(1)) factors of both these bounds simultaneously, but no algorithm achieving the optimal O(k log n) bound in sublinear time is known. At a high level, sublinear time Sparse FFT algorithms operate by 'hashing' the spectrum of the input signal into approximate to k 'buckets', identifying frequencies that are 'isolated' in their buckets, subtracting them from the signal and repeating until the entire signal is recovered. The notion of 'isolation' in a 'bucket', inspired by applications of hashing in sparse recovery with arbitrary linear measurements, has been the main tool in the analysis of Fourier hashing schemes in the literature. However, Fourier hashing schemes, which are implemented via filtering, tend to be 'noisy' in the sense that a frequency that hashes into a bucket contributes a non-negligible amount to neighboring buckets. This leakage to neighboring buckets makes identification and estimation challenging, and the standard analysis based on isolation becomes difficult to use without losing omega(1) factors in sample complexity. In this paper we propose a new technique for analysing noisy hashing schemes that arise in Sparse FFT, which we refer to as isolation on average. We apply this technique to two problems in Sparse FFT: estimating the values of a list of frequencies using few samples and computing Sparse FFT itself, achieving sample-optimal results in k log(O(1)) n time for both. We feel that our approach will likely be of interest in designing Fo

关键词： Sparse Fourier Transform Fourier sampling sublinear algorithms

来源：评论

学校读者我要写书评

暂无评论

Approximate Earth Mover's Distance in Truly-Subquadratic Time 2024

Approximate Earth Mover's Distance in Truly-Subquadratic Tim...

引用

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

作者： Beretta, Lorenzo Rubinstein, Aviad Univ Copenhagen BARC Copenhagen Denmark Stanford Univ Stanford CA 94305 USA

ISBN: (纸本)9798400703836

We design an additive approximation scheme for estimating the cost of the min-weight bipartite matching problem: given a bipartite graph with non-negative edge costs and epsilon > 0, our algorithm estimates the cost of matching all but O(epsilon)-fraction of the vertices in truly subquadratic time O (n(2-delta(epsilon))). Our algorithm has a natural interpretation for computing the Earth Mover's Distance (EMD), up to a epsilon-additive approximation. Notably, we make no assumptions about the underlying metric (more generally, the costs do not have to satisfy triangle inequality). Note that compared to the size of the instance (an arbitrary n x n cost matrix), our algorithm runs in sublinear time. Our algorithm can approximate a slightly more general problem: max-cardinality bipartite matching with a knapsack constraint, where the goal is to maximize the number of vertices that can be matched up to a total cost B.

关键词： sublinear algorithms Earth Mover's Distance Matching

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

"efficient Combinatorial Methods in Sparsification, Summarization and Testing of Large Datasets"

"efficient Combinatorial Methods in Sparsification, Summariz...

引用

作者： Yaroslavtsev, Grigory PennState University Libraries

学位级别：Doctor of Philosophy

Increasingly large amounts of structured data are being collected by personal computers,mobile devices, personal gadgets, sensors, etc., and stored in data centers operated by thegovernment and private companies. Processing of such data to extract key information isone of the main challenges faced by computer scientists. Developing methods for constructingcompact representations of large data is a natural way to approach this *** thesis is focused on rigorous mathematical and algorithmic solutions for sparsi-cation and summarization of large amounts of information using discrete combinatorialmethods. Areas of mathematics most closely related to it are graph theory, informationtheory and analysis of real-valued functions over discrete domains. These areas, somewhatsurprisingly, turn out to be related when viewed through the computational lens. In thisthesis we illustrate the power and limitations of methods for constructing small representationsof large data sets, such as graphs and databases, using a variety methods drawnfrom these *** primary goal of sparsication, summarization and sketching methods discussedhere is to remove redundancy in distributed systems, reduce storage space and save otherresources by compressing the representation, while preserving the key structural propertiesof the original data or system. For example, the size of the network can be reduced byremoving redundant nodes and links, while (approximately) preserving the distances orconnectivities between the *** thesis serves as an overview of results in [31, 30, 152, 38, 171, 33]. It also containsan extension of results in [152] obtained jointly with David Woodruff.

关键词： algorithms big data sublinear algorithms graph theory sparsification summarization

来源：评论

学校读者我要写书评

暂无评论

Property testing and reconstruction with applications to data privacy

Property testing and reconstruction with applications to dat...

引用

作者： Jha, Madhav PennState University Libraries

学位级别：Doctor of Philosophy

The Lipschitz property is a fundamental property of functions with many applications in mathematics and computer science. Intuitively, a function is Lipschitz if it is not too sensitive to small changes in its inputs. In various applications, it is important (often crucial) that the input function satisfies the Lipschitz property. Given query access to a function, can we test that it is Lipschitz? Better still, can we restore or reconstruct the Lipschitz property in a (possibly non-Lipschitz) function by modifying it suitably? In this thesis, we initiate the study of testing and reconstruction of the Lipschitz property of functions. Our primary motivation for studying the Lipschitz property stems from its applications to data privacy. Formally, a function f : D → R is Lipschitz if d_R(f(x),f(y)) ≤ d_D(x,y) for all x, y in D, where d_R and d_D denote the distance metrics on the range and domain of f, respectively. We investigate the Lipschitz property of functions under the well- studied model of property testing (Rubinfeld and Sudan; Goldreich, Goldwasser and Ron) and local property reconstruction (Ailon, Chazelle, Comandur and Liu; Saks and Seshadhri). A property tester has to distinguish functions with the property (in this case, Lipschitz) from functions that differ from every function with the property on many values. A local reconstructor restores a desired property (in this case, Lipschitz) in the following sense: given an arbitrary function f and a query x, it returns g(x), where the resulting function g satisfies the property, changing f only when necessary. If f has the property, g must be equal (or at least “close”) to f . We design efficient testers and local reconstructors for functions over domains of the form {1, . . . , n}^d, equipped with l1 distance, and give corresponding impossibility results. The algorithms we design have applications to data privacy and program analysis.

关键词： property testing property reconstruction Lipschitz function sublinear algorithms data privacy

来源：评论

学校读者我要写书评

暂无评论

Efficient Recovery algorithms with Restricted Access to Strings

Efficient Recovery Algorithms with Restricted Access to Stri...

引用

作者： Sinha, Sandip Columbia University

学位级别：Ph.D., Doctor of Philosophy

We design efficient algorithms for computational problems over strings in several models where the algorithms have limited access to the input. These models, and algorithms developed respecting these constraints, are becoming increasingly relevant due to the rapidly increasing size of datasets in myriad applications. Our first problem of interest is trace reconstruction. This is an important problem in learning theory and coding theory, and has applications in computational biology. In this problem, the goal is to recover an unknown string given independent samples (traces) of it generated via a probabilistic noise process called the deletion channel. We give state-of-the-art algorithms for this problem in several settings. Then we consider the problem of estimating the longest increasing subsequence (LIS) of a given string in sublinear time, given query access to the string. While the LIS of a string can be computed exactly in near-linear time, the optimal complexity of approximating the LIS length, especially when the LIS is much less than the string length, is still open. We significantly improve upon prior work in terms of both approximation and time complexity in this regime. The runtime of our algorithm essentially matches the trivial query complexity lower bound as a function of the length of the LIS. Finally, we consider the problem of local decoding, or random access, on compressed strings. The Burrows-Wheeler Transform (BWT) is an important preprocessing step in lossless text compression that rearranges a string into runs of identical characters (by exploiting context regularities), resulting in highly compressible strings. However, the decoding process of the BWT is inherently sequential, and prevents fast random access to the original string. We design a succinct data structure for locally decoding short substrings (and answering several other queries) of a given string under its compressed BWT efficiently.

关键词： Information theory Randomness in computing Smoothed analysis sublinear algorithms Succinct data structures Trace reconstruction

来源：评论

学校读者我要写书评

暂无评论

Faster algorithms for testing under conditional sampling 28

Faster algorithms for testing under conditional sampling

引用

28th Conference on Learning Theory, COLT 2015

作者： Falahatgar, Moein Jafarpour, Ashkan Orlitsky, Alon Pichapati, Venkatadheeraj Suresh, Ananda Theertha University of California San Diego United States

There has been considerable recent interest in distribution-tests whose run-time and sample requirements are sublinear in the domain-size k. We study two of the most important tests under the conditional-sampling model where each query specifies a subset S of the domain, and the response is a sample drawn from S according to the underlying distribution. For identity testing, which asks whether the underlying distribution equals a specific given distribution or ϵ-differs from it, we reduce the known time and sample complexities from Ω∼(ϵ-4) to Ω∼(ϵ-2), thereby matching the information theoretic lower bound. For closeness testing, which asks whether two distributions underlying observed data sets are equal or different, we reduce existing complexity from Ω∼(ϵ-4 log5 k) to an even sub-logarithmic Ω∼(ϵ-5 log log k) thus providing a better bound to an open problem in Bertinoro Workshop on sublinear algorithms (Fisher, 2014). © 2015 A. Agarwal & S. Agarwal.

关键词： Conditional sampling Property testing sublinear algorithms

来源：评论

学校读者我要写书评

暂无评论

RANDOM WALKS AND FORBIDDEN MINORS II: A poly(dε^-1)-QUERY TESTER FOR MINOR-CLOSED PROPERTIES OF BOUNDED-DEGREE GRAPHS

引用

SIAM JOURNAL ON COMPUTING 2023年第2期52卷 STOC19-323-STOC19-338页

作者： Kumar, Akash Seshadhri, C. Stolman, Andrew M. EPFL Dept Comp Sci W Lafayette IN 47907 USA Univ Calif Santa Cruz Dept Comp Sci Santa Cruz CA 95062 USA

Let G be a graph with n vertices and maximum degree d. Fix some minor-closed property P (such as planarity). We say that G is epsilon-far from P if one has to remove epsilon dn edges to make it have P. The problem of property testing P was introduced in the seminal work of Benjamini, Schramm, and Shapira (Symposium on the Theory of Computing 2008) that gave a tester with query complexity triply exponential in epsilon(-1). Levi and Ron [ACM Trans. algorithms, 11 (2005), 24 2015] have given the best tester to date, with a quasi-polynomial (in epsilon(-1)) query complexity. It remained an open problem to show whether there is a property tester whose query complexity is poly(d epsilon(-1)), even for planarity. In this paper, we resolve this open question. For any minor-closed property, we give a tester with query complexity ***(epsilon(-1)). The previous line of work on (independent of n, two-sided) testers is primarily combinatorial. Our work, on the other hand, employs techniques from spectral graph theory. This paper is a continuation of recent work of the authors (Foundations of Computer Science 2018) analyzing random walk algorithms that find forbidden minors.

关键词： property testing graph minors sublinear algorithms

来源：评论

学校读者我要写书评

暂无评论

TRIGGER DETECTION FOR ADAPTIVE SCIENTIFIC WORKFLOWS USING PERCENTILE SAMPLING

引用

SIAM JOURNAL ON SCIENTIFIC COMPUTING 2016年第5期38卷 S240-S263页

作者： Bennettt, Janine C. Bhagatwala, Ankit Chen, Jacqueline H. Pinar, Ali Salloum, Maher Seshadhri, C. Sandia Natl Labs Livermore CA 94550 USA Lawrence Berkeley Natl Lab Berkeley CA 94720 USA Univ Calif Santa Cruz Dept Comp Sci Santa Cruz CA 95064 USA

The increasing complexity of both scientific simulations and high-performance computing system architectures are driving the need for adaptive workflows, in which the composition and execution of computational and data manipulation steps dynamically depend on the evolutionary state of the simulation itself. Consider, for example, the frequency of data storage. Critical phases of the simulation should be captured with high frequency and with high fidelity for postanalysis;however, we cannot afford to retain the same frequency for the full simulation due to the high cost of data movement. We can instead look for triggers, indicators that the simulation will be entering a critical phase, and adapt the workflow accordingly. In this paper, we present a methodology for detecting triggers and demonstrate its use in the context of direct numerical simulations of turbulent combustion using S3D. We show that chemical explosive mode analysis (CEMA) can be used to devise a noise-tolerant indicator for rapid increase in heat release. However, exhaustive computation of CEMA values dominates the total simulation, and thus is prohibitively expensive. To overcome this computational bottleneck, we propose a quantile sampling approach. Our sampling-based algorithm comes with provable error/confidence bounds, as a function of the number of samples. Most importantly, the number of samples is independent of the problem size, and thus our proposed sampling algorithm offers perfect scalability. Our experiments on homogeneous charge compression ignition and reactivity controlled compression ignition simulations show that the proposed method can detect rapid increases in heat release, and its computational overhead is negligible. Our results will be used to make dynamic workflow decisions regarding data storage and mesh resolution in future combustion simulations.

关键词： sublinear algorithms quantile sampling in situ data analysis chemical explosive mode analysis (CEMA) S3D adaptive workflow judicious I/O

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：