\( \def\<#1>{\left<#1\right>} % an undirected version of \rightarrow: \newcommand{\mathdash}{\relbar\mkern-9mu\relbar} \def\deg#1{\mathrm{deg}(#1)} \newcommand{\dg}[1]{d_{#1}} \newcommand{\Norm}{\mathrm{N}} \newcommand{\const}[1]{c_{#1}} \newcommand{\cconst}[1]{\alpha_{#1}} \newcommand{\Exp}[1]{E_{#1}} \newcommand*{\ppr}{\mathbin{\ensuremath{\otimes}}} \newcommand*{\su}{\mathbin{\ensuremath{\oplus}}} \newcommand{\nulis}{\vmathbb{0}} %{\mathbf{0}} \newcommand{\vienas}{\vmathbb{1}} \newcommand{\Up}[1]{#1^{\uparrow}} %{#1^{\vartriangle}} \newcommand{\Down}[1]{#1^{\downarrow}} %{#1^{\triangledown}} \newcommand{\lant}[1]{#1_{\mathrm{la}}} % lower antichain \newcommand{\uant}[1]{#1_{\mathrm{ua}}} % upper antichain \newcommand{\skal}[1]{\langle #1\rangle} \newcommand{\NN}{\mathbb{N}} % natural numbers \newcommand{\RR}{\mathbb{R}} \newcommand{\minTrop}{\mathbb{T}_{\mbox{\rm\footnotesize min}}} \newcommand{\maxTrop}{\mathbb{T}_{\mbox{\rm\footnotesize max}}} \newcommand{\FF}{\mathbb{F}} \newcommand{\pRR}{\mathbb{R}_{\mbox{\tiny $+$}}} \newcommand{\QQ}{\mathbb{Q}} \newcommand{\ZZ}{\mathbb{Z}} \newcommand{\gf}[1]{GF(#1)} \newcommand{\conv}[1]{\mathrm{Conv}(#1)} \newcommand{\vvec}[2]{\vec{#1}_{#2}} \newcommand{\f}{{\mathcal F}} \newcommand{\h}{{\mathcal H}} \newcommand{\A}{{\mathcal A}} \newcommand{\B}{{\mathcal B}} \newcommand{\C}{{\mathcal C}} \newcommand{\R}{{\mathcal R}} \newcommand{\MPS}[1]{f_{#1}} % matrix multiplication \newcommand{\ddeg}[2]{\#_{#2}(#1)} \newcommand{\length}[1]{|#1|} \DeclareMathOperator{\support}{sup} \newcommand{\supp}[1]{\support(#1)} \DeclareMathOperator{\Support}{sup} \newcommand{\spp}{\Support} \newcommand{\Supp}[1]{\mathrm{Sup}(#1)} %{\mathcal{S}_{#1}} \newcommand{\lenv}[1]{\lfloor #1\rfloor} \newcommand{\henv}[1]{\lceil#1\rceil} \newcommand{\homm}[2]{{#1}^{\langle #2\rangle}} \let\daug\odot \let\suma\oplus \newcommand{\compl}[1]{Y_{#1}} \newcommand{\pr}[1]{X_{#1}} \newcommand{\xcompl}[1]{Y'_{#1}} \newcommand{\xpr}[1]{X'_{#1}} \newcommand{\cont}[1]{A_{#1}} % content \def\fontas#1{\mbox{#1}} %{\mathrm{#1}} %{\mathtt{#1}} % \newcommand{\arithm}[1]{\fontas{Arith}(#1)} \newcommand{\Arithm}[1]{\fontas{Arith}(#1)} \newcommand{\Bool}[1]{\fontas{Bool}(#1)} \newcommand{\linBool}[1]{\fontas{Bool}_{\mathrm{lin}}(#1)} \newcommand{\rBool}[2]{\fontas{Bool}_{#2}(#1)} \newcommand{\BBool}[2]{\fontas{Bool}_{#2}(#1)} \newcommand{\MMin}[1]{\fontas{Min}(#1)} \newcommand{\MMax}[1]{\fontas{Max}(#1)} \newcommand{\negMin}[1]{\fontas{Min}^{-}(#1)} \newcommand{\negMax}[1]{\fontas{Max}^{-}(#1)} \newcommand{\Min}[2]{\fontas{Min}_{#2}(#1)} \newcommand{\Max}[2]{\fontas{Max}_{#2}(#1)} \newcommand{\convUn}[1]{\fontas{L}_{\ast}(#1)} \newcommand{\Un}[1]{\fontas{L}(#1)} \newcommand{\kUn}[2]{\fontas{L}_{#2}(#1)} \newcommand{\Nor}{\mu} % norm without argument \newcommand{\nor}[1]{\Nor(#1)} \newcommand{\bool}[1]{\hat{#1}} % Boolean version of f \newcommand{\bphi}{\phi} % boolean circuit \newcommand{\xf}{\boldsymbol{\mathcal{F}}} \newcommand{\euler}{\mathrm{e}} \newcommand{\ee}{f} % other element \newcommand{\exchange}[3]{{#1}-{#2}+{#3}} \newcommand{\dist}[2]{{#2}[#1]} \newcommand{\Dist}[1]{\mathrm{dist}(#1)} \newcommand{\mdist}[2]{\dist{#1}{#2}} % min-max dist. \newcommand{\matching}{\mathcal{M}} \renewcommand{\E}{A} \newcommand{\F}{\mathcal{F}} \newcommand{\set}{W} \newcommand{\Deg}[1]{\mathrm{deg}(#1)} \newcommand{\mtree}{MST} \newcommand{\stree}{{\cal T}} \newcommand{\dstree}{\vec{\cal T}} \newcommand{\Rich}{U_0} \newcommand{\Prob}[1]{\ensuremath{\mathrm{Pr}\left\{{#1}\right\}}} \newcommand{\xI}{\boldsymbol{I}} \newcommand{\plus}{\mbox{\tiny $+$}} \newcommand{\sgn}[1]{\left[#1\right]} \newcommand{\ccompl}[1]{{#1}^*} \newcommand{\contr}[1]{[#1]} \newcommand{\harm}[2]{{#1}\,\#\,{#2}} %{{#1}\,\oplus\,{#2}} \newcommand{\hharm}{\#} %{\oplus} \newcommand{\rec}[1]{1/#1} \newcommand{\rrec}[1]{{#1}^{-1}} \DeclareRobustCommand{\bigO}{% \text{\usefont{OMS}{cmsy}{m}{n}O}} \newcommand{\dalyba}{/}%{\oslash} \newcommand{\mmax}{\mbox{\tiny $\max$}} \newcommand{\thr}[2]{\mathrm{Th}^{#1}_{#2}} \newcommand{\rectbound}{h} \newcommand{\pol}[3]{\sum_{#1\in #2}{#3}_{#1}\prod_{i=1}^n x_i^{#1_i}} \newcommand{\tpol}[2]{\min_{#1\in #2}\left\{\skal{#1,x}+\const{#1}\right\}} \newcommand{\comp}{\circ} % composition \newcommand{\0}{\vec{0}} \newcommand{\drops}[1]{\tau(#1)} \newcommand{\HY}[2]{F^{#2}_{#1}} \newcommand{\hy}[1]{f_{#1}} \newcommand{\hh}{h} \newcommand{\hymin}[1]{f_{#1}^{\mathrm{min}}} \newcommand{\hymax}[1]{f_{#1}^{\mathrm{max}}} \newcommand{\ebound}[2]{\partial_{#2}(#1)} \newcommand{\Lpure}{L_{\mathrm{pure}}} \newcommand{\Vpure}{V_{\mathrm{pure}}} \newcommand{\Lred}{L_1} %L_{\mathrm{red}}} \newcommand{\Lblue}{L_0} %{L_{\mathrm{blue}}} \newcommand{\epr}[1]{z_{#1}} \newcommand{\wCut}[1]{w(#1)} \newcommand{\cut}[2]{w_{#2}(#1)} \newcommand{\Length}[1]{l(#1)} \newcommand{\Sup}[1]{\mathrm{Sup}(#1)} \newcommand{\ddist}[1]{d_{#1}} \newcommand{\sym}[2]{S_{#1,#2}} \newcommand{\minsum}[2]{\mathrm{MinS}^{#1}_{#2}} \newcommand{\maxsum}[2]{\mathrm{MaxS}^{#1}_{#2}} % top k-of-n function \newcommand{\cirsel}[2]{\Phi^{#1}_{#2}} % its circuit \newcommand{\sel}[2]{\sym{#1}{#2}} % symmetric pol. \newcommand{\cf}[1]{{#1}^{o}} \newcommand{\Item}[1]{\item[\mbox{\rm (#1)}]} % item in roman \newcommand{\bbar}[1]{\underline{#1}} \newcommand{\Narrow}[1]{\mathrm{Narrow}(#1)} \newcommand{\Wide}[1]{\mathrm{Wide}(#1)} \newcommand{\eepsil}{\varepsilon} \newcommand{\amir}{\varphi} \newcommand{\mon}[1]{\mathrm{mon}(#1)} \newcommand{\mmon}{\alpha} \newcommand{\gmon}{\alpha} \newcommand{\hmon}{\beta} \newcommand{\nnor}[1]{\|#1\|} \newcommand{\inorm}[1]{\left\|#1\right\|_{\mbox{\tiny $\infty$}}} \newcommand{\mstbound}{\gamma} \newcommand{\coset}[1]{\textup{co-}{#1}} \newcommand{\spol}[1]{\mathrm{ST}_{#1}} \newcommand{\cayley}[1]{\mathrm{C}_{#1}} \newcommand{\SQUARE}[1]{\mathrm{SQ}_{#1}} \newcommand{\STCONN}[1]{\mathrm{STCON}_{#1}} \newcommand{\STPATH}[1]{\mathrm{PATH}_{#1}} \newcommand{\SSSP}[1]{\mathrm{SSSP}(#1)} \newcommand{\APSP}[1]{\mathrm{APSP}(#1)} \newcommand{\MP}[1]{\mathrm{MP}_{#1}} \newcommand{\CONN}[1]{\mathrm{CONN}_{#1}} \newcommand{\PERM}[1]{\mathrm{PER}_{#1}} \newcommand{\mst}[2]{\tau_{#1}(#2)} \newcommand{\MST}[1]{\mathrm{MST}_{#1}} \newcommand{\MIS}{\mathrm{MIS}} \newcommand{\dtree}{\mathrm{DST}} \newcommand{\DST}[1]{\dtree_{#1}} \newcommand{\CLIQUE}[2]{\mathrm{CL}_{#1,#2}} \newcommand{\ISOL}[1]{\mathrm{ISOL}_{#1}} \newcommand{\POL}[1]{\mathrm{POL}_{#1}} \newcommand{\ST}[1]{\ptree_{#1}} \newcommand{\Per}[1]{\mathrm{per}_{#1}} \newcommand{\PM}{\mathrm{PM}} \newcommand{\error}{\epsilon} \newcommand{\PI}[1]{A_{#1}} \newcommand{\Low}[1]{A_{#1}} \newcommand{\node}[1]{v_{#1}} \newcommand{\BF}[2]{W_{#2}[#1]} % Bellman-Ford \newcommand{\FW}[3]{W_{#1}[#2,#3]} % Floyd-Washall \newcommand{\HK}[1]{W[#1]} % Held-Karp \newcommand{\WW}[1]{W[#1]} \newcommand{\pWW}[1]{W^{+}[#1]} \newcommand{\nWW}[1]{W^-[#1]} \newcommand{\knap}[2]{W_{#2}[#1]} \newcommand{\Cut}[1]{w(#1)} \newcommand{\size}[1]{\mathrm{size}(#1)} \newcommand{\dual}[1]{{#1}^{\ast}} \def\gcd#1{\mathrm{gcd}(#1)} \newcommand{\bal}{\gamma} \newcommand{\proj}[1]{{#1}'} \newcommand{\Rectbelow}[2]{\fontas{Rect}^{\downarrow}_{#2}(#1)} \newcommand{\Rect}[2]{\fontas{Rect}_{#2}(#1)} \newcommand{\restr}[2]{\partial_{#2}{#1}} \newcommand{\coset}[1]{\mathrm{1\hspace{-0.1em}-}{#1}} %{{#1}^*} \)

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:

  1. A pure DP algorithm for the minimum weight Steiner tree problem [HTML]

    The Dreyfus-Levin-Wagner pure DP algorithm for this problem is presented.

  2. 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$.

  3. 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}$.

  4. Boolean bounds for (max,+) circuits [HTML]

    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.

  5. 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.

  6. 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:
  7. 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\}$.

  8. 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\}$.

  9. Envelope bounds for tropical circuits [HTML]

    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$.

  10. Depth of tropical circuits [HTML]

    A general lower bound on the depth of tropical $(\min,+)$ and $(\max,+)$ circuits is proved, and two applications are given.

  11. 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$).

  12. 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.

  1. Can the L(A)/Max(A) gap be large? [1 problem, HTML]

  2. Can the Max(A)/Min(A) gap be large in approximation? [3 problems, HTML]

  3. Is the Bellman-Ford-Moore single source shortest $s$-$t$ path (min,+) circuit optimal? [1 problem, HTML]

  4. Can reciprocal inputs speed up non-homogeneous (max,+) circuits? [2 problems, HTML]

  5. Matroids, greedy algorithm, and approximating tropical circuits [4 problems, HTML]

  6. ...

Miscellaneous comments

  1. Pure DP versus LP algorithms [HTML]

  2. What do circuits produce and what they actually compute [HTML]

  3. What input weights do we used to prove lower bounds? [HTML]

  4. ....

Local copies of some not-easy-to find publications


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:

Complexity measures. Given a finite set $A\subseteq\NN^n$ of vectors, the complexity measures we are interested in are:

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$.

  Jump back ☝


⇦   Back to the home page of the book