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

27th Annual European Symposium on algorithms (ESA)

作者： Brand, Cornelius Saarland Univ MMCI Saarland Informat Campus Saarbrucken Germany

ISBN: (纸本)9783959771245

We describe a generic way of exponentially speeding up algorithms which rely on Color-Coding by using the recently introduced technique of Extensor-Coding (Brand, Dell and Husfeldt, STOC 2018). To demonstrate the usefulness of this "patching" of Color-Coding algorithms, we apply it ad hoc to the exponential-space algorithms given in Gutin et al. (Journal Comp. Sys. Sci. 2018) and obtain the fastest known deterministic algorithms for, among others, the k-internal out-branching and k-internal spanning tree problems. To realize these technical advances, we make qualitative progress in a special case of the detection of multilinear monomials in multivariate polynomials: We give the first deterministic fixed-parameter tractable algorithm for the k-multilinear detection problem on a class of arithmetic circuits that may involve cancellations, as long as the computed polynomial is promised to satisfy a certain natural condition. Furthermore, we explore the limitations of using this very approach to speed up algorithms by determining exactly the dimension of a crucial subalgebra of extensors that arises naturally in the instantiation of the technique: It is equal to F2k+1, the kth odd term in the Fibonacci sequence. To determine this dimension, we use tools from the theory of Grobner bases, and the studied algebraic object may be of independent interest. We note that the asymptotic bound of F2k+1 approximate to phi(2k) = O(2.619(k)) curiously coincides with the running time bound on one of the fastest algorithms for the k-path problem based on representative sets due to Fomin et al. (JACM 2016). Here, phi is the golden ratio.

关键词： Color-Coding Extensor-Coding internal out-branching colorful problems algebraic algorithms multilinear detection deterministic algorithms exterior algebra

来源：评论

学校读者我要写书评

暂无评论

The algebraic Group Model and its Applications 38th

The Algebraic Group Model and its Applications

引用

38th Annual International Cryptology Conference (CRYPTO)

作者： Fuchsbauer, Georg Kiltz, Eike Loss, Julian ENS CNRS PSL INRIA Paris France Ruhr Univ Bochum Bochum Germany

ISBN: (纸本)9783319968810;9783319968803

One of the most important and successful tools for assessing hardness assumptions in cryptography is the Generic Group Model (GGM). Over the past two decades, numerous assumptions and protocols have been analyzed within this model. While a proof in the GGM can certainly provide some measure of confidence in an assumption, its scope is rather limited since it does not capture group-specific algorithms that make use of the representation of the group. To overcome this limitation, we propose the algebraic Group Model (AGM), a model that lies in between the Standard Model and the GGM. It is the first restricted model of computation covering group-specific algorithms yet allowing to derive simple and meaningful security statements. To prove its usefulness, we show that several important assumptions, among them the Computational Diffie-Hellman, the Strong Diffie-Hellman, and the interactive LRSW assumptions, are equivalent to the Discrete Logarithm (DLog) assumption in the AGM. On the more practical side, we prove tight security reductions for two important schemes in the AGM to DLog or a variant thereof: the BLS signature scheme and Groth's zero-knowledge SNARK (EUROCRYPT 2016), which is the most efficient SNARK for which only a proof in the GGM was known. Our proofs are quite simple and therefore less prone to subtle errors than those in the GGM. Moreover, in combination with known lower bounds on the Discrete Logarithm assumption in the GGM, our results can be used to derive lower bounds for all the above-mentioned results in the GGM.

关键词： algebraic algorithms Generic group model Security reductions Cryptographic assumptions

来源：评论

学校读者我要写书评

暂无评论

Decoding Reed-Muller Codes over Product Sets

引用

THEORY OF COMPUTING 2017年 13卷 1-38页

作者： Kim, John Y. Kopparty, Swastik Virtu Financial Austin TX 78746 USA Rutgers State Univ Dept Math New Brunswick NJ USA Rutgers State Univ Dept Comp Sci New Brunswick NJ USA

