Avoiding Range via Turan-Type Bounds

In this paper, we propose a new approach to the range avoidance problem for ${\mathrm{𝖭𝖢}}_k^0$ circuits via Turan-type extremal problems in hypergraphs. For an ${\mathrm{𝖭𝖢}}_k^0$ circuit $C$, for each function $f_i\in C$ where $i\in [m]$, let $I(f_i)$ denote the set of input variables that $f_i$ depends on. Let $H_C$ denote the hypergraph defined as follows: Let $V$ be the set of inputs in $C$. For $1\le i\le m$, define a hyperedge $e_i$ as $\{x_j\mid j\in [n],x_j\in I(f_i)\}$. Thus the multiset $E=\{\{e_i\mid i\in [m]\}\}$ has exactly $m$ elements, each of size at most $k$. Let $ℱ$ be the family of functions that appear in the circuit $C$, and let $\varphi :E\to ℱ$ be a labelling of the edges of the hypergraph $H$ with the corresponding function. Without loss of generality, by assigning colors to Boolean bits, say red $R$ for $0$, and blue $B$ for $1$, we can interpret these functions as functions from ${\{R,B\}}^k\to \{R,B\}$, which induces a color to the hyperedge given any $2$-coloring of the vertices of the hypergraph. A $2$-coloring of the hyperedges of $H$ is said to be a $\varphi$-coloring if there is a vertex coloring which induces this edge coloring via $\varphi$. With this notation, we state the following theorem, which essentially follows from the above definition (see section 3).

The main idea of the above proof is that it suffices to identify a sub-hypergraph $H$ in $H_C$ such that there is an edge-coloring of $H$ which is not $\varphi$-coloring on $H$. If we can ascertain the existence of a copy of $\mathscr{H}$’ by extremal hypergraph theory, then it can be leveraged to solve the Avoid problem. In particular, this formulates range avoidance problem in terms of Turan-type extremal problems in hypergraphs of the following kind - for a fixed family of hypergraphs $\mathscr{H}$, what is the maximum number of edges that can exist in an $n$-vertex hypergraph that avoids any member of the family $H$ as an (induced) subgraph? This is particularly well-studied for $k$-uniform hypergraphs and is denoted by ${\mathrm{𝖾𝗑}}_k(n,\mathscr{H})$. Notice that the family $\mathscr{H}$ may critically depend on the set of functions $ℱ$, and the mapping $\varphi$, and hence on the circuit $C$. A natural question is, is there a family of hypergraphs $\mathscr{H}$ that works for all circuits in the circuit class¹¹1We remark that while it may not be easy to find the hypergraph structure from the given circuit in general, for the important special cases of the problem mentioned in the previous discussion, just the exhaustive search based on the circuit structure will yield efficient algorithms to find the hypergraph structure. for which we are interested to solve Avoid problem.

We first demonstrate immediate, simple applications of this framework for designing algorithms for Avoid in restricted settings. As mentioned above, [8] designed a simple iterative algorithm for solving Avoid when the input is restricted to circuits where each output function depends on at most $2$ input bits. We show that the same special case can also be solved using our approach. Thus, as a warm-up, we derive an alternative proof of the following theorem (originally due to [8]) using our framework.

As a second demonstration of our framework, we use tools from extremal graph theory to provide deterministic polynomial time algorithms for Avoid when $ℱ$ contains only $\wedge$ and $\vee$ functions that depend on exactly $k$ input bits. We remark that such powerful tools are not needed to solve this special case, as the iterative algorithmic idea due to [8] can be extended to this case as well. Nevertheless, we argue that it serves as a demonstration of our technique itself. We state both of these applications as the following proposition.

We now demonstrate the main application of this framework. Towards describing the setting of our application, we study the complexity of Avoid in the restricted case of when the circuit is monotone. A first observation is that by applying De Morgan’s law we can reduce the Avoid (when $m>2n$) in polynomial time to $𝒞$-Avoid where $𝒞$ is restricted to monotone circuits, where reduction preserves the depth of the circuit and at most doubles the size of the circuit. Hence, solving Avoid even for monotone circuits implies breakthrough circuit lower bounds. We provide the details of the following proposition in the full version [16].

Therefore, we can restrict our attention to solving the range avoidance problem for the monotone circuits. We also observe the following corollary for the case of ${\mathrm{𝖭𝖢}}_k^0$ circuits, which are the current boundary for polynomial time algorithms solving Avoid. For any $k>0$, if $m>2n$, ${\mathrm{𝖭𝖢}}_k^0$-Avoid reduces to Monotone-${\mathrm{𝖭𝖢}}_{2k}^0$-Avoid in deterministic polynomial time. In particular, when $m>2n$, ${\mathrm{𝖭𝖢}}_3^0$-Avoid reduces to Monotone-${\mathrm{𝖭𝖢}}_6^0$-Avoid in deterministic polynomial time. In the remaining part of the paper, we use the framework in Theorem 1 to show polynomial time algorithms for Monotone-${\mathrm{𝖭𝖢}}_3^0$-Avoid and related problems.

