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

International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC)

作者： Qi Ding Hongqing Zhang School of Mathematical Science Dalian University of Technology Dalian China

Using the framework of formal theory of partial differential equations, we consider a method of computation of the m-Hilbert polynomial (i.e. Hilbert polynomial with multivariable), which generalizes the Seiler's theorem of Hilbert polynomial with single variable. Next we present an approach to compute the number of arbitrary functions of positive differential order in the general solution, and give a formally well-posed initial problem. Finally,as applications the Maxwell equations and weakly over determined equations are considered.

关键词： polynomials Partial differential equations Differential equations Maxwell equations Scientific computing Hilbert space algebra Physics

来源：评论

学校读者我要写书评

暂无评论

polynomials that sign represent parity and Descartes rule of signs

Polynomials that sign represent parity and Descartes rule of...

引用

Annual IEEE Conference on Computational Complexity

作者： S. Basu N. Bhatnagar P. Gopalan R.J. Lipton School of Mathematics Georgia Tech Research Institute Georgia Institute of Technology USA College of Computing Georgia Tech Research Institute Georgia Institute of Technology USA

We study the sparsity of real polynomials that sign represent parity on n variables, each of which takes values from some finite subset A of integers. While the degree of such polynomials has been well studied by M. Minsky and S. Papert (1968) and J. Aspnes (1994), relatively little is known about their sparsity. We study this problem using Descartes rule of signs, a classical result in algebra, relating the sparsity of a polynomial to its number of real roots. We show that sign representing parity over {0,1,..., m - 1}/sup n/ with the degree in each variable at most m - 1 requires sparsity at least m/sup n/. We show a bound of (m - l)/sup n/ for weak representations. We show that a tradeoff exists between sparsity and degree, by constructing a sign representation that has higher degree but lower sparsity. In some cases, the difference in sparsities is exponential. We show a lower bound of n(m - 2) + 1 on the sparsity of polynomials of any degree representing parity over {0, 1, ..., m -1 }/sup n/. We prove exact bounds on the sparsity of such polynomials for any two element subset A. We show that for depth-two and-or-not circuits with a threshold gate at the top, the minimum circuit size for a function f equals the minimum sparsity of a polynomial sign representing f over a certain basis. We use this to give a simple proof that such circuits need size (3/2)/sup n/ to compute parity, which improves on previous bounds by M. Goldmann (1997). We also show a tight lower bound of 2/sup n/ for the inner product function over {0,1}/sup n/ /spl times/ {0,1}/sup n/. The main technical tool used is Descartes rule of signs. Our bounds hold for various bases where Descartes sign rule is valid.

关键词： polynomials Circuits Educational institutions algebra Character generation Mathematics Engineering profession computer science Complexity theory Computational modeling

来源：评论

学校读者我要写书评

暂无评论

theory of supports for linear codes endowed with the sum-rank metric

arXiv

引用

arXiv 2018年

作者： Martínez-Peñas, Umberto Dept. of Electrical & Computer Engineering University of Toronto Canada

The sum-rank metric naturally extends both the Hamming and rank metrics in coding theory over fields. It measures the error-correcting capability of codes in multishot matrix-multiplicative channels (e.g. linear network coding or the discrete memoryless channel on fields). Although this metric has already shown to be of interest in several applications, not much is known about it. In this work, sum-rank supports for codewords and linear codes are introduced and studied, with emphasis on duality. The lattice structure of sum-rank supports is given;characterizations of the ambient spaces (support spaces) they define are obtained;the classical operations of restriction and shortening are extended to the sum-rank metric;and estimates (bounds and equalities) on the parameters of such restricted and shortened codes are found. Three main applications are given: 1) Generalized sum-rank weights are introduced, together with their basic properties and bounds;2) It is shown that duals, shortened and restricted codes of maximum sum-rank distance (MSRD) codes are in turn MSRD;3) Degenerateness and effective lengths of sum-rank codes are introduced and characterized. In an appendix, skew supports are introduced, defined by skew polynomials, and their connection to sum-rank supports is given.94A60, 94B05, 94C99 Copyright © 2018, The Authors. All rights reserved.

