12
$\begingroup$

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.

Improve this question
$\endgroup$
15
  • 2
    $\begingroup$ 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. $\endgroup$
    – Stasys
    Dec 8, 2011 at 15:46
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Stasys
    Dec 8, 2011 at 17:06
  • $\begingroup$ 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. $\endgroup$
    – MassimoLauria
    Dec 8, 2011 at 18:25
  • $\begingroup$ 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. $\endgroup$
    – MassimoLauria
    Dec 8, 2011 at 19:48
  • 2
    $\begingroup$ 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.) $\endgroup$
    – Stasys
    Dec 8, 2011 at 20:22

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.