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

21st Annual ACM-SIAM Symposium on Discrete Algorithms

作者： Indyk, Piotr Ngo, Hung Q. Rudra, Atri CSAIL MIT United States Department of Computer Science and Engineering University at Buffalo SUNY United States

ISBN: (纸本)9780898717013

We consider the following "efficiently decodable" non-adaptive group testing problem. There is an unknown string χ ∈ {0, 1} n with at most d ones in it. We are allowed to test any subset S ⊆ [n] of the indices. The answer to the test tells whether χi = 0 for all i ∈ S or not. The objective is to design as few tests as possible (say, t tests) such that χ can be identified as fast as possible (say, poly(t)-time). Efficiently decodable non-adaptive group testing has applications in many areas, including data stream algorithms and data forensics. A non-adaptive group testing strategy can be represented by a 1 x n matrix, which is the stacking of all the characteristic vectors of the tests. It is well-known that if this matrix is d-disjunct, then any test outcome corresponds uniquely to an unknown input string. Furthermore, we know how to construct d-disjunct matrices with t = O(d2 log n) efficiently. However, these matrices so far only allow for a "decoding" time of O(nt), which can be exponentially larger than poly(t) for relatively small values of d. This paper presents a randomness efficient construction of d-disjunct matrices with t = O(d2 log n) that can be decoded in time poly(d)·t log2 t + O(t2). To the best of our knowledge, this is the first result that achieves an efficient decoding time and matches the best known O(d2 log n) bound on the number of tests. We also derandomize the construction, which results in a polynomial time deterministic construction of such matrices when d = O(log n/ log log n). A crucial building block in our construction is the notion of (d, )-list disjunct matrices, which represent the more general "list group testing" problem whose goal is to output less than d + positions in χ, including all the (at most d) positions that have a one in them. List disjunct matrices turn out to be interesting objects in their own right and were also considered independently by [Cheraghchi, FCT 2009]. We present connections between list disjunct matrices

关键词： Matrix algebra

来源：评论

学校读者我要写书评

暂无评论

Derandomized Parallel Repetition of Structured PCPs

Derandomized Parallel Repetition of Structured PCPs

引用

Annual IEEE Conference on Computational Complexity

作者： Irit Dinur Or Meir Department of Computer Science and Applied Mathematics Weizmann Institute of Science Rehovot Israel

A PCP is a proof system for NP in which the proof can be checked by a probabilistic verifier. The verifier is only allowed to read a very small portion of the proof, and in return is allowed to err with some bounded probability. The probability that the verifier accepts a false proof is called the soundness error, and is an important parameter of a PCP system that one seeks to minimize. Constructing PCPs with sub-constant soundness error and, at the same time, a minimal number of queries into the proof (namely two) is especially important due to applications for inapproximability. In this work we construct such PCP verifiers, i.e., PCPs that make only two queries and have sub-constant soundness error. Our construction can be viewed as a combinatorial alternative to the "manifold vs. point'' construction, which is the only construction in the literature for this parameter range. The "manifold vs. point'' PCP is based on a low degree test, while our construction is based on a direct product test. Our construction of a PCP is based on extending the derandomized direct product test of Impagliazzo, Kabanets and Wigderson (STOC 09) to a derandomized parallel repetition theorem. More accurately, our PCP construction is obtained in two steps. We first prove a derandomized parallel repetition theorem for specially structured PCPs. Then, we show that any PCP can be transformed into one that has the required structure, by embedding it on a de-Bruijn graph.

关键词： Testing Computational complexity algebra computer science Error probability polynomials Error correction

来源：评论

学校读者我要写书评

暂无评论

INTERSECTION THEORIES AND CHEBYSHEV polynomials III

引用

JOURNAL OF algebra AND ITS applications 2009年第1期8卷 53-81页

作者： Humphries, Stephen P. Brigham Young Univ Dept Math Provo UT 84602 USA

We investigate the properties of certain operators that were used in previous papers to create geometric and algebraic intersection number functions. Using these operators we show how to construct a general intersection theory and then we investigate properties of certain polynomials that arise naturally in this context. We indicate connections to twin primes.

关键词： Intersection function Dehn twist Chebyshev polynomials Dickson polynomials simple close curve twin primes divisibility sequences

来源：评论

学校读者我要写书评

暂无评论

Applied algebra : Codes, Ciphers and Discrete Algorithms, Second Edition 2

引用

丛书名： Discrete mathematics and its applications

2009年

作者： Hardy, Darel W.

ISBN: (数字)9781439894699

ISBN: (纸本)9781420071429

