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

holographic algorithms beyond matchgates

INFORMATION AND COMPUTATION 2018年第Part1期259卷 102-129页

作者： Cai, Jin-Yi Guo, Heng Williams, Tyson Univ Wisconsin Madison 1210 West Dayton St Madison WI 53706 USA Univ Edinburgh Informat Forum 10 Crichton St Edinburgh EH8 9AB Midlothian Scotland Blocher Consulting 206 North Randolph Champaign IL 61820 USA

holographic algorithms introduced by Valiant have two ingredients: matchgates, which are gadgets realizing local constraint functions by weighted planar perfect matchings, and holographic reductions, which show equivalences among problems with different descriptions via basis transformations. In this paper, we replace matchgates in the paradigm above by the affine type and the product type constraint functions, which are known to be tractable in general (not necessarily planar) graphs. We present polynomial-time algorithms to decide if a given counting problem has a holographic reduction to another problem defined by the affine or product-type functions. We also give polynomial-time algorithms to the same problems for symmetric functions, where the complexity is measured in terms of the (exponentially more) succinct representations. The latter result implies that the symmetric Boolean Holant dichotomy (Cai, Guo, and Williams, SICOMP 2016) is efficiently decidable. Our proof techniques are mainly algebraic. (c) 2018 Elsevier Inc. All rights reserved.

关键词： Counting complexity holographic algorithms

来源：评论

学校读者我要写书评

暂无评论

holographic algorithms on Domains of General Size

引用

THEORY OF COMPUTING SYSTEMS 2023年第3期67卷 417-436页

作者： Fu, Zhiguo Cai, Jin-Yi Northeast Normal Univ KLAS Sch Informat Sci & Technol Changchun 130024 Jilin Peoples R China Univ Wisconsin Dept Comp Sci Madison WI 53706 USA

An essential problem in the design of holographic algorithms is to decide whether the required signatures can be realized by matchgates under a suitable basis transformation. For domain size two, Cai and Choudhary (2007, 2009) characterized all functions directly realizable as matchgate signatures without a basis transformation, and Cai and Lu (Theory Comput. Syst. 46(3), 398-415 2010;J. Comput. Syst. Sci. 77, 41-61 2011) gave a polynomial time algorithm for the realizability problem for symmetric signatures under basis transformations. We generalize this theory to arbitrary domain size k. Specifically, we give a polynomial time algorithm for the Simultaneous Realizability Problem on domain size k >= 3 for signatures realizable by matchgates over a basis of size 1. Using this, one can decide whether suitable signatures for a holographic algorithms on domain size k are realizable and if so, to find a suitable linear basis to realize these signatures by an efficient algorithm. We dedicate this paper to the memory of Alan L. Selman, a close personal friend and a former colleague of the second author, and also a former Editor-in-Chief for this journal. The results in this paper are a demonstration of the structure and unity of complexity theory. As this is a persistent theme of Professor Selman in his multifaceted and significant contributions to our field, we dedicate it to Alan as a tribute to his life and his influential work.

关键词： holographic algorithms Matchgates Simultaneous realizability problem

来源：评论

学校读者我要写书评

暂无评论

holographic algorithms: The power of dimensionality resolved

引用

THEORETICAL COMPUTER SCIENCE 2009年第18期410卷 1618-1628页

作者： Cai, Jin-Yi Lu, Pinyan Tsinghua Univ Beijing Peoples R China Univ Wisconsin Madison WI 53706 USA

Valiant's theory of holographic algorithms is a novel methodology to achieve exponential speed-ups in computation. A fundamental parameter in holographic algorithms is the dimension of the linear basis vectors. We completely resolve the problem of the power of higher dimensional bases. We prove that 2-dimensional bases are universal for holographic algorithms. (c) 2009 Elsevier B.V. All rights reserved.

关键词： holographic algorithms Bases Dimension

来源：评论

学校读者我要写书评

暂无评论

holographic algorithms on bases of rank 2

引用

INFORMATION PROCESSING LETTERS 2014年第11期114卷 585-590页

作者： Fu, Zhiguo Yang, Fengqin Jilin Univ Sch Math Changchun 130024 Peoples R China NE Normal Univ Sch Comp Sci & Informat Technol Changchun 130117 Peoples R China