We now show the main technical application of the framework in the case when $ℱ$ contains only MAJ function on $k$ inputs, with the additional constraint that two functions should depend on at most one common input variable. As per the above formulation, this makes the hypergraph to be linear and $k$-uniform. In the setting of $k$-uniform linear hypergraphs, using Turan-type results for specifically designed graphs in $\mathscr{H}$, we can use Theorem 1 for deriving polynomial time algorithms for solving Avoid for specific classes of circuits.

Turan-type extremal problems for hypergraphs were introduced by [1] and bounds are known (see [12] for a survey) for ${\mathrm{𝖾𝗑}}_k(n,\mathscr{H})$ for a few hypergraphs $\mathscr{H}$. Bounds are known for when $\mathscr{H}$ is a $k\times k$ grid [5], wickets [19], Fano plane [13] (see section 2 for a brief overview of Turan-type extremal problems, and exact definition of these hypergraphs). We exhibit several different fixed hypergraphs $H$ and use them to provide different proofs of the following algorithmic upper bound

Our proof relies on a reduction of the problem to a more restricted case of Monotone-${\mathrm{𝖭𝖢}}_3^0$-Avoid where each individual output function is the majority of three input bits. We call this version ${\text{MAJ}}_3$-Avoid. Notice that for any two functions, there can be at most two input bits that both of them can depend on. By using a combinatorial argument on the circuit, we show how to reduce ${\text{MAJ}}_3$-Avoid to the case where two functions can depend on at most one common input. We denote this version as One-Intersect-MAJ₃-Avoid. As mentioned above, using Theorem 1 along with the fact that $H_C$ is $k$-uniform, and $ℱ=\{{\text{MAJ}}_3\}$, we design polynomial time algorithms for One-Intersect-MAJ₃-Avoid where each function is majority on three inputs and two different functions depend on at most one common input bit. We exhibit several different hypergraphs $H$ - wickets (Lemma 18), $k\times k$ grid (Lemma 20), and several other structures $k$-cage, weak Fano plane, $(k,\mathrm{\ell })$-butterfly, $(k,\mathrm{\ell })$-odd kite (see full version [16]) which can be also used to derive polynomial time algorithms for One-Intersect-MAJ₃-Avoid. Extremal bounds are known for ${\mathrm{𝖾𝗑}}_k(n,\mathscr{H})$ only when $\mathscr{H}$ is a weak Fano plane, $3\times 3$ grid and the wicket. The best known bounds for ${\mathrm{𝖾𝗑}}_k(n,\mathscr{H})$ among these are when $\mathscr{H}$ is the hypergraph called a wicket (see Section 2 for a definition), and hence we use it in the proof of Theorem 5.

Observing that the above reduction to the monotone case also doubles the number of input bits on which each function depends, for ${\mathrm{𝖭𝖢}}_k^0$-Avoid with $m>2n$, this implies a reduction to Mon-${\mathrm{𝖭𝖢}}_{2k}^0$-Avoid. We use Theorem 1, with $\mathscr{H}$ as the $k\times k$ grid (see (Lemma 20)), we show that:

However, unlike the case when $k=3$, it is unclear how to reduce Monotone-${\mathrm{𝖭𝖢}}_k^0$-Avoid to ${\text{MAJ}}_k$-Avoid, and then further to ${\text{One-Intersect-MAJ}}_k$-Avoid. Indeed, designing polynomial time algorithms for Monotone-${\mathrm{𝖭𝖢}}_6^0$-Avoid itself with $m=n+O(n^{2/3})$ already leads to explicit construction of rigid matrices[6], which is an important problem in the area.

Deterministic polynomial time algorithms are known[6] for ${\mathrm{𝖭𝖢}}_3^0$-Avoid when $m\ge \frac{n^2}{\log n}$ and as mentioned above, improving the stretch constraint to $m=n+O(n^{2/3})$ would imply explicit construction of rigid matrices. We next aim to improve the stretch requirement in the above theorem to linear (in fact, to just $n$), thus improving the known bounds for the case of Monotone-${\mathrm{𝖭𝖢}}_3^0$-Avoid.

