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

<blockquote>
  <p>A Boolean function f is called a 2-slice function if it evaluates to zero on inputs with less than two 1’s and evaluates to one on inputs with more than two 1’s. On inputs with exactly two 1’s f may be nontrivially defined. There is a natural correspondence between 2-slice functions and graphs. Using the framework of graph complexity, we show that sufficiently strong superlinear monotone lower bounds for the very special class of 2-slice functions would imply superpolynomial lower bounds over a complete basis for certain functions derived from them. </p>
</blockquote>

<ul>
<li>Graph Complexity and Slice Functions / Satyanarayana V. Lokam,
Theory Comput. Systems 36, 71–88 (2003)</li>
</ul>

<p>also as in his comments SJ covers this similar case in his book in the section  exploring star complexity of graphs sec1.7.2.</p>

<ul>
<li><a href="http://rads.stackoverflow.com/amzn/click/3642245072" rel="nofollow">Boolean function complexity: advances and frontiers</a>, Stasys Jukna</li>
</ul>

CC BY-SA 3.0
2013-09-25T03:37:33.817Z
2013-09-25T03:37:33.817Z
vzn
<p>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? </p>

<p>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.</p>

<p>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)}}$.</p>

<p>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$? </p>

<p>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.</p>

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

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

<p><strong>Update</strong>: <a href="https://cstheory.stackexchange.com/questions/1441/hardness-of-parameterized-clique">This question</a> may be partially relevant. </p>