Using mathematical tools from number theory and finite fields, Applied algebra: Codes, Ciphers, and Discrete Algorithms, Second Edition presents practical methods for solving problems in data security and data integrity. It is designed for an applied algebra course for students who have had prior classes in abstract or linear algebra. While the content has been reworked and improved, this edition continues to cover many algorithms that arise in cryptography and error-control codes. New to the Second EditionA CD-ROM containing an interactive version of the book that is powered by Scientific Notebook®, a mathematical word processor and easy-to-use computer algebra systemNew appendix that reviews prerequisite topics in algebra and number theoryDouble the number of exercisesInstead of a general study on finite groups, the book considers finite groups of permutations and develops just enough of the theory of finite fields to facilitate construction of the fields used for error-control codes and the Advanced Encryption Standard. It also deals with integers and polynomials. Explaining the mathematics as needed, this text thoroughly explores how mathematical techniques can be used to solve practical problems. About the AuthorsDarel W. Hardy is Professor Emeritus in the Department of Mathematics at Colorado State University. His research interests include applied algebra and *** Richman is a professor in the Department of Mathematical Sciences at Florida Atlantic University. His research interests include Abelian group theory and constructive *** L. Walker is Associate Dean Emeritus in the Department of Mathematical Sciences at New Mexico State University. Her research interests include Abelian group theory, appl

关键词： mathematics \u0026 statistics

来源：评论

学校读者我要写书评

暂无评论

Milne's volume function and vector symmetric polynomials

引用

JOURNAL OF SYMBOLIC COMPUTATION 2009年第5期44卷 583-590页

作者： Briand, Emmanuel Rosas, Mercedes Univ Seville Dept Algebra Fac Matemat E-41012 Seville Spain

The number of real roots of a system of polynomial equations fitting inside a given box call be counted using a vector symmetric polynomial introduced by P. Milne, the Volume function. We provide the expansion of Milne's volume function in the basis of monomial vector symmetric functions, and observe that only monomial functions of a particular kind appear in the expansion, the squarefree monomial functions. By means of an appropriate specialization of the vector symmetric Newton identities, we derive an inductive formula that expresses the squarefree monomial functions in the power sums basis. As a corollary, we obtain an inductive formula that writes Milne's Volume function in the power sums basis. The lattice of the sub-hypergraphs of a hypergraph appears in a natural way in this setting. (C) 2008 Elsevier Ltd. All rights reserved.

关键词： Vector symmetric functions Zero-dimensional systems of equations Hypergraphs

来源：评论

学校读者我要写书评

暂无评论

Extended Zeilberger's algorithm for identities on Bernoulli and Euler polynomials

引用

JOURNAL OF number theory 2009年第9期129卷 2111-2132页

作者： Chen, William Y. C. Sun, Lisa H. Nankai Univ Ctr Combinator LPMC TJKLC Tianjin 300071 Peoples R China

We present a computer algebra approach to proving identities on Bernoulli polynomials and Euler polynomials by using the extended Zeilberger's algorithm given by Chen, Hou and Mu. The key idea is to use the contour integral definitions of the Bernoulli and Euler numbers to establish recurrence relations on the integrands. Such recurrence relations have certain parameter free properties which lead to the required identities without computing the integrals. Furthermore two new identities on Bernoulli numbers are derived. (C) 2009 Elsevier Inc. All rights reserved.

关键词： Bernoulli number Euler number Bernoulli polynomial Euler polynomial Zeilberger's algorithm

来源：评论

学校读者我要写书评

暂无评论

Counting complex disordered states by efficient pattern matching: chromatic polynomials and Potts partition functions

引用