Towards this, notice that the above argument for Theorem 5 uses the bounds for the Turan number from the literature in a black-box manner. In fact, the quadratic constraints on the stretch function $m$ that we have imposed in Theorem 5 can be relaxed by using stricter variants of the power-bound conjecture in the context of Turan numbers of linear hypergraphs. In particular, [7] conjectures that there exists an $ϵ$ such that any linear hypergraph on $n$ vertices having more than $\omega (n^{2-ϵ})$ edges must contain a $(u,u-4)$-hypergraph²²2A $(u,u-4)$-hypergraph in this context is a $3$-uniform linear hypergraph which has $u-4$ edges spanning $u$ vertices. as a subgraph. The specific hypergraph of wicket is an example of a $(9,5)$-hypergraph. However, there are $(9,5)$-hypergraphs which are not suitable for our purpose. Hence, we need a stronger variant of this conjecture, which insists on having a wicket as a subgraph instead of just $(9,5)$-subgraphs.

Specifically, in the case of wickets, which we critically use in our argument for Theorem 5, [4, 19] conjectured that the Turan number for $3$-uniform hypergraphs avoiding wickets is $n^{2-o(1)}$, and this will directly improve the constraint on $m$ as $m=n^{2-o(1)}$ for Theorem 5 as well.

To go beyond the limitations posed by the above structures for which Turan number bounds are classically studied, we define a new notion of cycles called $𝒳{}_{2\mathrm{\ell }}$-cycles in $3$-uniform linear hypergraphs. We first show a new Turan-type theorem for such cycles for connected hypergraphs, which might be of independent interest.

In the context of One-Intersect-MAJ₃-Avoid where $m>n$, using the above theorem, we show that the corresponding hypergraph $H_C$ contains a loose $𝒳{}_{2\mathrm{\ell }}$ cycle. Using the framework of Theorem 1, where we show (Lemma 26) there exists an edge-coloring of $𝒳{}_{2\mathrm{\ell }}$ which is not MAJ-coloring. In addition, we note that although the cycle is not of fixed size, we can find it in $H_C$ in polynomial time. This gives us the following theorem.

Thus, while the applicability of Theorem 1 seems to impose constraints such as $k$-uniformity and one-intersection to the cases of Avoid that they can be used to solve, the above theorem indicates that along with other combinatorial reductions to such special cases, it can still lead to useful bounds for the more general problem.

We collect the preliminaries from the theory of hypergraphs that we use in the paper. We will work with hypergraphs $G(V,E)$ where $E\subseteq 2^V$. A hypergraph is linear if two edges intersect in at most one vertex - $\forall e_1,e_2\in E$, $|e_1\cap e_2|\le 1$. A hypergraph is said to be $k$-uniform if every edge has exactly $k$ elements from $V$ - $\forall e\in E,|e|=k$. We will be working with $k$-uniform linear hypergraphs, and in particular with $k=3$. We will define some of the hypergraphs that are used in the paper.

A $k\times k$ grid in a hypergraph is a set of $k^2$ vertices $\{v_{11},v_{12},\mathrm{\dots }{v}_{kk}\}$ such that there are edges $r_1,r_2,\mathrm{\dots }{r}_k,c_1,c_2,\mathrm{\dots }{c}_k\in E$, corresponding to the vertices in the rows and columns respectively, when the vertices are arranged in the row-major order (See Figure 1(a)). A particular special hypergraph (for $k=3$) is called a wicket is the $3\times 3$ grid with one edge removed (See Figure 1(b)).

A Berge path is defined as $v_1{e}_1{v}_2\mathrm{\dots }{v}_k{e}_k{v}_{k+1}$ where each edge $e_i$ contains vertices $v_i,v_{i+1}$. A Berge path is said to be even if $k$ is even and odd otherwise. We say a hypergraph is connected if there exists a Berge path between any two pairs of vertices.

One of the classical extremal Turan-type problems introduced in the context of hypergraphs by [1] is the following: for a fixed set of $k$-uniform hypergraphs $\mathscr{H}$, what is the maximum number of edges that a $k$-uniform linear hypergraph can have, if it does not contain a subgraph isomorphic to any of the hypergraphs in the collection $\mathscr{H}$ of hypergraphs. This number is denoted by ${\mathrm{𝖾𝗑}}_k(n,\mathscr{H})$. The Turan density of $\mathscr{H}$ is denoted by $\pi (\mathscr{H})={lim}_{n\to \mathrm{\infty }}\left({\left(\genfrac{}{}{0pt}{}{n}{k}\right)}^{-1}{\mathrm{𝖾𝗑}}_k(n,\mathscr{H})\right)$. It is known that a $k$-uniform hypergraph $\mathscr{H}$ has $\pi (\mathscr{H})=0$ (also called degenerate) if and only if it is $k$-partite.

The special $3$-uniform hypergraph called wicket, denoted by $W$ (see figure 1(b)), forms an important step in our argument. We will need the following result about 3-uniform linear hypergraphs due to Solymosi [19].