We give a polynomial-time algorithm to decode multivariate polynomial codes of degree d up to half their minimum distance, when the evaluation points are an arbitrary product set S-m, for every d < vertical bar S vertical bar. Previously known algorithms could achieve this only if the set S had some very special algebraic structure, or if the degree d was significantly smaller than vertical bar S vertical bar. We also give a near-linear-time randomized algorithm, based on tools from list-decoding, to decode these codes from nearly half their minimum distance, provided d < (1- epsilon) vertical bar S vertical bar for constant epsilon > 0. Our result gives an m-dimensional generalization of the well-known decoding algorithms for Reed-Solomon codes, and can be viewed as giving an algorithmic version of the Schwartz-Zippel lemma.

关键词： error-correcting codes Reed-Muller codes algebraic algorithms Schwartz-Zippel lemma

来源：评论

学校读者我要写书评

暂无评论

Building Above Read-Once Polynomials: Identity Testing and Hardness of Representation

引用

ALGORITHMICA 2016年第4期76卷 890-909页

作者： Mahajan, Meena Rao, B. V. Raghavendra Sreenivasaiah, Karteek Inst Math Sci Madras Tamil Nadu India Indian Inst Technol Madras Tamil Nadu India Max Planck Inst Informat Saarbrucken Germany

Polynomial Identity Testing (PIT) algorithms have focussed on polynomials computed either by small alternation-depth arithmetic circuits, or by read-restricted formulas. Read-once polynomials (ROPs) are computed by read-once formulas (ROFs) and are the simplest of read-restricted polynomials. Building structures above these, we show the following: (1) a deterministic polynomial-time non-black-box PIT algorithm for . (2) Weak hardness of representation theorems for sums of powers of constant-free ROPs and for s of the form . (3) A partial characterization of multilinear monotone constant-free ROPs.

关键词： Polynomial Identity Testing algebraic algorithms Arithmetic circuits

来源：评论

学校读者我要写书评

暂无评论

Polynomial-Time Approximation Schemes for Circle and Other Packing Problems

引用

ALGORITHMICA 2016年第2期76卷 536-568页

作者： Miyazawa, Flavio K. Pedrosa, Lehilton L. C. Schouery, Rafael C. S. Sviridenko, Maxim Wakabayashi, Yoshiko Univ Estadual Campinas Inst Comp Campinas SP Brazil Univ Sao Paulo Dept Comp Sci Sao Paulo Brazil Yahoo Labs New York NY USA

We consider the problem of packing a set of circles into a minimum number of unit square bins. To obtain rational solutions, we use augmented bins of height , for some arbitrarily small number . For this problem, we obtain an asymptotic approximation scheme (APTAS) that is polynomial on , and thus may be given as part of the problem input. For the special case that is constant, we give a (one dimensional) resource augmentation scheme, that is, we obtain a packing into bins of unit width and height using no more than the number of bins in an optimal packing without resource augmentation. Additionally, we obtain an APTAS for the circle strip packing problem, whose goal is to pack a set of circles into a strip of unit width and minimum height. Our algorithms are the first approximation schemes for circle packing problems, and are based on novel ideas of iteratively separating small and large items, and may be extended to a wide range of packing problems that satisfy certain conditions. These extensions comprise problems with different kinds of items, such as regular polygons, or with bins of different shapes, such as circles and spheres. As an example, we obtain APTAS's for the problems of packing d-dimensional spheres into hypercubes under the L-p-norm.

关键词： Circle bin packing Circle strip packing Asymptotic approximation scheme Resource augmentation scheme Sphere packing algebraic algorithms

来源：评论

学校读者我要写书评

暂无评论

Determining cyclicity of finite modules

引用

JOURNAL OF SYMBOLIC COMPUTATION 2016年 73卷 153-156页

作者： Lenstra, H. W., Jr. Silverberg, A. Leiden Univ Math Inst NL-2300 RA Leiden Netherlands Univ Calif Irvine Dept Math Irvine CA 92697 USA