关键词： Matrix algebra

来源：评论

学校读者我要写书评

暂无评论

On the polynomial parity argument complexity of the Combinatorial Nullstellensatz

arXiv

引用

arXiv 2017年

作者： Belovs, Aleksandrs Ivanyos, Gábor Qiao, Youming Santha, Miklos Yang, Siyi Faculty of Computing University of Latvia Institute for Computer Science and Control Hungarian Academy of Sciences Budapest Hungary Centre for Quantum Computation and Intelligent Systems University of Technology Sydney Australia IRIF Université Paris Diderot CNRS Paris75205 France Centre for Quantum Technologies National University of Singapore MajuLab CNRS Singapore117543 Singapore Centre for Quantum Technologies National University of Singapore Singapore117543 Singapore

The complexity class PPA consists of NP-search problems which are reducible to the parity principle in undirected graphs. It contains a wide variety of interesting problems from graph theory, combinatorics, algebra and number theory, but only a few of these are known to be complete in the class. Before this work, the known complete problems were all discretizations or combinatorial analogues of topological fixed point theorems. Here we prove the PPA-completeness of two problems of radically different style. They are PPA-Circuit CNSS and PPA-Circuit Chevalley, related respectively to the Combinatorial Nullstellensatz and to the Chevalley-Warning Theorem over the two elements field F2. The input of these problems contain PPA-circuits which are arithmetic circuits with special symmetric properties that assure that the polynomials computed by them have always an even number of zeros. In the proof of the result we relate the multilinear degree of the polynomials to the parity of the maximal parse subcircuits that compute monomials with maximal multilinear degree, and we show that the maximal parse subcircuits of a PPA-circuit can be paired in polynomial time. Copyright © 2017, The Authors. All rights reserved.

关键词： Polynomial approximation

来源：评论

学校读者我要写书评

暂无评论

Efficient Unitary Designs from Random Sums and Permutations

Efficient Unitary Designs from Random Sums and Permutations

引用

Annual IEEE Symposium on Foundations of computer Science

作者： Chi-Fang Chen Jordan Docter Michelle Xu Adam Bouland Fernando G.S.L. Brandão Patrick Hayden Institute for Quantum Information and Matter California Institute of Technology Pasadena CA USA Department of Computer Science Stanford University Stanford CA USA Stanford Institute for Theoretical Physics Stanford University Stanford CA USA

ISBN: (数字)9798331516741

ISBN: (纸本)9798331516758

A unitary k-design is an ensemble of unitaries that matches the first $k$ moments of the Haar measure. In this work, we provide two efficient constructions of k-designs on n-qubits using new random matrix theory techniques. Our first construction is based on exponentiating sums of random i.i.d. Hermitian matrices and uses O(k 2 n 2 )-many gates. In the spirit of central limit theorems, we show that this random sum approximates the Gaussian Unitary Ensemble (GUE). We then show that the product of just two exponentiated GUE matrices is already approximately Haar random. Our second construction is based on products of exponentiated sums of random permutations and uses Õ( $k$ poly ( $n$ )) many gates. The $k$ dependence is optimal (up to polylogarithmic factors) and is inherited from the efficiency of existing k-wise independent permutations. Furthermore, replacing random permutations with quantum-secure pseudorandom permutations (PRPs), we also obtain a pseudorandom unitary (PRU) ensemble that is secure under nonadaptive queries. A central feature of both proofs is a new connection between the polynomial method in quantum query complexity and the large-dimension ( $N$ ) expansion in random matrix theory. In particular, the first construction uses the polynomial method to control high moments of certain random matrix ensembles without requiring delicate Weingarten calculations. In doing so, we define and solve a moment problem on the unit circle, asking whether a finite number of equally weighted points can reproduce a given set of moments. In our second construction, the key step is to exhibit an orthonormal basis for irreducible representations of the partition algebra that has a low-degree large- $N$ expansion. This allows us to show that the distinguishing probability is a low-degree rational polynomial of the dimension $N$ .