A slightly weaker result was proven by [10] where they showed that ${\mathrm{𝖾𝗑}}_3(n,W)\le \frac{(1-c)n^2}{6}$. Another standard hypergraph that we will be using is the Fano plane. A Fano plane $F$ is a $3$-uniform linear hypergarph which is isomorphic to the hypergraph $H(V,E)$ with vertex set $V=[7]$ and edge set $E=\{\{1,2,3\},\{3,4,5\},\{1,5,6\},\{3,6,7\},\{2,5,7\},\{1,4,7\},\{2,4,6\}\}$. The following result shows a bound on ${\mathrm{𝖾𝗑}}_3(n,F)$.

Coming to $k$-uniform hypergraphs, we use the following result about $k\times k$ grid $G_k$, which exhibits a bound for ${\mathrm{𝖾𝗑}}_k(n,\{G_k\})$.

Various notions of cycles have been explored in the hypergraph setting. [3] consider the notion of linear cycles of length $\mathrm{\ell }$ (denoted by $C_{\mathrm{\ell }}$) which is defined as set of $\mathrm{\ell }$ edges such that each pair of adjacent edges $e_i,e_{i+1}$ (modulo $\mathrm{\ell }$) intersect in exactly one vertex and each pair of non-adjacent edges are disjoint. [3] show that ${\mathrm{𝖾𝗑}}_k(n,C_{2\mathrm{\ell }})\le c_{k,\mathrm{\ell }}{n}^{1+\frac{1}{\mathrm{\ell }}}$ and ${\mathrm{𝖾𝗑}}_k(n,C_{2\mathrm{\ell }+1})\le c_{k,\mathrm{\ell }}^{\prime }{n}^{1+\frac{1}{\mathrm{\ell }}}$. Another notion of cycles which is well-studied is that of Berge cycle of length $\mathrm{\ell }$, denoted by ${ℬ}_{\mathrm{\ell }}$ which consists of $\mathrm{\ell }$ distinct edges such that each hyperedge $e_i$ contains vertices $v_i,v_{i+1}$ where and the edge $e_{\mathrm{\ell }}$ contains vertices $v_1,v_{\mathrm{\ell }}$ where $v_1,\mathrm{\dots }{v}_{\mathrm{\ell }}$ are distinct vertices. [9] show that ${\mathrm{𝖾𝗑}}_k(n,{ℬ}_{2\mathrm{\ell }})=d_{k,\mathrm{\ell }}{n}^{1+\frac{1}{\mathrm{\ell }}}$ and ${\mathrm{𝖾𝗑}}_k(n,{ℬ}_{2\mathrm{\ell }+1})=d_{k,\mathrm{\ell }}^{\prime }{n}^{1+\frac{1}{\mathrm{\ell }}}$.

We define a new notion of cycles called $𝒳{}_{2\mathrm{\ell }}$-cycles in $3$-uniform linear hypergraphs. We define $𝒳{}_{2\mathrm{\ell }}$ to be a relaxation of ${ℬ}_{2\mathrm{\ell }}$ where $\exists e_i,e_j$ such that $|e_i\cap e_j|=1$, $i+1\equiv jmod2$ and $|i-j|>2$. We call the $(e_i,e_j)$-pair a $\chi$-structure in the cycle. Alternatively, we can view $𝒳{}_{2\mathrm{\ell }}$ using the lens of the Berge path. $𝒳{}_{2\mathrm{\ell }}$ can be thought as ${ℬ}_{2{\mathrm{\ell }}_1}\cup {ℬ}_{2{\mathrm{\ell }}_2}\cup \chi$ where ${ℬ}_{2{\mathrm{\ell }}_1}=u_1{e}_1{u}_2\mathrm{\dots }{u}_{2{\mathrm{\ell }}_1}{e}_{2{\mathrm{\ell }}_1}{u}_{2{\mathrm{\ell }}_1+1}$, ${ℬ}_{2{\mathrm{\ell }}_2}=v_1{e}_1^{\prime }{v}_2\mathrm{\dots }{v}_{2{\mathrm{\ell }}_2}{e}_{2{\mathrm{\ell }}_2}^{\prime }{v}_{2{\mathrm{\ell }}_2+1}$, $\chi =(e,e^{\prime })$ where $e,e^{\prime }\notin \{e_1,\mathrm{\dots }{e}_{2{\mathrm{\ell }}_1},e_1^{\prime },\mathrm{\dots }{e}_{2{\mathrm{\ell }}_2}^{\prime }\}$ and $e=\{u_1,2u_{{\mathrm{\ell }}_1},w\},e^{\prime }=\{v_1,2v_{{\mathrm{\ell }}_2},w\}$. If we relax the Berge paths to Berge walks (denoted by ${𝒫}_{\mathrm{\ell }}$) by allowing repetition of edges and vertices, we get a loose $𝒳{}_{2\mathrm{\ell }}$ cycle. In section 4, we shall prove extremal bounds on this structure and use it to solve range avoidance for restricted circuit classes.