MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Elbassioni, Khaled M.dblp
Editor(s):
Azar, Yossi
Erlebach, Thomas		dblp
dblp
Not MPII Editor(s):
Azar, Yossi
Erlebach, Thomas
BibTeX cite key*:
Elbassioni2006d
Title, Booktitle
Title*:
On the Complexity of the Multiplication Method for Monotone CNF/DNF Dualization
Booktitle*:
Algorithms - ESA 2006, 14th Annual European Symposium
Event, URLs
Conference URL::
Downloading URL:
http://www.springerlink.com/content/9u4712042651q278/fulltext.pdf
Event Address*:
Zürich, Switzerland
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
11 September 2006
Event End Date:
13 September 2006
Publisher
Name*:
Springer
URL:
Address*:
Berlin, Germany
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
4168
Number:
Month:
Pages:
340-351
Year*:
2006
VG Wort Pages:
ISBN/ISSN:
978-3-540-38875-3
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
Given the irredundant CNF representation $\phi$ of a monotone Boolean function $f:\{0,1\}^n\mapsto\{0,1\}$, the dualization problem calls for finding the corresponding unique irredundant DNF representation $\psi$ of $f$. The (generalized) multiplication method works by repeatedly dividing the clauses of $\phi$ into (not necessarily disjoint) groups, multiplying-out the clauses in each group, and then reducing the result by applying the absorption law. We present the first non-trivial upper-bounds on the complexity of this multiplication method. Precisely, we show that if the grouping of the clauses is done in an output-independent way, then multiplication can be performed in sub-exponential time $(n|\psi|)^{O(\sqrt{|\phi|})}|\phi|^{O(\log n)}$. On the other hand, multiplication can be carried-out in quasi-polynomial time
$\poly(n,|\psi|)\cdot|\phi|^{o(\log |\psi|)}$, provided that the grouping is done depending on the intermediate outputs produced during the multiplication process.
URL for the Abstract:
http://dx.doi.org/10.1007/11841036_32
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{Elbassioni2006d,
AUTHOR = {Elbassioni, Khaled M.},
 EDITOR = {Azar, Yossi and Erlebach, Thomas},
 TITLE = {On the Complexity of the Multiplication Method for Monotone CNF/DNF Dualization},
 BOOKTITLE = {Algorithms - ESA 2006, 14th Annual European Symposium},
 PUBLISHER = {Springer},
 YEAR = {2006},
 VOLUME = {4168},
 PAGES = {340--351},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Z{\"u}rich, Switzerland},
 ISBN = {978-3-540-38875-3},
}

Entry last modified by Christine Kiesel, 05/02/2007
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Khaled Elbassioni		Created
12/27/2006 11:00:26 PM
Revisions
7.
6.
5.
4.
3.		Editor(s)
Christine Kiesel
Christine Kiesel
Christine Kiesel
Christine Kiesel
Christine Kiesel		Edit Dates
02.05.2007 15:29:26
10.03.2007 08:15:19
07.02.2007 19:05:11
07.02.2007 19:04:51
07.02.2007 15:12:50