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

Splitting a Delaunay triangulation in linear time

ALGORITHMICA 2002年第1期34卷 39-46页

作者： Chazelle, B Devillers, O Hurtado, F Mora, M Sacristán, V Teillaud, M Princeton Univ Dept Comp Sci Princeton NJ 08544 USA INRIA F-06902 Sophia Antipolis France Univ Politecn Cataluna Dept Matemat Aplicada 2 E-08028 Barcelona Spain

Computing the Delaunay triangulation of n points requires usually a minimum of 2 (n log n) operations, but in some special cases where some additional knowledge is provided, faster algorithms can be designed. Given two sets of points, we prove that, if the Delaunay triangulation of all the points is known, the Delaunay triangulation of each set can be computed in randomized expected linear time.

关键词： computational geometry Delaunay triangulation Voronoi diagrams randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Nonmalleable cryptography

引用

SIAM JOURNAL ON COMPUTING 2000年第2期30卷 391-437页

作者： Dolev, D Dwork, C Naor, M Hebrew Univ Jerusalem Dept Comp Sci IL-91904 Jerusalem Israel IBM Corp Almaden Res Ctr Div Res San Jose CA 95120 USA Weizmann Inst Sci Dept Comp Sci & Appl Math IL-76100 Rehovot Israel

The notion of nonmalleable cryptography, an extension of semantically secure cryptography, is defined. Informally, in the context of encryption the additional requirement is that given the ciphertext it is impossible to generate a different ciphertext so that the respective plaintexts are related. The same concept makes sense in the contexts of string commitment and zero-knowledge proofs of possession of knowledge. Nonmalleable schemes for each of these three problems are presented. The schemes do not assume a trusted center;a user need not know anything about the number or identity of other system users. Our cryptosystem is the rst proven to be secure against a strong type of chosen ciphertext attack proposed by Racko and Simon, in which the attacker knows the ciphertext she wishes to break and can query the decryption oracle on any ciphertext other than the target.

关键词： cryptography cryptanalysis encryption authentication randomized algorithms nonmalleability chosen ciphertext security auction protocols commitment schemes zero-knowledge

来源：评论

学校读者我要写书评

暂无评论

Doubly logarithmic communication algorithms for optical-communication parallel computers

引用

SIAM JOURNAL ON COMPUTING 1997年第4期26卷 1100-1119页

作者： Goldberg, LA Jerrum, M Leighton, T Rao, S SANDIA NATL LABS LIVERMORE CA 94550 USA UNIV EDINBURGH DEPT COMP SCI EDINBURGH EH9 3JZ MIDLOTHIAN SCOTLAND NEC RES INST PRINCETON NJ 08540 USA MIT DEPT MATH CAMBRIDGE MA 02139 USA MIT COMP SCI LAB CAMBRIDGE MA 02139 USA

In this paper, we consider the problem of interprocessor communication on parallel computers that have optical communication networks. We consider the completely connected optical-communication parallel computer (OCPC), which has a completely connected optical network, and also the mesh-of-optical-buses parallel computer (MOB-PC), which has a mesh of optical buses as its communication network. The particular communication problem that we study is that of realizing an h-relation. In this problem, each processor has at most h messages to send and at most h messages to receive. It is clear that any 1-relation can be realized in one communication step on an OCPC. However, the best previously known p-processor OCPC algorithm for realizing an arbitrary h-relation for h > 1 requires -(h + log p) expected communication steps. (This algorithm is due to Valiant and is based on earlier work of Anderson and Miller.) Valiant's algorithm is optimal only for h = Omega(log p), and it is an open question of Gereb-Graus and Tsantilas whether there is a faster algorithm for h = Omega(log p). In this paper, we answer this question in the affirmative and we extend the range of optimality by considering the case in which h less than or equal to log p. In particular, we present a -(h + log log p)-communication-step randomized algorithm that realizes an arbitrary h-relation on a p-processor OCPC. We show that if h less than or equal to log p, then the failure probability can be made as small as p(-alpha) for any positive constant alpha. We use the OCPC algorithm as a subroutine in a -(h + log log p)communication-step randomized algorithm that realizes an arbitrary h-relation on a p x p-processor MOB-PC. Once again, we show that if h less than or equal to log p, then the failure probability can be made as small as p(-alpha) for any positive constant alpha.

