\( \newcommand{\nlength}[1]{\|#1\|} \newcommand{\ccompl}[1]{Y_{#1}} \newcommand{\ppr}[1]{X_{#1}} \def\<#1>{\left<#1\right>} \newcommand{\CC}{\mathbf{C}} \newcommand{\F}{\mathcal{F}} \newcommand{\f}{\mathcal{F}} \newcommand{\rnw}{\mathbf{w}} \newcommand{\RR}{\mathbb{R}} \newcommand{\NN}{\mathbb{N}} \newcommand{\skal}[1]{\left\langle #1\right\rangle} \DeclareDocumentCommand\setdef{mo}{\left\{#1\IfNoValueTF{#2}{}{ : #2}\right\}} \)

Proof of the Design Lemma

Before proving this lemma, we will establish two structural facts: the Structural Lemma for (max,+) circuits, and the Decomposition Lemma for circuits over any semirings.

Recall that a DP algorithm is simple if its recursion equations only use Max and Sum (or Min and Sum) operations. Thus, each such algorithm is, in fact, a special (recursively constructed) (max,+) circuit with fanin-2 Max and Sum gates. Inputs for such a circuit are variables $x_1,\ldots,x_n$, where $x_i$ is the weigh given to the $i$-th ground-element. Gates are fanin-$2$ Max and Sum operations. Such a circuit solves some maximization problem with a linear objective function \[ f_A(x)=\max_{a\in A}\ \skal{a,x}\,, \] where $A\subset\NN^n$ is a finite set of vectors of nonnegative integers, $\NN=\{0,1,2,\ldots\}$, and $\skal{a,x}= a_1x_1+\cdots+a_nx_n$ is the scalar product. Vectors in $A$ are feasible solutions. The size of a circuit is the total number of gates in it.

Every (max,+) circuit (syntactically) produces some set $B\subset\NN^n$ of vectors as follows. At an input gate $x_i$, the singleton $\{e_i\}$ consisting of just one $0$-$1$ vector with a $1$ in the $i$-th position is produced. If $u$ is a gate at inputs of which some sets $X,Y\subseteq \NN^n$ of vectors are produced, then the set produced at the gate $u$ is the set-theoretic union $X\cup Y$ if $u$ is a Max gate, and is the cross-sum $X+Y=\{x+y\colon x\in X \mbox{ and } y\in Y\}$ of sets of vectors vectors, where $x+y=(x_1+y_1,\ldots,x_n+y_n)$. The set produced by the entire circuit is the set $B\subset\NN^n$ produced at its output gate.

If a (max,+) circuit solves some maximization problem $f_A(x)$, then the produced by the circuit set $B$ of vectors needs not to coincide with $A$. We only know that $f_A(x)=f_B(x)$ must hold for all input weightings $x\in (\NN\cup\{-\infty\})^n$. If the circuit only approximates the problem $f_A$ within some factor $r$, then we only known that $ f_A(x)/r\leq f_B(x)\leq f_A(x) $ must hold for all input weightingsn $x$. Still, also in this latter case, we have some structural information about the produced set $B$.

An $r$-shadow of a vector $a\in\{0,1\}^n$ with $m$ ones is a vector $b$ with at least $m/r$ ones such that $b\leq a$. A vector $b\in\NN^n$ is contained in a vector $a\in\NN^n$, if $b_i\leq a_i$ holds for all $i=1,\ldots,n$.

Structural Lemma: Let $A\subset \{0,1\}^n$. If $B$ is the set of vectors produced by a $(\max,+)$ circuit approximating the maximization problem $f_A$ within the factor $r$, then every vector of $B$ must be contained in at least one vector of $A$, and at least one $r$-shadow of every vector in $A$ must belong to $B$.
Proof: See here . $\Box$

On the other hand, if we know the produced by a circuit set $B\subset\NN^n$, then we can say how many gates the circuit must have: if $t$ is the number of gates, then the set $B$ must coverable by at most $t$ so-called ``balanced rectangle''. This is the content of the following lemma By a norm-measure we will mean any assignment of nonnegative real numbers $\nlength{x}$ to vectors $x\in\NN^n$ such that $\nlength{e_i}\leq 1$ for each of the $n$ unit vectors $e_i\in\{0,1\}^n$, and the measure is subadditive in that $\nlength{x+y}\leq \nlength{x}+\nlength{y}$ holds for all $x,y\in\NN^n$. In particular, the weight of vectors (sum of all entries) or their length (number of nonzero positions), or their $\ell_p$-norms are norm measures.

A rectangle is a cross-sum $X+Y=\{x+y\colon x\in X, y\in Y\}$ of two sets of vectors $X,Y\subseteq \NN^n$. Such a rectangle is $m$-balanced, if every vector in $X$ has norm between $m/3$ and $2m/3$.

Decomposition Lemma: Suppose that a set $B\subset\NN^n$ can be produced by a circuit of size $t$. Then, for every $m\geq 3$, there are at most $t$ $m$-balanced rectangles $X+Y\subseteq B$ such that every vector in $B$ of norm at least $m$ belongs to at least one of these rectangles.
Proof: See here . $\Box$


Now we are ready to prove our

Design Lemma: If $\f$ is an $(n,m,l)$-design for $m\geq 3$ and $l\leq m/3r$, then any (max,+) circuit approximating the maximization problem on $\f$ within factor $r$ must have at least $|\f|$ gates.
Proof: Let $A\subset\{0,1\}^n$ be the set of characteristic $0$-$1$ vectors of sets in $\f$. Hence, the maximization problem on $\f$ is $f_A(x)=\max_{a\in A}\skal{a,x}$. Take a $(\max,+)$ circuit of size $t$ approximating this problem within the factor $r\geq 1$, and let $B$ be the produced by this circuit set of vectors.

Set $p:=m/r$. Since our circuit producing the set $B$ has size $t$, the Decomposition Lemma (with the norm of $0$-$1$ vectors being the number of $1$s) implies that there must be at most $t$ $p$-balanced rectangles $R=X+Y$ such that $R\subseteq B$ and every vector in $B$ with at least $p$ ones must belong to at least one of these rectangles. By the Structural Lemma, the set $B$ must contain at least one $r$-shadow $b_a$ of each vector $a\in A$. Since each of these $r$-shadows has at least $m/r=p$ ones, each of them must belong to at least one of these balanced rectangles, as well. So, the set $A$ can be written as a union of at most $t$ sets $A_R=\{a\in A\colon b_a\in R\}$, where each $R$ is a $p$-balanced rectangle lying in $B$. It remains therefore to show that $|A_R|\leq 1$ holds for each such rectangle $R$; then we have the desired lower bound $t\geq |A|$.

To show this, fix a vector $a\in A_R$, and let $b_a\in R$ be its $r$-shadow belonging to $R$. Since the rectangle is $p$-balanced, this means that $b_a=x+y$ for some $x\in X$ and $y\in Y$ such that the number of $1$s in $x$ lies between $p/3$ and $2p/3$. By the Structural Lemma, every vector of $x+Y$ must be contained in some vector of $A$. But all vectors in $x+Y$ contain the same vector $x$ with at least $p/3=m/3r\geq l$ ones. Since vectors in $A$ are characteristic vectors of an $(n,m,l)$-design, this means that all vectors of $x+Y$ must be contained in our fixed vector $a$. Similarly, since vector $y$ has at least $p-2p/3= p/3\geq l$ ones, all vectors of $X+y$ must be also contained in the same vector $a$. Thus, all vectors of the rectangle $R=X+Y$ must be contained in our fixed vector $a$.

Suppose now that $|A_R|\geq 2$. Then an $r$-shadow $b_c$ of some other vector $c\neq a$ of $A$ must belong to the rectangle $R$. But $b_c$ has at least $m/r>l$ ones, meaning that then $a$ and $c$ must share more than $l$ ones, a contradiction with $A$ being an $(n,m,l)$-design. Thus $|A_R|\leq 1$, as desired. $\Box$

Reference:

  1. M. Jerrum and M. Snir, Some exact complexity results for straight-line computations over semirings, J. ACM, 29(3) (1982) 874-897. Local copy.

S. Jukna, December 2015

Go back to the comment page.