关键词： computer science algebra Quantum mechanics Logic gates polynomials Complexity theory

来源：评论

学校读者我要写书评

暂无评论

Extremal Combinatorics 2

引用

丛书名： Texts in Theoretical computer Science. An EATCS Series

2011年

作者： Stasys Jukna

ISBN: (数字)9783642173646

ISBN: (纸本)9783642173639

This book is a concise, self-contained, up-to-date introduction to extremal combinatorics for nonspecialists. There is a strong emphasis on theorems with particularly elegant and informative proofs, they may be called gems of the theory. The author presents a wide spectrum of the most powerful combinatorial tools together with impressive applications in computer science: methods of extremal set theory, the linear algebra method, the probabilistic method, and fragments of Ramsey theory. No special knowledge in combinatorics or computer science is assumed - the text is self-contained and the proofs can be enjoyed by undergraduate students in mathematics and computer science. Over 300 exercises of varying difficulty, and hints to their solution, complete the text. This second edition has been extended with substantial new material, and has been revised and updated throughout. It offers three new chapters on expander graphs and eigenvalues, the polynomial method and error-correcting codes. Most of the remaining chapters also include new material, such as the Kruskal-Katona theorem on shadows, the Lovasz-Stein theorem on coverings, large cliques in dense graphs without induced 4-cycles, a new lower bounds argument for monotone formulas, Dvir's solution of the finite field Kakeya conjecture, Moser's algorithmic version of the Lovasz Local Lemma, Schoning's algorithm for 3-SAT, the Szemeredi-Trotter theorem on the number of point-line incidences, surprising applications of expander graphs in extremal number theory, and some other new results.

关键词： theory of Computation number theory Discrete Mathematics in computer Science Discrete Mathematics Computational Mathematics and Numerical Analysis

来源：评论

学校读者我要写书评

暂无评论

Intruder deductions, constraint solving and insecurity decision in presence of exclusive or

Intruder deductions, constraint solving and insecurity decis...

引用

Annual Symposium on Logic in computer Science

作者： H. Comon-Lundh V. Shmatikov LSV INRIA-ENS Cachan Cachan France SRI International Inc. Menlo Park CA USA

We present decidability results for the verification of cryptographic protocols in the presence of equational theories corresponding to xor and Abelian groups. Since the perfect cryptography assumption is unrealistic for cryptographic primitives with visible algebraic properties such as xor, we extend the conventional Dolev-Yao model by permitting the intruder to exploit these properties. We show that the ground reachability problem in NP for the extended intruder theories in the cases of xor and Abelian groups. This result follows from a normal proof theorem. Then, we show how to lift this result in the xor case: we consider a symbolic constraint system expressing the reachability (e.g., secrecy) problem for a finite number of sessions. We prove that such a constraint system is decidable, relying in particular on an extension of combination algorithms for unification procedures. As a corollary, this enables automatic symbolic verification of cryptographic protocols employing xor for a fixed number of sessions.

关键词： Cryptographic protocols Cryptography Equations Constraint theory Authentication Logic computer science Context modeling algebra polynomials

来源：评论

学校读者我要写书评

暂无评论

Finite Fields: theory, applications, and Algorithms

引用

1994年

作者： Gary L. Mullen Peter Jau-Shyong Shiue

ISBN: (数字)9780821877593