An essential problem in the design of holographic algorithms is to decide whether the required signatures can be realized under a suitable basis transformation (SRP). For holographic algorithms with matchgates on domain size 2, [1,2,4,5] have built a systematical theory. In this paper, we reduce SRP on domain size k >= 3 to SRP on domain size 2 for holographic algorithms with matchgates on bases of rank 2. Furthermore, we generalize the collapse theorem of [3] to domain size k >= 3. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Computational complexity holographic algorithms Matchgate computation SRP

来源：评论

学校读者我要写书评

暂无评论

holographic algorithms WITH MATCHGATES CAPTURE PRECISELY TRACTABLE PLANAR #CSP

引用

SIAM JOURNAL ON COMPUTING 2017年第3期46卷 853-889页

作者： Cai, Jin-Yi Lu, Pinyan Xia, Mingji Univ Wisconsin Dept Comp Sci 1210 W Dayton St Madison WI 53706 USA Shanghai Univ Finance & Econ Shanghai Peoples R China Univ Chinese Acad Sci Chinese Acad Sci State Key Lab Comp Sci Inst Software Beijing Peoples R China

Valiant introduced matchgate computation and holographic algorithms. A number of seemingly exponential time problems can be solved by this novel algorithmic paradigm in polynomial time. We show that, in a very strong sense, matchgate computations and holographic algorithms based on them provide a universal methodology to a broad class of counting problems studied in the statistical physics community for decades. They capture precisely those problems which are #P-hard on general graphs but computable in polynomial time on planar graphs. More precisely, we prove complexity dichotomy theorems in the framework of counting CSP problems. The local constraint functions take Boolean inputs and can be arbitrary real-valued symmetric functions. We prove that every problem in this class belongs to precisely three categories: (1) those which are tractable (i.e., polynomial time computable) on general graphs, or (2) those which are #P-hard on general graphs but tractable on planar graphs, or (3) those which are #P-hard even on planar graphs. The classification criteria are explicit. Moreover, problems in category (2) are tractable on planar graphs precisely by holographic algorithms with matchgates.

关键词： holographic algorithms counting problems #P dichotomy theorems

来源：评论

学校读者我要写书评

暂无评论

holographic algorithms without matchgates

引用

LINEAR ALGEBRA AND ITS APPLICATIONS 2013年第2期438卷 782-795页

作者： Landsberg, J. M. Morton, Jason Norine, Serguei Texas A&M Univ Dept Math College Stn TX 77843 USA Penn State Univ Dept Math University Pk PA 16802 USA McGill Univ Dept Math & Stat Montreal PQ Canada

The theory of holographic algorithms, which are polynomial time algorithms for certain combinatorial counting problems, surprised the complexity community by showing certain problems, very similar to #P complete problems, were in fact in the class P. In particular, the theory produces algebraic tests for a problem to be in P. In this article we describe the geometric basis of these algorithms by (i) replacing the construction of graph fragments in the procedure by the direct construction of a skew symmetric matrix, and (ii) replacing the computation of weighted perfect matchings of an auxiliary graph by computing the Pfaffian of the directly constructed skew-symmetric matrix. This procedure indicates a more geometric approach to complexity classes. It also leads to more general constructions where one replaces the "Grassmann-Pliicker identities" which test for admissibility by other algebraic tests. Natural problems treatable by these methods have been previously considered in a different context, and we present one such example. (C) 2012 Elsevier Inc. All rights reserved.

关键词： holographic algorithms Pfaffian Spinors Matchgates

来源：评论

学校读者我要写书评

暂无评论

holographic algorithms with Matchgates Capture Precisely Tractable Planar #CSP

Holographic Algorithms with Matchgates Capture Precisely Tra...

引用

IEEE 51st Annual Symposium on Foundations of Computer Science (FOCS)

作者： Cai, Jin-Yi Lu, Pinyan Xia, Mingji Univ Wisconsin Madison WI 53706 USA Microsoft Res Asia Beijing Peoples R China Chinese Acad Sci Inst Software Beijing 100864 Peoples R China

ISBN: (纸本)9780769542447

