10
$\begingroup$

Call a monotone boolean function $f$ a matroid function if its minterms are bases of some matroid. I am interested in monotone circuit complexity of such functions, even when we "tie hands" of these circuits as follows.

Take a monotone boolean circuit and replace Or gates by Sum gates, and And gates by Product gates. The resulting monotone arithmetic circuit will (syntactically) produce some multivariate polynomial. Say that a circuit is read-$r$ times circuit if every variable in this produced polynomial has degree at most $r$. So let $B_r(f)$ denote the minimum number of gates in a read-$r$ times monotone circuit computing $f$, and $B(f)$ be the minimum of $B_r(f)$ over all $r\geq 1$.

Question: Are there explicit matroid functions $f$ known with $B_r(f)$ large? At least for $r=1$.

Motivation: Every monotone boolean function $f$ defines a natural minimization problem: given an assignment of nonnegative weights to the variables, compute the minimum weight of a minterm of $f$; the weight of a minterm is the sum of weights of its variables. One can show that $B_r(f)$ is a lower bound on the number of operations used by any "pure" dynamic programming algorithm approximating the minimization problem on $f$ within the factor $r$; a DP algorithm is "pure" if it can be implemented as $(\min,+)$ circuit.

Now, keep our hats: by Edmonds-Rado theorem, for every matroid function $f$, the minimization problem on $f$ can be solved by the standard greedy algorithm, even exactly, for all input weightings! So, the measure $B_r(f)$ reflects the approximation weakness of pure DP algorithms when compared with greedy algorithms.

It is known that there are at least $2^{2^n/n^{3/2}}$ matroid functions; see Knuth 1974. So, matroid functions of $n$ variables with $B(f)\geq 2^n/n^2$ exist. (Clearly, even non-monotone circuit complexity of some such function is exponential.)

My question is whether we know explicit examples, at least for $B_r(f)$ with bounded $r$. Of course, we have several lower bounds for monotone circuits, even for unbounded $r$. But do any of them works also for matroid functions? Note that for $r=1$, the hands of circuits are extremely tied: boolean functions computed at inputs of an And gate cannot then share a common variable. So, at least for $r=1$, we don't need the entire power of Razborov's method of approximations:lower bounds for read-once monotone circuits should come much easier.


[ADDED 16.04.2016] I just realized that the case $r=1$ is indeed easy. If a boolean function $f$ is homogeneous (all minterms have the same cardinality) then $B_1(f)$ is at least the monotone arithmetic $(+,\times)$ circuit complexity of $f$. [Read-once circuits cannot use the idempotence $x^2=x$.] Let now $h$ be the spanning tree function: minterms are spanning trees of $K_n$. This is a matroid function (graphic matroid). Jerrum and Snir have shown that the $(+,\times)$ complexity of $h$, and hence, also $B_1(h)$ is exponential in $n$. On the other hand, as a boolean function, $h$ is just the graph connectivity function CONN, and a well-known pure DP algorithm of Floyd-Warshall yields $B(h)=O(n^3)$. So, my question actually asks what happens for $r>1$, the first interesting case being $r=2$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.