中国科学院软件研究所机构知识库
Advanced  
ISCAS OpenIR  > 软件所图书馆  > 会议论文
Title:
the complexity of weighted boolean #csp modulo k
Author: Guo Heng ; Huang Sangxia ; Lu Pinyan ; Xia Mingji
Source: Leibniz International Proceedings in Informatics, LIPIcs
Conference Name: 28th International Symposium on Theoretical Aspects of Computer Science, STACS 2011
Conference Date: March 10, 2011 - March 12, 2011
Issued Date: 2011
Conference Place: Dortmund, Germany
Keyword: Computational complexity
Indexed Type: EI
ISSN: 1868-8969
ISBN: 9783939897255
Department: (1) University of Wisconsin-Madison Madison WI 53706 United States; (2) KTH - Royal Institute of Technology Stockholm Sweden; (3) Microsoft Research Asia Beijing China; (4) Institute of Software Chinese Academy of Sciences Beijing 100190 China
Abstract: We prove a complexity dichotomy theorem for counting weighted Boolean CSP modulo k for any positive integer k > 1. This generalizes a theorem by Faben for the unweighted setting. In the weighted setting, there are new interesting tractable problems. We first prove a dichotomy theorem for the finite field case where k is a prime. It turns out that the dichotomy theorem for the finite field is very similar to the one for the complex weighted Boolean #CSP, found by [Cai, Lu and Xia, STOC 2009]. Then we further extend the result to an arbitrary integer k. © Heng Guo, Sangxia Huang, Pinyan Lu and Mingji Xia.
English Abstract: We prove a complexity dichotomy theorem for counting weighted Boolean CSP modulo k for any positive integer k > 1. This generalizes a theorem by Faben for the unweighted setting. In the weighted setting, there are new interesting tractable problems. We first prove a dichotomy theorem for the finite field case where k is a prime. It turns out that the dichotomy theorem for the finite field is very similar to the one for the complex weighted Boolean #CSP, found by [Cai, Lu and Xia, STOC 2009]. Then we further extend the result to an arbitrary integer k. © Heng Guo, Sangxia Huang, Pinyan Lu and Mingji Xia.
Language: 英语
Content Type: 会议论文
URI: http://ir.iscas.ac.cn/handle/311060/16368
Appears in Collections:软件所图书馆_会议论文

Files in This Item:

There are no files associated with this item.


Recommended Citation:
Guo Heng,Huang Sangxia,Lu Pinyan,et al. the complexity of weighted boolean #csp modulo k[C]. 见:28th International Symposium on Theoretical Aspects of Computer Science, STACS 2011. Dortmund, Germany. March 10, 2011 - March 12, 2011.
Service
Recommend this item
Sava as my favorate item
Show this item's statistics
Export Endnote File
Google Scholar
Similar articles in Google Scholar
[Guo Heng]'s Articles
[Huang Sangxia]'s Articles
[Lu Pinyan]'s Articles
CSDL cross search
Similar articles in CSDL Cross Search
[Guo Heng]‘s Articles
[Huang Sangxia]‘s Articles
[Lu Pinyan]‘s Articles
Related Copyright Policies
Null
Social Bookmarking
Add to CiteULike Add to Connotea Add to Del.icio.us Add to Digg Add to Reddit
所有评论 (0)
暂无评论
 
评注功能仅针对注册用户开放,请您登录
您对该条目有什么异议,请填写以下表单,管理员会尽快联系您。
内 容:
Email:  *
单位:
验证码:   刷新
您在IR的使用过程中有什么好的想法或者建议可以反馈给我们。
标 题:
 *
内 容:
Email:  *
验证码:   刷新

Items in IR are protected by copyright, with all rights reserved, unless otherwise indicated.

 

 

Valid XHTML 1.0!
Copyright © 2007-2019  中国科学院软件研究所 - Feedback
Powered by CSpace