Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
On the Incompressibility of Monotone DNFs
| |
|
On the Incompressibility of Monotone DNFs
Matthias P. Krieger1 
| (1) |
Institut fur Informatik, Lehrstuhl fur Theoretische Informatik, Johann Wolfgang Goethe-Universitat Frankfurt am Main, Robert-Mayer-Strasse
11-15, D-60054 Frankfurt am Main, Germany |
Abstract We prove optimal lower bounds for multilinear circuits and for monotone circuits with bounded depth. These lower bounds state
that, in order to compute certain functions, these circuits need exactly as many OR gates as the respective DNFs. The proofs
exploit a property of the functions that is based solely on prime implicant structure. Due to this feature, the lower bounds
proved also hold for approximations of the considered functions that are similar to slice functions. Known lower bound arguments
cannot handle these kinds of approximations. In order to show limitations of our approach, we prove that cliques of size n
- 1 can be detected in a graph with n vertices by monotone formulas with O(log n) OR gates. Our lower bound for multilinear
circuits improves a lower bound due to Borodin, Razborov and Smolensky for nondeterministic read-once branching programs computing
the clique function.
Fulltext Preview (Small, Large)
|
|
|
|
|
|