CC BY-SA 3.0
2011-12-08T15:46:19.463Z
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.
Stasys
CC BY-SA 3.0
2011-12-08T17:06:18.523Z
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$.
Stasys
CC BY-SA 3.0
2011-12-08T18:25:47.810Z
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.
MassimoLauria
CC BY-SA 3.0
2011-12-08T19:48:38.490Z
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.
MassimoLauria
CC BY-SA 3.0
2011-12-08T19:59:20.933Z
I must mention that for my question it is enough to show a function which is hard for $k$ and $k+1$ and with monotone complexity, say, $n^{k/2-10}$.  Your example does not exclude this. PS: is that example in your upcoming book?
MassimoLauria
CC BY-SA 3.0
2011-12-08T20:22:11.800Z
my first comment relied on graph complexity. The "$(2+c)n$" phenomenon can be found on page 13 of this [draft](http://www.thi.informatik.uni-frankfurt.de/~jukna/ftp/graph-compl.pdf). B.t.w. I haven't quite understood what you mean by being "hard for k and k+1"? (My fault, of course.)
Stasys
CC BY-SA 3.0
2011-12-08T22:05:43.947Z
(...more plausible it is mine)
MassimoLauria
CC BY-SA 3.0
2011-12-08T22:12:05.783Z
You may say that a function $f$ is easy for some weights $k_1,k_2,...,k_l$ if there is an efficiently computable $g$ such that $f(x)=g(x)$ for all $x$ such that $|x|\in\{k_1,k_2,\ldots,k_l\}$.  Function $f$ is hard if there is no such a function $g$.  Notice that if $f$ is hard for monotone circuit for a fixed weight $k$, then it is hard also for non-monotone circuits.
MassimoLauria
CC BY-SA 3.0
2012-01-15T02:17:02.337Z
am studying similar problem, was about to post question & found this question. what is f(k) in the original problem? also you cite emil jerabek in the question, are you referencing a paper? I looked through his papers & did not see one that seems to cover this area. also I was going to post an answer that it seems like [mahaney's thm on sparse sets](http://www.cs.umd.edu/~jkatz/complexity/f05/lecture6.pdf) is at least somewhat relevant to this question...? are you guys familiar with it? ps thx much stasys for posting link to your draft
vzn
CC BY-SA 3.0
2012-08-20T15:59:49.203Z
@vzn: Massimo was referring to a chat we had over lunch, continued by email. The basic observation is as follows. In Lemma 3.6 of the Alon and Boppana paper, they consider graphs induced by a random $g$-colouring. If you change the distribution to consider only random $g$-colourings such that each colour appears $m/g$-many times, one can modify the proof of the Lemma to make it work, and the resulting graphs have fixed weight.
Emil Jeřábek
CC BY-SA 3.0
2012-08-21T15:12:07.007Z
?? @Emil having trouble figuring out what you guys mean by "fixed weight". in these types of thms the positive/negative instances always increase in weight with graph size.
vzn
CC BY-SA 3.0
2012-08-21T18:03:00.760Z
@vzn: Yes. It is fixed in the sense that the exponential lower bound applies to any motonone circuits computing the given function on inputs of weight $k_1$ and $k_2$, while being allowed to output anything for other inputs. The two weights, however, depend on $n$; the best parameters for the Alon–Boppana result give something like $k_1\approx n-k_2\approx n^{2/3}$ ignoring logarithmic factors, leading to a $2^{n^{1/6-\epsilon}}$ lower bound (here $n$ is the length of the input, which is $\binom m2$ for graphs with $m$ vertices).
Emil Jeřábek
CC BY-SA 3.0
2012-08-21T18:45:23.840Z
@emil ok! inputs of what you call "fixed weight" are typically called _slices_ and many proofs in this area actually only consider two slices, the positive and negative slices, to prove the more general problem. there is in fact a very nice new paper that seems to satisfy this question, would you say log(n) weight counts as "sparse"? it has been referenced elsewhere on this site but is maybe not so well known otherwise. (apparently M. is referring to k_1, k_2 as having "few ones" above)
vzn
CC BY-SA 3.0
2013-03-07T22:58:45.360Z
@stasys in your comment above is $s(G)$ intended to be the star complexity of the graph? which suggests this question: it is known [eg refs you cite] that star complexity is a lower bound for circuit complexity; is the converse also known?
vzn
CC BY-SA 3.0
2013-03-24T20:10:59.710Z
@vzn: Unfortunately, there is no converse. If we, say, stay by depth-3 circuits, then there are graphs $G$ on $2^m$ vertices such that $s(G)\leq const$ but $f_G$ requires depth-3 circuits of size about $2^\sqrt{m}$. Take Parity. But Massimo's original question is indeed interesting: I couldn't extend Berkowitz's trick for $k$-slices to $\{k,k+1\}$-slices.
Stasys
<cc.complexity-theory><lower-bounds><circuit-complexity><parameterized-complexity><monotone>
Monotone circuit complexity of computing functions on sparse inputs
MassimoLauria
# Monotone circuit complexity of computing functions on sparse inputs

(Asked by: username_0 on 2011-12-07)

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

username_3 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](https://cstheory.stackexchange.com/questions/1441/hardness-of-parameterized-clique) may be partially relevant.

**Tags:** cc.complexity-theory, lower-bounds, circuit-complexity, parameterized-complexity, monotone

> **Comments:**
> **username_1**: 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.  
> **username_1**: 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$.  
> **username_0**: 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.  
> **username_0**: 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.  
> **username_0**: I must mention that for my question it is enough to show a function which is hard for $k$ and $k+1$ and with monotone complexity, say, $n^{k/2-10}$.  Your example does not exclude this. PS: is that example in your upcoming book?  
> **username_1**: my first comment relied on graph complexity. The "$(2+c)n$" phenomenon can be found on page 13 of this [draft](http://www.thi.informatik.uni-frankfurt.de/~jukna/ftp/graph-compl.pdf). B.t.w. I haven't quite understood what you mean by being "hard for k and k+1"? (My fault, of course.)  
> **username_0**: (...more plausible it is mine)  
> **username_0**: You may say that a function $f$ is easy for some weights $k_1,k_2,...,k_l$ if there is an efficiently computable $g$ such that $f(x)=g(x)$ for all $x$ such that $|x|\in\{k_1,k_2,\ldots,k_l\}$.  Function $f$ is hard if there is no such a function $g$.  Notice that if $f$ is hard for monotone circuit for a fixed weight $k$, then it is hard also for non-monotone circuits.  
> **username_2**: am studying similar problem, was about to post question & found this question. what is f(k) in the original problem? also you cite emil jerabek in the question, are you referencing a paper? I looked through his papers & did not see one that seems to cover this area. also I was going to post an answer that it seems like [mahaney's thm on sparse sets](http://www.cs.umd.edu/~jkatz/complexity/f05/lecture6.pdf) is at least somewhat relevant to this question...? are you guys familiar with it? ps thx much stasys for posting link to your draft  
> **username_3**: @username_2: Massimo was referring to a chat we had over lunch, continued by email. The basic observation is as follows. In Lemma 3.6 of the Alon and Boppana paper, they consider graphs induced by a random $g$-colouring. If you change the distribution to consider only random $g$-colourings such that each colour appears $m/g$-many times, one can modify the proof of the Lemma to make it work, and the resulting graphs have fixed weight.  
> **username_2**: ?? @Emil having trouble figuring out what you guys mean by "fixed weight". in these types of thms the positive/negative instances always increase in weight with graph size.  
> **username_3**: @username_2: Yes. It is fixed in the sense that the exponential lower bound applies to any motonone circuits computing the given function on inputs of weight $k_1$ and $k_2$, while being allowed to output anything for other inputs. The two weights, however, depend on $n$; the best parameters for the Alon–Boppana result give something like $k_1\approx n-k_2\approx n^{2/3}$ ignoring logarithmic factors, leading to a $2^{n^{1/6-\epsilon}}$ lower bound (here $n$ is the length of the input, which is $\binom m2$ for graphs with $m$ vertices).  
> **username_2**: @emil ok! inputs of what you call "fixed weight" are typically called _slices_ and many proofs in this area actually only consider two slices, the positive and negative slices, to prove the more general problem. there is in fact a very nice new paper that seems to satisfy this question, would you say log(n) weight counts as "sparse"? it has been referenced elsewhere on this site but is maybe not so well known otherwise. (apparently M. is referring to k_1, k_2 as having "few ones" above)  
> **username_2**: @stasys in your comment above is $s(G)$ intended to be the star complexity of the graph? which suggests this question: it is known [eg refs you cite] that star complexity is a lower bound for circuit complexity; is the converse also known?  
> **username_1**: @username_2: Unfortunately, there is no converse. If we, say, stay by depth-3 circuits, then there are graphs $G$ on $2^m$ vertices such that $s(G)\leq const$ but $f_G$ requires depth-3 circuits of size about $2^\sqrt{m}$. Take Parity. But Massimo's original question is indeed interesting: I couldn't extend Berkowitz's trick for $k$-slices to $\{k,k+1\}$-slices.  

---

## 1 answers

### Answer by username_2 on 2013-09-25. Score: 2

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:

> A Boolean function f is called a 2-slice function if it evaluates to zero on inputs with less than two 1’s and evaluates to one on inputs with more than two 1’s. On inputs with exactly two 1’s f may be nontrivially defined. There is a natural correspondence between 2-slice functions and graphs. Using the framework of graph complexity, we show that sufficiently strong superlinear monotone lower bounds for the very special class of 2-slice functions would imply superpolynomial lower bounds over a complete basis for certain functions derived from them.

* Graph Complexity and Slice Functions / Satyanarayana V. Lokam,
  Theory Comput. Systems 36, 71–88 (2003)

also as in his comments SJ covers this similar case in his book in the section exploring star complexity of graphs sec1.7.2.

* [Boolean function complexity: advances and frontiers](http://rads.stackoverflow.com/amzn/click/3642245072), username_1 Jukna


---