关键词： parallel algorithms randomized algorithms routing optical networks

来源：评论

学校读者我要写书评

暂无评论

Security Pricing as Enabler of Cyber-Insurance A First Look at Differentiated Pricing Markets

引用

IEEE TRANSACTIONS ON DEPENDABLE AND SECURE COMPUTING 2019年第2期16卷 358-372页

作者： Pal, Ranjan Golubchik, Leana Psounis, Konstantinos Hui, Pan Univ Southern Calif Dept Comp Sci Los Angeles CA 90007 USA Univ Southern Calif Dept Elect Engn Los Angeles CA 90007 USA Hong Kong Univ Sci & Technol Dept Comp Sci & Engn Clear Water Bay Hong Kong Peoples R China Y Labs Telekom Innovat Labs D-10587 Berlin Germany

Despite the promising potential of network risk management services (e.g., cyber-insurance) to improve information security, their deployment is relatively scarce, primarily due to such service companies being unable to guarantee profitability. As a novel approach to making cyber-insurance services more viable, we explore a symbiotic relationship between security vendors (e.g., Symantec) capable of price differentiating their clients, and cyber-insurance agencies having possession of information related to the security investments of their clients. The goal of this relationship is to (i) allow security vendors to price differentiate their clients based on security investment information from insurance agencies, (ii) allow the vendors to make more profit than in homogeneous pricing settings, and (iii) subsequently transfer some of the extra profit to cyber-insurance agencies to make insurance services more viable. In this paper, we perform a theoretical study of a market for differentiated security product pricing, primarily with a view to ensuring that security vendors (SVs) make more profit in the differentiated pricing case as compared to the case of non-differentiated pricing. In order to practically realize such pricing markets, we propose novel and computationally efficient consumer differentiated pricing mechanisms for SVs based on (i) the market structure, (ii) the communication network structure of SV consumers captured via a consumer's Bonacich centrality in the network, and (iii) security investment amounts made by SV consumers. We validate our analytical model via extensive simulations conducted on practical SV client network topologies;main results show (through those simulations) that (a) a monopoly SV could improve its profit margin by upto approximate to 25 percent (based on the simulation setting) by accounting for clients' investment information and network locations, whereas in an oligopoly setting, SVs could improve their profit margins by upto ap

关键词： Security monopoly oligopoly pricing bonacich centrality {Market, Nash} equilibrium randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Gradient Coding With Iterative Block Leverage Score Sampling

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2024年第9期70卷 6639-6664页

作者： Charalambides, Neophytos Pilanci, Mert Hero, Alfred O. Univ Michigan Dept Elect Engn & Comp Sci Ann Arbor MI 48109 USA Univ Calif San Diego Dept Comp Sci & Engn San Diego CA 92093 USA Univ Calif San Diego Halicioglu Data Sci Inst San Diego CA 92093 USA Stanford Univ Dept Elect Engn Stanford CA 94305 USA Univ Michigan Dept Elect Engn & Comp Sci Ann Arbor MI 48109 USA

Gradient coding is a method for mitigating straggling servers in a centralized computing network that uses erasure-coding techniques to distributively carry out first-order optimization methods. randomized numerical linear algebra uses randomization to develop improved algorithms for large-scale linear algebra computations. In this paper, we propose a method for distributed optimization that combines gradient coding and randomized numerical linear algebra. The proposed method uses a randomized $\ell _randomized$ -subspace embedding and a gradient coding technique to distribute blocks of data to the computational nodes of a centralized network, and at each iteration the central server only requires a small number of computations to obtain the steepest descent update. The novelty of our approach is that the data is replicated according to importance scores, called block leverage scores, in contrast to most gradient coding approaches that uniformly replicate the data blocks. Furthermore, we do not require a decoding step at each iteration, avoiding a bottleneck in previous gradient coding schemes. We show that our approach results in a valid $\ell _randomized$ -subspace embedding, and that our resulting approximation converges to the optimal solution.

