Proceedings Article, Paper @InProceedings Beitrag in Tagungsband, Workshop

 Show entries of: this year (2019) | last year (2018) | two years ago (2017) | Notes URL
 Action: login to update Options: Goto entry point

 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
 URL of the conference: URL for downloading the paper: 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:

 (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},