• Calendar

February 19, Monday
12:00 – 14:00

Graph theory and its applications is an exciting mathematical discipline which motivates the search for new algorithms, exact structures and combinatorial properties. To illustrate this point, consider the following simple question: When can you factor a logic (Boolean) formula, into a (logically equivalent) form in which each variable appears once and only once?

For example, the function $f = ab + acd + ace$ satisfies this property since it can be factored into the "read-once" expression $f = a(b+c(d+e))$. However, the function $h = ab + bc + cd$ does not satisfy the property.

In this talk, we will present the mathematical and computational aspects of this problem. We will show several classical characterizations of read-once functions which involve combinatorics, graph theory and properties of positive (monotone) Boolean functions. We also present the first polynomial time algorithm for recognizing and factoring read-once functions. The algorithm is based on a theorem of Gurvich and on algorithms for cograph recognition and a new efficient method for checking normality.

Finally, we raise a number of questions regarding the factoring certain non-read-once functions. In particular, we are able to show that if the co-occurrence graph of a positive Boolean function f is a tree, then the function is read-twice. However, no characterization is known for general read-twice functions.