Valiant introduced matchgate computation and holographic algorithms. A number of seemingly exponential time problems can be solved by this novel algorithmic paradigm in polynomial time. We show that, in a very strong sense, matchgate computations and holographic algorithms based on them provide a universal methodology to a broad class of counting problems studied in statistical physics community for decades. They capture precisely those problems which are #P-hard on general graphs but computable in polynomial time on planar graphs. More precisely, we prove complexity dichotomy theorems in the framework of counting CSP problems. The local constraint functions take Boolean inputs, and can be arbitrary real-valued symmetric functions. We prove that, every problem in this class belongs to precisely three categories: (1) those which are tractable (i.e., polynomial time computable) on general graphs, or (2) those which are #P-hard on general graphs but tractable on planar graphs, or (3) those which are #P-hard even on planar graphs. The classification criterion is explicit. Moreover, problems in category (2) are tractable on planar graphs precisely by holographic algorithms with matchgates.

关键词： #CSP #P-hard Boolean functions Boolean inputs classification criteria complexity dichotomy theorems computational complexity constraint theory counting CSP problems exponential time problems general graphs graph theory holographic algorithms local constraint functions match gate computation matchgates planar graphs polynomial time computable real-valued symmetric functions statistical physics community

来源：评论

学校读者我要写书评

暂无评论

holographic algorithms: From Art to Science 07

Holographic Algorithms: From Art to Science

引用

39th Annual ACM Symposium on Theory of Computing

作者： Cai, Jin-Yi Lu, Pinyan Univ Wisconsin Dept Comp Sci Madison WI 53706 USA

ISBN: (纸本)9781595936318

We develop the theory of holographic algorithms. We define a basis manifold and give characterizations of algebraic varieties of realizable symmetric generators and recognizers on this manifold. We present a polynomial time decision algorithm for the simultaneous realizability problem. Using the general machinery we are able to give unexpected holographic algorithms for some counting problems, modulo certain Mersenne type integers. These counting problems are #P-complete without the moduli. Going beyond symmetric signatures, we define d-admissibility and d-realizability for general signatures, and give a characterization of 2-admissibility.

关键词： holographic algorithms matchgates signatures

来源：评论

学校读者我要写书评

暂无评论

Signature Theory in holographic algorithms

引用

ALGORITHMICA 2011年第4期61卷 779-816页

作者： Cai, Jin-Yi Lu, Pinyan Microsoft Res Asia Beijing 100190 Peoples R China Univ Wisconsin Dept Comp Sci Madison WI 53706 USA

In the theory of holographic algorithms proposed by Valiant, computation is expressed and processed in terms of signatures. We substantially develop the signature theory in holographic algorithms. This theory is developed in terms of d-realizability and d-admissibility. For the class of 2-realizable signatures we prove a Birkhoff-type theorem which determines this class. It gives a complete structural understanding of the relationship between 2-realizability and 2-admissibility. This is followed by characterization theorems for 1-realizability and 1-admissibility. Finally, using this theory of general (i.e., unsymmetric) signatures we give additional counting problems solvable in polynomial time by holographic algorithms.

关键词： holographic algorithms Signature d-realizability Complexity theory Counting problems

来源：评论

学校读者我要写书评

暂无评论

On Symmetric Signatures in holographic algorithms

引用

THEORY OF COMPUTING SYSTEMS 2010年第3期46卷 398-415页

作者： Cai, Jin-Yi Lu, Pinyan Univ Wisconsin Dept Comp Sci Madison WI 53706 USA Tsinghua Univ Dept Comp Sci & Technol Beijing 100084 Peoples R China

In holographic algorithms, symmetric signatures have been particularly useful. We give a complete characterization of these symmetric signatures over all bases of size 1. These improve previous results by Cai and Choudhary (ICALP 2006, vol. 4051, pp. 703-714, 2006) where only symmetric signatures over the Hadamard basis (special basis of size 1) were obtained. In particular, we give a complete list of Boolean symmetric signatures over bases of size 1. It is an open problem whether signatures over bases of higher dimensions are strictly more powerful. The recent result by Valiant (FOCS 2006, pp. 509-517, 2006) seems to suggest that bases of size 2 might be indeed more powerful than bases of size 1. This result is with regard to a restrictive counting version of #SAT called #Pl-Rtw-Mon-3CNF. It is known that the problem is #P-hard, and its mod 2 version is aS center dot P-hard. Yet its mod 7 version is solvable in polynomial time by holographic algorithms. This was ac complished by a suitable symmetric signature over a basis of size 2. We show that the same unexpected holographic algorithm can be realized over a basis of size 1. Furthermore we prove that 7 is the only modulus for which such an "accidental algorithm" exists.

关键词： holographic algorithms Matchgates and signatures Symmetric signatures 0-1 signatures Realizability

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：