12

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.

Community
  • 1
MassimoLauria
  • 1,841
  • 16
  • 21
  • 2
    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 Dec 08 '11 at 15:46
  • 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$. – Stasys Dec 08 '11 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. – MassimoLauria Dec 08 '11 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. – MassimoLauria Dec 08 '11 at 19:48
  • 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 Dec 08 '11 at 19:59
  • 2
    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.) – Stasys Dec 08 '11 at 20:22
  • (...more plausible it is mine) – MassimoLauria Dec 08 '11 at 22:05
  • 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 Dec 08 '11 at 22:12
  • 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 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 Jan 15 '12 at 02:17
  • @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 Aug 20 '12 at 15:59
  • ?? @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 Aug 21 '12 at 15:12
  • @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 Aug 21 '12 at 18:03
  • @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 Aug 21 '12 at 18:45
  • @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 Mar 07 '13 at 22:58
  • @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 Mar 24 '13 at 20:10

1 Answers1

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.

vzn
  • 11,014
  • 2
  • 31
  • 64