# Monotone circuit complexity of computing functions on sparse inputs

The weight $|x|$ of a binary string $x\in\{0,1\}^n$ is the number of ones in the string. What happens if we are interested in computing a monotone function on inputs with few ones?

We know that deciding if a graph has a $k$-clique is hard for monotone circuits (see among others Alon Boppana, 1987), but if a graph has for example at most $k^3$ edges it possible to find a monotone bounded depth circuit of size $f(k)\cdot n^{O(1)}$ which decides $k$-clique.

My question: is there any function which is hard to compute by a monotone circuit even on inputs of weight less than $k$? Here hard means circuit size $n^{{k}^{\Omega(1)}}$.

Even better: is there an explicit monotone function which is hard to compute even if we only care about inputs of weight $k_1$ and $k_2$?

Emil Jeřábek already observed that known lower bounds hold for monotone circuits that separate two classes of inputs ($a$-cliques vs maximal $(a-1)$-colorable graphs), thus at cost of some independence in the probabilistic argument it is possible to make it work for two classes of input of fixed weight. This would cause $k_2$ to be a function of $n$ which I want to avoid.

What is would really like is an explicit hard function for $k_1$ and $k_2$ much smaller than $n$ (as in the parameterized complexity framework). Even better if $k_1=k_2+1$.

Notice that a positive answer for $k_1=k_2$ would imply an exponential lower bound for arbitrary circuits.

Update: This question may be partially relevant.

• To your very first (general) question (not about Clique). I think, even the case of inputs with at most $2$ ones is very difficult. Take a bipartite $n\times m$ graph $G$ with $m=o(n)$. Assign to each vertex $u$ a boolean variable $x_u$. Let $f_G(x)$ be a monotone boolean function whose minterms are $x_u\land x_v$ for the edges $uv$ of $G$. Let $s(G)$ be the minimal size of a monotone circuit which correctly computes $f_G$ on inputs with $\leq 2$ ones. Then any lower bound $s(G)\geq (2+c)n$ for a constant $c>0$ would imply an exponential lower bound for nonmonotone circuits. Dec 8, 2011 at 15:46
• Existing arguments for monotone circuits need that many inputs with many ($\gg n/2$) ones must be rejected. The best we can do so far is to prove $\exp(\min\{a,n/b\}^{1/4})$ lower bound when circuit must accept all $b$-cliques, and reject all complete $a$-partite graphs ($a<b$). B.t.w. important is that you deal with sparse, not with dense inputs. Say, $k$-Clique requires monotone circuits of size about $n^k$ for every constant $k\geq 3$, but $(n-k)$-Clique has monotone circuits of size $O(n^2\log n)$ for every constant $k$. Dec 8, 2011 at 17:06
• I should clarify that I care about sparse inputs in the sense of sparse graph. Looking for a $k$-clique in a very sparse graph (with say $k^{10}$ edges) can be done in FPT monotone circuit size. Dec 8, 2011 at 18:25
• Your example in the first comment is very nice. If I understand correctly this is a similar issue with monotone functions which are hard on a fixed weight $k$. Using pseudo complement functions to simulate negated inputs, the circuit complexity does not differ between monotone and non-monotone case. For constant (or small) $k$ this pseudo complement can be implemented efficiently by a monotone circuit. Dec 8, 2011 at 19:48
• my first comment relied on graph complexity. The "$(2+c)n$" phenomenon can be found on page 13 of this draft. B.t.w. I haven't quite understood what you mean by being "hard for k and k+1"? (My fault, of course.) Dec 8, 2011 at 20:22

specifically considering one part of the question (eg for $k_1$=1,$k_2$=2), Lokam studied "2-slice" functions in this paper & proves that strong lower bounds on them can be generalized, therefore this is a very hard open problem related to basic complexity class separation & any such construction/explicit function would be a breakthrough; from the abstract: