Supplements to the book "Tropical Circuit Complexity"
Here I am going to collect supplementary material to the book.
The notation used here is the same as in the book.
A brief summary of notation, complexity measures we deal with in the
book, and basic relations between these measures are given in this footnote(1).
Technical note: I am using MathJax to type math.
If math symbols are not processing, try a hard refresh,
which is executed by holding your Shift key
and then clicking the Refresh/Reload/whatever button in your favorite browser.
Excluded material
Here is some material that I decided (after some considerations)
to remove from draft versions both because of the 125 pages limitation for
this book series, and (more importantly) because this stuff could be
too technical and/or too specific and, hence, not urgently necessary
for the first acquaintance with tropical circuits.
Relatively easy stuff:
A pure DP algorithm for the minimum weight Steiner tree problem [HTML]
The Dreyfus-Levin-Wagner pure DP algorithm for this problem is presented.
Tropical convolution: a yet another application of Schnorr's bound
[HTML]
The minimum number of $\min$ or $\max$ gates in a $(\min,+)$ or $(\max,+)$
circuit computing the tropical $n$-degree convolution is exactly $n^2-2n+1$.
Simultaneous computation of all derivatives: Baur-Strassen
[HTML]
The $i$-th derivative of a set $A\subseteq\{0,1\}^n$ of vectors is the set
of vectors obtained from $A$ by first removing all vectors $a\in A$ with $a_i=0$, and then switching to $0$ the $i$th position of all remaining vectors.
A remarkable result of Baur and Strassen from 1983 implies that
the set $A$ as well as all its $n$ derivatives can be
simultaneously produced by a Minkowski $(\cup,+)$ circuit of size $\leq
5\cdot \Un{A}$.
For every antichain $A\subseteq\{0,1\}^n$, we have $\MMax{A}
\geq \sqrt{\frac{1}{cn}\cdot \Bool{B}}-n$ for an absolute constant $c\gt 0$, where
the set $B=\{\vec{1}-a\colon\ a\in A\}$ is obtained from $A$ by
interchanging $0$s and $1$s in all vectors of $A$.
A stronger lower bound $\MMax{A}\geq \Bool{A}$ (in terms of the same set $A$) holds,
as long as $-\infty$ is also allowed as an input weight.
Bellman-Ford-Moore (min,+) branching program for lightest k-walks is optimal
[HTML]
By combining a classical result
of Erdős and Gallai with the tropical Markov's bound (Lemma 4.4 in the book),
the optimality of the Bellman-Ford-Moore (min,+) branching program for the lightest walk of length
$k$ between the vertices $1$ and $n$
problem in $K_n$ is shown. Whether the Bellman-Ford-Moore shortest $s$-$t$ path (min,+) circuit is also optimal (among all (min,+) circuits) remains an
open problem. It even remains open whether the Bellman-Ford-Moore (min,+) branching program for the shortest $s$-$t$ path problem is optimal among all (min,+) branching programs.
An application of the Kirchhoff effective conductance formula
[HTML]
That the spanning tree polynomial can be computed by a monotone arithmetic $(+,\times,/)$ circuit (with division gates) of size $O(n^4)$ is directly derived from two classical results established by electrical
engineers at least 100 years ago: Kirchhoff's effective conductance formula and the machinery of star-mesh transformation.
A bit more involved stuff:
Sets with large Sidon sets inside them are hard to produce
[HTML]
The lower bound $\Un{A}\geq |B|/2$ holds for any set $A\subseteq\NN^n$ and for any subset $B\subseteq A$ which is
a Sidon set inside $A$: if $a+b=c+d$ for $a,b\in B$ and $c,d\in A$, then $\{c,d\}=\{a,b\}$.
Cover-free sets: tropical version of Schnorr's bound
[HTML]
The lower bound $\MMin{A}\geq |B|/2$ holds for any antichain $A\subseteq\{0,1\}^n$ and for any subset $B\subseteq A$ which is cover-free inside $A$: if $a + b \geq c$ for $a,b\in B$ and $c\in A$, then $c\in\{a, b\}$. The lower bound $\MMax{A}\geq |B|/2$ holds for any subset $B\subseteq A$ which is non-coverable inside $A$:
if $a + b \geq c$ for $a,b\in A$ and $c\in B$, then $c\in\{a, b\}$.
Let $A\subseteq\{0,1\}^n$ be an antichain, $m\geq 2$ be an integer, and $B=\{a\in A\colon a_1+\ldots+a_n=m\}$ be the $m$-th envelope of $A$.
If $B$ has particular properties, then both $\MMin{A}$ and $\MMax{A}$ are at least $|B|$ divided by the largest possible number $|X+Y|$ of vectors in a
rectangle $X+Y\subseteq B$ which is strongly $m$-balanced in that all vectors $x\in X$ have the same number
of $1$s lying between $m/3$ and $2m/3$.
A general lower bound on the depth of tropical $(\min,+)$ and $(\max,+)$ circuits is proved, and two applications are given.
Reciprocal inputs cannot speed up homogeneous (max,+) circuits
[HTML]
It is shown that (tropical) reciprocal inputs $-x_1,\ldots,-x_n$ cannot substantially (more than quadratically) speed up $(\max,+)$ circuits computing $(\max,+)$ polynomials $f(x)=\max_{a\in A}\skal{a,x}+\const{a}$ as long as they are homogeneous (the sum $a_1+\cdots+a_n$ of all entries is the same for all vectors $a\in A$).
Approximating hypergraph matchings by (max,+) circuits is hard
[HTML]
The greedy algorithm can approximate the maximum weight perfect matching
problem in $k$-partite graphs within the factor $r=k$.
It is shown that, if $k\geq 6$, then any $(\max,+)$ circuit approximating this problem within the factor
$r\approx 2^k$ must have an exponential number of gates. This shows that the powers of the greedy algorithm
and that of $(\max,+)$ circuits are incomparable also in approximation.
Open problems
In the book, I was rather selective when formulating only five open problems: I have included only several "frontier" (in my subjective opinion,
needless to say) ones. There are, however, not less interesting, albeit more specific but, perhaps,
easier to solve, open problems. I will formulate some of them here.
Can the L(A)/Max(A) gap be large?
[1 problem, HTML]
Can the Max(A)/Min(A) gap be large in approximation?
[3 problems, HTML]
Is the Bellman-Ford-Moore single source shortest $s$-$t$ path (min,+) circuit optimal?
[1 problem, HTML]
Can reciprocal inputs speed up non-homogeneous (max,+) circuits?
[2 problems, HTML]
Matroids, greedy algorithm, and approximating tropical circuits
[4 problems, HTML]
What do circuits produce and what they actually compute
[HTML]
What input weights do we used to prove lower bounds?
[HTML]
....
Local copies of some not-easy-to find publications
Gashkov, S.B.: On one method of obtaining lower bounds on the monotone complexity of polynomials. Vestnik MGU, Ser. 1 Math. Mech. 5, 7–13 (1987). In Russian. local copy
Kerr, L.R.: The effect of algebraic structure on the computation complexity of matrix
multiplications. Ph.D. thesis, Cornell Univ., Ithaca, N.Y. (1970)
local copyHere is my sketch of his proof.
Kuznetzov, S.E.: Circuits composed of functional elements without zero paths in the basis
{&, V, -}. Izv. Vyssh. Uchebn. Zaved. Mat., 228(5):56–63, 1981. In Russian. local copy
Markov, A.A.: Minimal relay-diode bipoles for monotonic symmetric
functions. Problemy Kibernetiki 8, 117–121 (1962). In Russian. local copy. English transl. in Problems of Cybernetics 8, 205–212 (1964)
Robacker, J.T.: Min-max theorems on shortest chains and disjoint cuts of a network. Technical Report. RM-1660, The Rand Corp. (1956)
local copy
Footnotes:
(1)
Notation. In this supplementary stuff, we use the same notation as in the book. In particular, for a vectors $x,y\in\NN^n$ and for finite sets $A,B\subseteq\NN^n$ of vectors:
$x\leq y$ means that $x_i\leq y_i$ for all positions $i=1,\ldots,n$.
$x+y$ is the componentwise sum of vectors $x$ and $y$.
$A+B$ is the Minkowski sum of sets $A$ and $B$, each vector $a\in A$ is added to all vectors $b\in B$.
We call sets $A+B\subseteq\NN^n$ of this form rectangles.
$\skal{x,y}=x_1y_1+\cdots+x_ny_n$ is the standard scalar product of vectors $x$ and $y$.
$\supp{x}$ is the set of nonzero positions of vector $x$.
$|A|$ is the number of vectors in $A$.
$A$ is an antichain if $a\not\leq b$ for any vectors $a\neq b\in A$ (vectors are incomparable under $\leq$).
$\Up{A}$ consists of all vectors $b\in \NN^n$ such that $b\geq a$ for some $a\in A$.
$\Down{A}$ consists of all vectors $b\in \NN^n$ such that $b\leq a$ for some $a\in A$.
$B$ lies above $A$ if $B\subseteq \Up{A}$.
$B$ lies below $A$ if $B\subseteq \Down{A}$.
The degree of a vector $a\in $A is the sum
$a_1+\cdots+a_n$ of all its entries.
The lower envelope $\lenv{A}$ of $A$ consists of all vectors $a\in A$ of minimal degree.
The higher envelope $\lenv{A}$ of $A$ consists of all vectors $a\in A$ of maximal degree.
$A$ is homogeneous if $\lenv{A} =\henv{A}$.
Complexity measures. Given a finite set $A\subseteq\NN^n$ of vectors, the complexity measures we are interested in are:
$\Bool{A}$ = min size of a monotone Boolean $(\lor,\land)$ circuit computing the Boolean function $f(x)=\bigvee_{a\in A}\bigwedge_{i : a_i\neq 0}x_i$. In particular, if $A\subseteq \{0,1\}^n$ , then for every input $x\in\{0,1\}^n$, $f(x)=1$ iff $x\geq a$ for some $a\in A$.
$\MMin{A}$ = min size of a tropical $(\min,+)$ circuit
computing $f(x)=\min_{a\in A}\skal{a,x}$ for all input weightings $x\in\RR_+^n$.
$\MMax{A}$ = min size of a tropical $(\max,+)$ circuit
computing $f(x)=\max_{a\in A}\skal{a,x}$ for all input weightings $x\in\RR_+^n$.
$\Arithm{A}$ = min size of a monotone arithmetic $(+,\times)$ circuit computing a polynomial $f(x)=\sum_{a\in A} \const{a}\prod_{i=1}^nx_i^{a_i}$ with $A$ as the set of exponent vectors of its monomials, and some positive integer coefficients $\const{a}$. In particular, $\Arithm{A}$ is a lower
bound on the size of any monotone arithmetic $(+,\times)$ circuit computing the polynomial $\sum_{a\in A} \prod_{i=1}^nx_i^{a_i}$.
$\Un{A}$ = min size of a Minkowski $(\cup,+)$ circuit producing the set $A$. Recall that
a Minkowski $(\cup,+)$ circuit has $n+1$ singleton sets $\{\vec{0}\},\{\vec{e}_1\},\ldots,\{\vec{e}_n\}$ of vectors as inputs, and uses the set-theoretical union $(\cup)$ and Minkowski sum $(+)$ of sets as (fanin $2$) gates. Each such circuit produces
in a natural way some set $A\subseteq\NN^n$ of vectors.
Minkowski circuits are in fact monotone arithmetic $(+,\times)$ circuits that can use additive idempotence:
the concentration is on the exponent vectors of monomials, while the acual values of nonzero coefficients are ignored.
The power of such circuits lies between that of tropical $(\min,+)$ and $(\max,+)$ circuits, and that of monotone arithmetic $(+,\times)$ circuits.
Hermann Minkowski 1864-1909.
Let us note that in the context of the current book,
the model of Minkowski circuits is used as just a convenient auxiliary
model that enables one to build bridges between circuits over different
semirings (such as tropical, arithmetic and Boolean),
and allows one to prove lower bounds on their size in a "clean" way using the standard language of vectors.
This is the only reason for why we extensively use this circuit model throughout the book.
[I feel, however, that Minkowski $(\cup,+)$ circuits deserve their own attention as a model of measuring the
"complexity" of sets of non-Boolean vectors.]
Relations. Among many other things, the following basic relations between these complexity measures are shown in the book for any antichain $A\subseteq\{0,1\}^n$.
That the gaps (1) and (3) can be exponential is shown in
this comment (Examples 1 and 2).
That the gap (2) can be exponential is shown on the shortest $s$-$t$ path problem (Theorem 3.6 in the book).
That the gap (5) can be exponential is shown on the minimum weight spanning tree problem (Theorem 3.16 in the book).
Whether the remaining gap (4) or even the gap $\MMin{A}/\MMax{A}$
can be large remains an open problem.
Coefficients can matter: there is an explicit multilinear polynomial $f(x)=\sum_{a\in A}\const{a}\prod_{i=1}^nx_i^{a_i}$ with special coefficients $\const{a}\gt 0$ requiring exponentially larger
monotone arithmetic $(+,\times)$ circuits than $\arithm{A}$ (Theorem 1.38 in the book, due to Yehudayoff).
Tropical $(\min,+)$ and $(\max,+)$ formulas and even branching programs can be
exponentially larger than tropical circuits (Theorem 5.10 in the book, due to
Hrubeš and Yehudayoff).
If negative weights are allowed, that is, if tropical circuits must solve an optimization problem not only on all input weightings $x\in\RR_+^n$ but on all weightings $x\in\RR^n$, then $\MMin{A}=\MMax{A}=\Un{A}=\arithm{A}$, and this then holds for arbitrary set $A\subseteq\NN^n$ of feasible solutions (not only for antichains $A\subseteq\{0,1\}^n$).
