# On Berge Multiplication for Monotone Boolean Dualization

@inproceedings{Boros2008OnBM, title={On Berge Multiplication for Monotone Boolean Dualization}, author={Endre Boros and Khaled M. Elbassioni and Kazuhisa Makino}, booktitle={ICALP}, year={2008} }

Given the prime CNF representation φof a monotoneBoolean function f:{0,1} n→{0,1}, the dualization problem calls for finding thecorresponding prime DNF representation ψoff. A very simple method (called Bergemultiplication[2] [Page 52---53]) works by multiplying outthe clauses of φfrom left to right in some order,simplifying whenever possible using the absorption law. Weshow that for any monotone CNF φ, Berge multiplicationcan be done in subexponential time, and for many interestingsubclasses of… Expand

#### Figures and Topics from this paper

#### 6 Citations

Algorithmic and Computational Complexity Issues of MONET

- Computer Science
- 2008

Several restricted classes of Monet are shown to be solvable in logarithmic space, which improves previously known polynomial time bounds and shows Monet to be in the complexity class of fixed-parameter tractable problems with respect to several parameters. Expand

Polynomially solvable cases of hypergraph transversal and related problems

- Computer Science, Mathematics
- 2011

The hypergraph transversal problem is shown to be solvable in output polynomial time for a number of hypergraph classes, and tight sublinear upper bounds on the readability of a monotone Boolean function given in CNF (or DNF) form are given, parameterized by the number of terms in the CNF and the maximum number of variables in the intersection of any constant number of Terms. Expand

Lower Bounds for Three Algorithms for the Transversal Hypergraph Generation

- Mathematics, Computer Science
- WG
- 2007

It is shown that none of the new algorithms improving the sequential method is output-polynomial, by proving lower bounds for all three algorithms. Expand

Lower bounds for three algorithms for transversal hypergraph generation

- Computer Science, Mathematics
- Discret. Appl. Math.
- 2009

It is shown that none of the three new algorithms improving the sequential method for hypergraph generation are output-polynomial, by proving lower bounds for all three algorithms. Expand

A transversal hypergraph approach for the frequent itemset hiding problem

- Mathematics, Computer Science
- Knowledge and Information Systems
- 2015

Experimental evaluation of the proposed approach on a number of real datasets has shown that the produced sanitized databases exhibit higher accuracy when compared with the solutions of other well-known approaches. Expand

Fast algorithms for implication bases and attribute exploration using proper premises

- Mathematics, Computer Science
- Annals of Mathematics and Artificial Intelligence
- 2013

A new algorithm for the fast computation of proper premises is presented, based on a known link between proper premises and minimal hypergraph transversals, and heuristic evidence that an approach based on proper premises will also be beneficial for other applications is provided. Expand

#### References

SHOWING 1-10 OF 55 REFERENCES

On the Complexity of the Multiplication Method for Monotone CNF/DNF Dualization

- Computer Science, Mathematics
- ESA
- 2006

The first non-trivial upper-bounds on the complexity of the (generalized) multiplication method are presented, showing that if the grouping of the clauses is done in an output-independent way, then multiplication can be performed in sub-exponential time (n|ψ|) O( √ |Φ|) | Φ| O(log n) . Expand

Dual subimplicants of positive Boolean functions

- Mathematics
- 1998

Given a positive Boolean function fand a subset δ of its variables, we give a combinatorial condition characterizing the existence of a prime implicant Dˆof the Boolean dual f d of f having the… Expand

Computational aspects of monotone dualization: A brief survey

- Computer Science, Mathematics
- Discret. Appl. Math.
- 2008

This paper focuses on the famous paper by Fredman and Khachiyan, which showed that the dualization of monotone disjunctive normal forms is solvable in quasi-polynomial time (and thus most likely not co-NP-hard), as well as on follow-up works. Expand

Efficient Read-Restricted Monotone CNF/DNF Dualization by Learning with Membership Queries

- Mathematics, Computer Science
- Machine Learning
- 2004

An incremental output polynomial time algorithm is given for exact learning both the read-k CNF and (not necessarily read restricted) DNF descriptions of f, the only method of obtaining information about f through membership queries. Expand

New Results on Monotone Dualization and Generating Hypergraph Transversals

- Mathematics, Computer Science
- SIAM J. Comput.
- 2003

It is shown that duality of two monotone CNFs can be disproved with limited nondeterminism and feasible in polynomial time with O(log2 n/\log log n) suitably guessed bits. Expand

Exact Transversal Hypergraphs and Application to Boolean µ-Functions

- Computer Science, Mathematics
- J. Symb. Comput.
- 1994

It is shown that hypergraphs are recognizable in polynomial time and that their minimal transversals as well as their maximal independent sets can be generated in lexicographic order withPolynomial delay between subsequent outputs, which is impossible in the general case unless P= NP. Expand

Dual-Bounded Generating Problems: All Minimal Integer Solutions for a Monotone System of Linear Inequalities

- Computer Science, Mathematics
- SIAM J. Comput.
- 2002

The results imply, in particular, that the problem of incrementally generating all minimal integer solutions to a monotone system of linear inequalities can be done in quasi-polynomial time. Expand

Generating all Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms

- Mathematics, Computer Science
- SIAM J. Comput.
- 1980

It is shown that it is possible to apply ideas of Paull and Unger and of Tsukiyama et al. to obtain polynomial-time algorithms for a number of special cases, e.g. the efficient generation of all maximal feasible solutions to a knapsack problem. Expand

Generating all maximal independent sets of bounded-degree hypergraphs

- Mathematics, Computer Science
- COLT '97
- 1997

This work shows that any monotone function with a read-k CNF representation can be learned in terms of its DNF representation with membership queries alone in time polynomial in the DNF size and n assuming k is some fixed constant. Expand

On the Complexity of Some Enumeration Problems for Matroids

- Computer Science, Mathematics
- SIAM J. Discret. Math.
- 2005

An incremental polynomial-time algorithm for enumerating all minimal (maximal) subsets of a matroid defined by an independence oracle on ground set S which span (do not span) $A$. Expand