Because of their applications in so many diverse areas, finite fields continue to play increasingly important roles in various branches of modern mathematics, including number theory, algebra, and algebraic geometry, as well as in computer science, information theory, statistics, and engineering. Computational and algorithmic aspects of finite field problems also continue to grow in importance. This volume contains the refereed proceedings of a conference entitled Finite Fields: theory, applications and Algorithms, held in August 1993 at the University of Nevada at Las Vegas. Among the topics treated are theoretical aspects of finite fields, coding theory, cryptology, combinatorial design theory, and algorithms related to finite fields. Also included is a list of open problems and conjectures. This volume is an excellent reference for applied and research mathematicians as well as specialists and graduate students in information theory, computer science, and electrical engineering.

关键词：

来源：评论

学校读者我要写书评

暂无评论

SparseAuto: An Auto-Scheduler for Sparse Tensor Computations Using Recursive Loop Nest Restructuring

arXiv

引用

arXiv 2023年

作者： Dias, Adhitha Anderson, Logan Sundararajah, Kirshanthan Pelenitsyn, Artem Kulkarni, Milind Electrical and Computer Engineering Purdue University 610 Purdue Mall West LafayetteIN47906 United States Computer Science Virginia Tech BlacksburgVA24061 United States

Automated code generation and performance enhancements for sparse tensor algebra have become essential in many real-world applications, such as quantum computing, physical simulations, computational chemistry, and machine learning. General sparse tensor algebra compilers are not always versatile enough to generate asymptotically optimal code for sparse tensor contractions. This paper shows how to generate asymptotically better schedules for complex sparse tensor expressions using kernel fission and fusion. We present generalized loop restructuring transformations to reduce asymptotic time complexity and memory footprint. Furthermore, we present an auto-scheduler that uses a partially ordered set (poset)-based cost model that uses both time and auxiliary memory complexities to prune the search space of schedules. In addition, we highlight the use of Satisfiability Module theory (SMT) solvers in sparse auto-schedulers to approximate the Pareto frontier of better schedules to the smallest number of possible schedules, with user-defined constraints available at compile-time. Finally, we show that our auto-scheduler can select better-performing schedules and generate code for them. Our results show that the auto-scheduler provided schedules achieve orders-of-magnitude speedup compared to the code generated by the Tensor algebra Compiler (TACO) for several computations on different real-world tensors. © 2023, CC BY.

关键词： Tensors

来源：评论

学校读者我要写书评

暂无评论

A formalization of set theory without variables

引用

丛书名： Colloquium Publications Amer Mathematical Soc

1987年

作者： Alfred Tarski and Steven Givant

ISBN: (数字)9781470431877

ISBN: (纸本)9780821810415

Completed in 1983, this work culminates nearly half a century of the late Alfred Tarski's foundational studies in logic, mathematics, and the philosophy of science. Written in collaboration with Steven Givant, the book appeals to a very broad audience, and requires only a familiarity with first-order logic. It is of great interest to logicians and mathematicians interested in the foundations of mathematics, but also to philosophers interested in logic, semantics, algebraic logic, or the methodology of the deductive sciences, and to computer scientists interested in developing very simple computer languages rich enough for mathematical and scientific applications. The authors show that set theory and number theory can be developed within the framework of a new, different, and simple equational formalism, closely related to the formalism of the theory of relation algebras. There are no variables, quantifiers, or sentential connectives. Predicates are constructed from two atomic binary predicates (which denote the relations of identity and set-theoretic membership) by repeated applications of four operators that are analogues of the well-known operations of relative product, conversion, Boolean addition, and complementation. All mathematical statements are expressed as equations between predicates. There are ten logical axiom schemata and just one rule of inference: the one of replacing equals by equals, familiar from high school algebra. Though such a simple formalism may appear limited in its powers of expression and proof, this book proves quite the opposite. The authors show that it provides a framework for the formalization of practically all known systems of set theory, and hence for the development of all classical mathematics. The book contains numerous applications of the main results to diverse areas of foundational research: propositional logic; semantics; first-order logics with finitely many variables; definability and axiomatizability questions in se

关键词：

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：