We present a deterministic polynomial-time algorithm that determines whether a finite module over a finite commutative ring is cyclic, and if it is, outputs a generator. (C) 2015 Elsevier Ltd. All rights reserved.

关键词： algebraic algorithms Finite rings Cyclic modules

来源：评论

学校读者我要写书评

暂无评论

LIMITS and Applications of Group Algebras for Parameterized Problems

引用

ACM TRANSACTIONS ON algorithms 2016年第3期12卷 31-31页

作者： Koutis, Ioannis Williams, Ryan Univ Puerto Rico Dept Comp Sci Rio Piedras PR USA Stanford Univ Dept Comp Sci Stanford CA 94305 USA

The fastest known randomized algorithms for several parameterized problems use reductions to the k-MLD problem: detection of multilinear monomials of degree k in polynomials presented as circuits. The fastest known algorithm for k-MLD is based on 2(k) evaluations of the circuit over a suitable algebra. We use communication complexity to show that it is essentially optimal within this evaluation framework. On the positive side, we give additional applications of the method: finding a copy of a given tree on k nodes, a minimum set of nodes that dominate at least t nodes, and an m-dimensional k-matching. In each case, we achieve a faster algorithm than what was known before. We also apply the algebraic method to problems in exact counting. Among other results, we show that a variation of it can break the trivial upper bounds for the disjoint summation problem.

关键词： Multilinear detection exact counting permanent algebraic algorithms color coding

来源：评论

学校读者我要写书评

暂无评论

The Persistent Homology of a Self-Map

引用

FOUNDATIONS OF COMPUTATIONAL MATHEMATICS 2015年第5期15卷 1213-1244页

作者： Edelsbrunner, Herbert Jablonski, Grzegorz Mrozek, Marian IST Austria Inst Sci & Technol Austria Klosterneuburg Austria Jagiellonian Univ Fac Math & Comp Sci Div Computat Math Krakow Poland

Considering a continuous self-map and the induced endomorphism on homology, we study the eigenvalues and eigenspaces of the latter. Taking a filtration of representations, we define the persistence of the eigenspaces, effectively introducing a hierarchical organization of the map. The algorithm that computes this information for a finite sample is proved to be stable, and to give the correct answer for a sufficiently dense sample. Results computed with an implementation of the algorithm provide evidence of its practical utility.

关键词： Discrete dynamical systems Computational topology Persistent homology Category theory algebraic algorithms Convergence Stability Computational experiments

来源：评论

学校读者我要写书评

暂无评论

algebraic algorithms FOR MATCHING AND MATROID PROBLEMS

引用

SIAM JOURNAL ON COMPUTING 2009年第2期39卷 679-702页

作者： Harvey, Nicholas J. A. MIT Comp Sci & Artificial Intelligence Lab Cambridge MA 02139 USA

We present new algebraic approaches for two well-known combinatorial problems: nonbipartite matching and matroid intersection. Our work yields new randomized algorithms that exceed or match the efficiency of existing algorithms. For nonbipartite matching, we obtain a simple, purely algebraic algorithm with running time O(n(omega)) where n is the number of vertices and omega is the matrix multiplication exponent. This resolves the central open problem of Mucha and Sankowski (2004). For matroid intersection, our algorithm has running time O(nr(omega-1)) for matroids with n elements and rank r that satisfy some natural conditions.

关键词： nonbipartite matching matroid intersection algebraic algorithms fast matrix multiplication

来源：评论

学校读者我要写书评

暂无评论

Quasi-optimal multiplication of linear differential operators

Quasi-optimal multiplication of linear differential operator...

引用

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

作者： Benoit, Alexandre Bostan, Alin van der Hoeven, Joris UPMC Paris France INRIA France Paris France CNRS Ecole Polytech Paris France

We show that linear differential operators with polynomial coefficients over a field of characteristic zero can be multiplied in quasi-optimal time. This answers an open question raised by van der Hoeven.

ISBN: (纸本)9781467343831

关键词： Linear differential operators multiplication algebraic algorithms computational complexity

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：