Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(5)
Communication Complexity
Complexity Theory
Expressive Power
Point of View
Conjunctive Normal Form
Subscribe
Academic
Publications
On the expressive power of CNF formulas of bounded tree and cliquewidth
On the expressive power of CNF formulas of bounded tree and cliquewidth,10.1016/j.dam.2010.09.007,Discrete Applied Mathematics,Irénée Briquel,Pascal
Edit
On the expressive power of CNF formulas of bounded tree and cliquewidth
(
Citations: 2
)
BibTex

RIS

RefWorks
Download
Irénée Briquel
,
Pascal Koiran
,
Klaus Meer
We study representations of polynomials over a field K from the
point of view
of their expressive power. Three important examples for the paper are polynomials arising as permanents of bounded treewidth matrices, polynomials given via arithmetic formulas, and families of so called CNF polynomials. The latter arise in a canonical way from families of Boolean formulas in conjunctive normal form. To each such CNF formula there is a canonically attached incidence graph. Of particular interest to us are CNF polynomials arising from formulas with an incidence graph of bounded tree or cliquewidth.We show that the class of polynomials arising from families of polynomial size CNF formulas of bounded treewidth is the same as those represented by polynomial size arithmetic formulas, or permanents of bounded treewidth matrices of polynomial size. Then, applying arguments from
communication complexity
we show that general permanent polynomials cannot be expressed by CNF polynomials of bounded treewidth. We give a similar result in the case where the cliquewidth of the incidence graph is bounded, but for this we need to rely on the widely believed complexity theoretic assumption #P⊈FP/poly.
Journal:
Discrete Applied Mathematics  DAM
, vol. 159, no. 1, pp. 114, 2011
DOI:
10.1016/j.dam.2010.09.007
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
www.sciencedirect.com
)
(
www.informatik.unitrier.de
)
(
dx.doi.org
)
Citation Context
(2)
...Briquel, Koiran and Meer [
6
,12] – building on a paper by Fischer et al. [9] which deals with counting problems – considered polynomials defined by CNF formulas of bounded treewidth (see also Section 3)...
...Also, our paper can be seen as an extension of the work of Briquel, Koiran and Meer [12,
6
] by generalization from CNFformulas to general CSPs...
...Briquel, Koiran and Meer [12,
6
] give the following result...
Stefan Mengel
.
Characterizing Arithmetic Circuit Classes by Constraint Satisfaction P...
...This class of matrices and their permanent polynomials were studied further in [8,
5
] with respect to more precisely determining their expressive power...
Klaus Meer
,
et al.
An Extended TreeWidth Notion for Directed Graphs Related to the Comput...
References
(6)
Parallel Algorithms with Optimal Speedup for Bounded Treewidth
(
Citations: 23
)
Hans L. Bodlaender
,
Torben Hagerup
Journal:
Siam Journal on Computing  SIAMCOMP
, vol. 27, no. 6, pp. 17251746, 1998
On the fixed parameter complexity of graph enumeration problems definable in monadic secondorder logic
(
Citations: 78
)
Bruno Courcelle
,
Johann A. Makowsky
,
Udi Rotics
Journal:
Discrete Applied Mathematics  DAM
, vol. 108, no. 12, pp. 2352, 2001
Counting truth assignments of formulas of bounded treewidth or cliquewidth
(
Citations: 24
)
Eldar Fischer
,
Johann A. Makowsky
,
Elena V. Ravve
Journal:
Discrete Applied Mathematics  DAM
, vol. 156, no. 4, pp. 511529, 2008
Lecture notes in computer science
(
Citations: 270
)
J. Uhl
,
S. Drossopoulou
,
G. Persch
,
G. Goos
,
M. Dausmann
,
G. Winterstein
,
W. Kirchgassner
Published in 1982.
Some Exact Complexity Results for StraightLine Computations over Semirings
(
Citations: 39
)
Mark Jerrum
,
Marc Snir
Journal:
Journal of The ACM  JACM
, vol. 29, no. 3, pp. 874897, 1982
Sort by:
Citations
(2)
Characterizing Arithmetic Circuit Classes by Constraint Satisfaction Problems
Stefan Mengel
An Extended TreeWidth Notion for Directed Graphs Related to the Computation of Permanents
Klaus Meer
,
Lehrstuhl Theoretische Informatik