关键词： Servers Approximation algorithms Task analysis Encoding Linear algebra Accuracy Monte Carlo methods Low-rank approximations least-squares regression randomized algorithms randomized numerical linear algebra coded computing stragglers erasure-coding replication-coding

来源：评论

学校读者我要写书评

暂无评论

Sublinear Time Eigenvalue Approximation via Random Sampling

引用

ALGORITHMICA 2024年第6期86卷 1764-1829页

作者： Bhattacharjee, Rajarshi Dexter, Gregory Drineas, Petros Musco, Cameron Ray, Archan Univ Massachusetts Manning Coll Informat & Comp Sci Amherst MA USA Purdue Univ Dept Comp Sci W Lafayette IN 47907 USA

We study the problem of approximating the eigenspectrum of a symmetric matrix A is an element of R-nxn with bounded entries (i.e., parallel to A parallel to(infinity) <= 1). We present a simple sublinear time algorithm that approximates all eigenvalues of A up to additive error +/-epsilon n using those of a randomly sampled (O) over tilde (log(3)n/epsilon(3)) x (O) over tilde (log(3)n/epsilon(3)) principal submatrix. Our result can be viewed as a concentration bound on the complete eigenspectrum of a random submatrix, significantly extending known bounds on just the singular values (the magnitudes of the eigenvalues). We give improved error bounds of +/- epsilon root nnz(A) and +/- epsilon parallel to A parallel to(F) when the rows of A can be sampled with probabilities proportional to their sparsities or their squared l(2) norms respectively. Here nnz(A) is the number of non-zero entries in A and parallel to A parallel to(F) is its Frobenius norm. Even for the strictly easier problems of approximating the singular values or testing the existence of large negative eigenvalues (Bakshi, Chepurko, and Jayaram, FOCS '20), our results are the first that take advantage of non-uniform sampling to give improved error bounds. From a technical perspective, our results require several new eigenvalue concentration and perturbation bounds for matrices with bounded entries. Our non-uniform sampling bounds require a new algorithmic approach, which judiciously zeroes out entries of a randomly sampled submatrix to reduce variance, before computing the eigenvalues of that submatrix as estimates for those of A. We complement our theoretical results with numerical simulations, which demonstrate the effectiveness of our algorithms in practice.

关键词： Eigenvalue approximation Sublinear algorithms randomized algorithms Symmetric matrices

来源：评论

学校读者我要写书评

暂无评论

Fast computation of Fourier integral operators

引用

SIAM JOURNAL ON SCIENTIFIC COMPUTING 2007年第6期29卷 2464-2493页

作者： Candes, Emmanuel Demanet, Laurent Ying, Lexing Stanford Univ Dept Math Stanford CA 94305 USA Univ Texas Dept Math Austin TX 78712 USA

We introduce a general purpose algorithm for rapidly computing certain types of oscillatory integrals which frequently arise in problems connected to wave propagation, general hyperbolic equations, and curvilinear tomography. The problem is to numerically evaluate a so-called Fourier integral operator (FIO) of the form integral e(2 pi i Phi(x,xi))a(x,xi) (f) over cap(xi)d xi. at points given on a Cartesian grid. Here, xi is a frequency variable, (f) over cap(xi) is the Fourier transform of the input f, a(x,xi) is an amplitude, and Phi(x,xi) is a phase function, which is typically as large as |xi|;hence the integral is highly oscillatory. Because a FIO is a dense matrix, a naive matrix vector product with an input given on a Cartesian grid of size N by N would require O(N-4)operations. This paper develops a new numerical algorithm which requires O(N-2.5 log N) operations and as low as O(root N) in storage space (the constants in front of these estimates are small). It operates by localizing the integral over polar wedges with small angular aperture in the frequency plane. On each wedge, the algorithm factorizes the kernel e(2 pi i Phi(x,xi))a(x,xi) into two components: (1) a diffeomorphism which is handled by means of a nonuniform FFT and (2) a residual factor which is handled by numerical separation of the spatial and frequency variables. The key to the complexity and accuracy estimates is the fact that the separation rank of the residual kernel is provably independent of the problem size. Several numerical examples demonstrate the numerical accuracy and low computational complexity of the proposed methodology. We also discuss the potential of our ideas for various applications such as reflection seismology.

关键词： fourier integral operators generalized Radon transform separated representation nonuniform fast Fourier transform matrix approximation operator compression randomized algorithms reflection seismology

来源：评论

学校读者我要写书评

暂无评论

Topological repairing of 3D digital images

引用

JOURNAL OF MATHEMATICAL IMAGING AND VISION 2008年第3期30卷 249-274页

作者： Siqueira, Marcelo Latecki, Longin Jan Tustison, Nicholas Gallier, Jean Gee, James Univ Fed Mato Grosso do Sul Dept Computacao & Estat BR-79070900 Campo Grande MS Brazil Temple Univ Dept Comp & Informat Sci Philadelphia PA 19122 USA Univ Penn Penn Image & Comp Sci Lab Dept Radiol Philadelphia PA 19104 USA Univ Penn Dept Comp & Informat Sci Philadelphia PA 19104 USA

We present here a new randomized algorithm for repairing the topology of objects represented by 3D binary digital images. By "repairing the topology", we mean a systematic way of modifying a given binary image in order to produce a similar binary image which is guaranteed to be well-composed. A 3D binary digital image is said to be well-composed if, and only if, the square faces shared by background and foreground voxels form a 2D manifold. Well-composed images enjoy some special properties which can make such images very desirable in practical applications. For instance, well-known algorithms for extracting surfaces from and thinning binary images can be simplified and optimized for speed if the input image is assumed to be well-composed. Furthermore, some algorithms for computing surface curvature and extracting adaptive triangulated surfaces, directly from the binary data, can only be applied to well-composed images. Finally, we introduce an extension of the aforementioned algorithm to repairing 3D digital multivalued images. Such an algorithm finds application in repairing segmented images resulting from multi-object segmentations of other 3D digital multivalued images.

关键词： well-composed images digital topology randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

METRIC EMBEDDINGS WITH RELAXED GUARANTEES

引用

SIAM JOURNAL ON COMPUTING 2009年第6期38卷 2303-2329页

作者： Chan, T. -H. Hubert Dhamdhere, Kedar Gupta, Anupam Kleinberg, Jon Slivkins, Aleksandrs Max Planck Inst Informat D-66123 Saarbrucken Germany Google Inc Mountain View CA 94043 USA Carnegie Mellon Univ Dept Comp Sci Pittsburgh PA 15213 USA Cornell Univ Dept Comp Sci Ithaca NY 14853 USA Microsoft Res Mountain View CA 94043 USA

We consider the problem of embedding finite metrics with slack: We seek to produce embeddings with small dimension and distortion while allowing a (small) constant fraction of all distances to be arbitrarily distorted. This definition is motivated by recent research in the networking community, which achieved striking empirical success at embedding Internet latencies with low distortion into low-dimensional Euclidean space, provided that some small slack is allowed. Answering an open question of Kleinberg, Slivkins, and Wexler [in Proceedings of the 45th IEEE Symposium on Foundations of Computer Science, 2004], we show that provable guarantees of this type can in fact be achieved in general: Any finite metric space can be embedded, with constant slack and constant distortion, into constant-dimensional Euclidean space. We then show that there exist stronger embeddings into l(1) which exhibit gracefully degrading distortion: There is a single embedding into l(1) that achieves distortion at most O(log 1/epsilon) on all but at most an epsilon fraction of distances simultaneously for all epsilon > 0. We extend this with distortion O(log 1/epsilon)(1/p) to maps into general l(p), p >= 1, for several classes of metrics, including those with bounded doubling dimension and those arising from the shortest-path metric of a graph with an excluded minor. Finally, we show that many of our constructions are tight and give a general technique to obtain lower bounds for epsilon-slack embeddings from lower bounds for low-distortion embeddings.

关键词： metric embeddings low-distortion embeddings metric spaces metric decompositions randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：