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.
My Menu
Saved Items

On the Incompressibility of Monotone DNFs

Matthias P. KriegerContact Information

(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.

Contact Information Matthias P. Krieger
Email: mkrieger@cs.uni-frankfurt.de
Fulltext Preview (Small, Large)
Image of the first page of the fulltext


Export this article
Export this article as RIS | Text
 
Remote Address: 38.107.191.101 • Server: mpweb04
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)