NEW JOURNAL OF PHYSICS 2009年第2期11卷 023001 (10-023001 (10页

作者： Timme, Marc van Bussel, Frank Fliegner, Denny Stolzenberg, Sebastian Max Planck Inst Dynam & Self Org D-37073 Gottingen Germany Cornell Univ Dept Phys Ithaca NY 14853 USA

Counting problems, determining the number of possible states of a large system under certain constraints, play an important role in many areas of science. They naturally arise for complex disordered systems in physics and chemistry, in mathematical graph theory, and in computer science. Counting problems, however, are among the hardest problems to access computationally. Here, we suggest a novel method to access a benchmark counting problem, finding chromatic polynomials of graphs. We develop a vertex-oriented symbolic pattern matching algorithm that exploits the equivalence between the chromatic polynomial and the zero-temperature partition function of the Potts antiferromagnet on the same graph. Implementing this bottom-up algorithm using appropriate computer algebra, the new method outperforms standard top-down methods by several orders of magnitude, already for moderately sized graphs. As a first application, we compute chromatic polynomials of samples of the simple cubic lattice, for the first time computationally accessing three-dimensional lattices of physical relevance. The method offers straightforward generalizations to several other counting problems.

关键词： polynomials PHYSICS CHEMISTRY computer science ALGORITHMS ANTIFERROMAGNETISM

来源：评论

学校读者我要写书评

暂无评论

Matrix differential equations and scalar polynomials satisfying higher order recursions

引用

JOURNAL OF MATHEMATICAL ANALYSIS AND applications 2009年第1期354卷 1-11页

作者： Duran, Antonio J. Grunbaum, F. Alberto Univ Calif Berkeley Dept Math Berkeley CA 94720 USA Univ Seville Dept Anal Matemat E-41080 Seville Spain

We show that any scalar differential operator with a family of polynomials as its common eigenfunctions leads canonically to a matrix differential operator with the same property. The construction of the corresponding family of matrix valued polynomials has been studied in [A. Duran. A generalization of Favard's theorem for polynomials satisfying a recurrence relation, J. Approx. theory 74 (1993) 83-109;A. Duran, On orthogonal polynomials with respect to a positive definite matrix of measures, Canad. J. Math. 47 (1995) 88-112;A. Durin, W van Assche, Orthogonal matrix polynomials and higher order recurrence relations, Linear algebra Appl. 219 (1995) 261-280] but the existence of a differential operator having them as common eigenfunctions had not been considered. This correspondence goes only one way and most matrix valued situations do not arise in this fashion. We illustrate this general construction with a few examples. In the case of some families of scalar valued polynomials introduced in [EA. Grunbaum, L. Haine, Bispectral Darboux transformations: An extension of the Krall polynomials, Int. Math. Res. Not. 8 (1997) 359-392] we take a first look at the algebra of all matrix differential operators that share these common eigenfunctions and uncover a number of phenomena that are new to the matrix valued case. (c) 2008 Elsevier Inc. All rights reserved.

关键词： Orthogonal polynomials Orthogonal matrix polynomials Recurrence relations Differential equations Bispectral problem

来源：评论

学校读者我要写书评

暂无评论

An efficient algorithm for decomposing multivariate polynomials and its applications to cryptography

引用

JOURNAL OF SYMBOLIC COMPUTATION 2009年第12期44卷 1676-1689页

作者： Faugere, Jean-Charles Perret, Ludovic Univ Paris 06 UPMC CNRS LIP6INRIACtr Paris RocquencourtSALSA ProjectU F-75016 Paris France

In this paper, we present an efficient and general algorithm for decomposing multivariate polynomials of the same arbitrary degree. This problem, also known as the Functional Decomposition Problem (FDP), is classical in computer algebra. It is the first general method addressing the decomposition of multivariate polynomials (any degree. any number of polynomials). As a byproduct, our approach can be also used to recover an ideal I from its kth power I-k. The complexity of the algorithm depends on the ratio between the number of variables (n) and the number of polynomials (u). For example, polynomials of degree four can be decomposed in O(n(12)), when this ratio is smaller than 1/2. This work was initially motivated by a cryptographic application, namely the cryptanalysis of 2R(-) schemes. From a cryptographic point of view, the new algorithm is so efficient that the principle of two-round schemes, including 2R(-) schemes, becomes useless. Besides, we believe that our algorithm is of independent interest. (c) 2008 Elsevier Ltd. All rights reserved.

关键词： Multivariate polynomials decomposition Grobner bases Cryptography

来源：评论

学校读者我要写书评

暂无评论

Evolution of railway network flexibility: The Spanish broad gauge case

引用

MATHEMATICS AND computerS IN SIMULATION 2009年第8期79卷 2317-2332页

作者： Roanes-Lozano, Eugenio Laita, Luis M. Roanes-Macias, Eugenio Wester, Michael J. Luis Ruiz-Lozano, Jos Roncero, Carlos Univ Complutense Madrid Dept Algebra E-28040 Madrid Spain Univ Politecn Madrid Dept Artificial Intelligence E-28660 Madrid Spain Univ New Mexico Dept Math & Stat Albuquerque NM 87131 USA Univ Seville Escuela Super Ingn Ind E-41092 Seville Spain Univ Extremadura Esc Ingn Ind Dept Ingn Elect & Elect E-06071 Badajoz Spain

The length of the Spanish broad gauge network has decreased in the 1956-2006 period. When looking at different railway maps through this period, it seems that the network is offering fewer and fewer alternatives when a line is cut, that is, the network is becoming less and less flexible. The goal of this article is to prove that the flexibility of the Spanish broad gauge network has decreased substantially in the 1956-2006 period. We have considered the network as a graph (ignoring traditional railway quality indicators such as commercial speed, number of tracks, electrifications, signaling, ...) and we have chosen two simple indicators as accurate in this sense: the number of cycles (cycles provide an alternative to reach a station if there is a problem in one line) and the number of stations of intermediate degree. To achieve this, we have developed a piece of software that is an ad hoc extension of Maple's networks package. (C) 2008 IMACS. Published by Elsevier B.V. All rights reserved.

关键词： Railway network analysis Graph theory computer algebra systems

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：