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


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.