# Dual Bounded Generation: Polynomial, Second-order Cone and Positive
Semidefinite Matrix Inequalities

Khaled Elbassioni Khalifa University of Science and Technology, Abu Dhabi,
UAE<EMAIL_ADDRESS>
###### Abstract

In the monotone integer dualization problem, we are given two sets of vectors
in an integer box such that no vector in the first set is dominated by a
vector in the second. The question is to check if the two sets of vectors
cover the entire integer box by upward and downward domination, respectively.
It is known that the problem is (quasi-)polynomially equivalent to that of
enumerating all maximal feasible solutions of a given monotone system of
linear/separable/supermodular inequalities over integer vectors. The
equivalence is established via showing that the dual family of minimal
infeasible vectors has size bounded by a (quasi-)polynomial in the sizes of
the family to be generated and the input description. Continuing in this line
of work, in this paper, we consider systems of polynomial, second-order cone,
and semidefinite inequalities. We give sufficient conditions under which such
bounds can be established and highlight some applications.

##  1 Introduction

We consider a monotone system of inequalities of the form:

$\displaystyle\displaystyle f_{i}(\mathbf{x})\leq~{}t_{i},\quad\text{ for
}i\in[r]:=\\{1,\ldots,r\\},$ (1)

over a vector of integer variables
$\mathbf{x}=(x_{1},\ldots,x_{n})\in\mathbb{Z}_{+}^{n}$, where
$f_{i}:\mathbb{Z}_{+}^{n}\mapsto\mathbb{R}_{+}$ is a monotone (non-decreasing)
non-negative function on $\mathbb{Z}_{+}^{n}$, that is,
$\mathbf{x},\mathbf{y}\in\mathbb{Z}_{+}^{n}$ and $\mathbf{x}\geq\mathbf{y}$
imply that $f_{i}(\mathbf{x})\geq f_{i}(\mathbf{y})$, for all $i\in[r]$. A
vector $\mathbf{x}\in\mathbb{Z}_{+}^{n}$ is said to be a maximal feasible
vector (or solution) for (1) if $\mathbf{x}$ is feasible for (1) and
$\mathbf{x}+\mathbf{1}^{j}$ is not feasible for all $j\in[n]$, where
throughout we use $\mathbf{1}^{j}$ to denote the $j$-unit $n$-dimensional
vector. Likewise, a vector $\mathbf{x}\in\mathbb{Z}_{+}^{n}$ is said to be a
minimal infeasible vector for (1) if $\mathbf{x}$ is infeasible for (1) and
$\mathbf{x}-\mathbf{1}^{j}$ is feasible for all $j\in[n]$ such that $x_{j}>0$.
Let $\mathcal{F}$ and ${\mathcal{I}}$ be respectively the families of maximal
feasible and minimal infeasible vectors for (1). We are interested in
incrementally generating the family $\mathcal{F}$:

GEN$(\mathcal{F}^{\prime})$:

Given a monotone system (1), and a subfamily
$\mathcal{F}^{\prime}\subseteq\mathcal{F}$ of its maximal feasible vectors,
either find a new maximal vector
$\mathbf{x}\in\mathcal{F}\setminus\mathcal{F}^{\prime}$, or provide an
evidence that $\mathcal{F}^{\prime}=\mathcal{F}$.

Clearly, the entire family $\mathcal{F}$ can be generated by initializing
$\mathcal{F}^{\prime}=\emptyset$ and iteratively solving the above problem
$|\mathcal{F}|+1$ times. It was shown in [BEG+02] that, when each $f_{i}$ is a
linear function, problem GEN$(\mathcal{F}^{\prime})$ can be solved in quasi-
polynomial time $k^{o(\log k)}$ time, where
$k=\max\\{n,r,|\mathcal{F}^{\prime}|\\}$, while the similar incremental
generation problem for the family of minimal infeasible solutions is NP-hard.
This result was extended to the case when each function $f_{i}$ can be written
as the sum $f_{i}(\mathbf{x})=\sum_{j=1}^{n}f_{ij}(x_{j})$ of single-variable
monotone functions $f_{ij}$, and more generally to the case when each $f_{i}$
is the sum of products of constant number of single-variable monotone
functions. A particularly interesting example of the latter case is when each
$f_{i}$ is a polynomial

$\displaystyle f_{i}(\mathbf{x})=\sum_{H\in\mathcal{H}_{i}}a_{H}\prod_{j\in
H}x_{j}^{d_{H,j}},$ (2)

where $\mathcal{H}_{i}\subseteq 2^{[n]}$ is a given mutliset family with
$d_{H,j}\in\mathbb{Z}_{+}$ and $a_{H}>0$ for all $H\in\mathcal{H}_{i}$.

It will be convenient to restrict the domain of each variable $x_{j}$ to a
subset $\mathcal{C}_{j}=\\{0,1\ldots,c_{j}\\}$ of $\mathbb{Z}_{+}$. Such a
bound $c_{j}$ of polynomial bit-length can be assumed in all the examples
considered in this paper. For instance, if each function $f_{i}$ is a
polynomial of the form (2), then any feasible solution for (1)
satisfies111assuming that $x_{j}\neq\infty$. $x_{j}\leq
c_{j}^{\prime}:=\min_{i}\frac{t_{i}}{\min_{H\in\mathcal{H}_{i}:~{}j\in
H}a_{H}}$. Thus, we may set $c_{j}:=\lfloor c_{j}^{\prime}\rfloor$, for all
$j\in[n]$. Keeping this in mind, we will assume in the rest of the paper that
the variable vector $\mathbf{x}$ is chosen from an integer box
$\mathcal{C}=\mathcal{C}_{1}\times\mathcal{C}_{2}\times\cdots\times\mathcal{C}_{n}=\\{\mathbf{x}\in\mathbb{R}^{n}|~{}\mathbf{0}\leq\mathbf{x}\leq\mathbf{c}\\}$,
where $\mathcal{C}_{j}=\\{0,1\ldots,c_{j}\\}$ for $j\in[n]$.

For an antichain (that is, a subset of pairwise incomparable elements)
$\mathcal{A}\subseteq\mathcal{C}$, denote by ${\mathcal{I}}(\mathcal{A})$ the
set of minimal non-dominated elements of $\mathcal{A}$, i.e., the set of those
elements $\mathbf{x}\in\mathcal{C}$ that are minimal with respect to the
property that $\mathbf{x}\not\leq\mathbf{a}$ for all
$\mathbf{a}\in\mathcal{A}$. It is easy to see that the mapping
${\mathcal{I}}:\text{Antichains}(\mathcal{C})\to\text{Antichains}(\mathcal{C})$
is one-to-one, and hence, the families $\mathcal{A}$ and
${\mathcal{I}}(\mathcal{A})$ can be thought of dual to each other. In
particular, if $\mathcal{F}$ is the family of maximal feasible solutions for
(1), then the dual ${\mathcal{I}}={\mathcal{I}}(\mathcal{F})$ represents the
family of minimal vectors of $\mathcal{C}$ which do not satisfy (1).

Let $f:\mathcal{C}\mapsto\mathbb{R}_{+}$, be a real-valued function over
$\mathcal{C}$. $f$ is said to be supermodular if

$\displaystyle f(\mathbf{x}\vee\mathbf{y})+f(\mathbf{x}\wedge\mathbf{y})\geq
f(\mathbf{x})+f(\mathbf{y})$ (3)

holds for all $\mathbf{x},\mathbf{y}\in\mathcal{C}$, where $\vee$ and $\wedge$
denote, respectively, the component-wise maximum and minimum operators over
$\mathcal{C}$: $(\mathbf{x}\vee\mathbf{y})_{j}=\max\\{x_{j},y_{j}\\}$ and
$(\mathbf{x}\wedge\mathbf{y})_{j}=\min\\{x_{j},y_{j}\\}$, for $j\in[n]$. It
was shown in [BEGK03] that if all the functions $f_{i}$ in (1) are integer-
valued supermodular functions, then GEN$(\mathcal{F}^{\prime})$ can be solved
in quasi-polynomial time $k^{o(\log k\cdot\log R)}$ time, where
$k=\max\\{n,r,|\mathcal{F}^{\prime}|\\}$ and
$R=\max_{i\in[r]}f_{i}(\mathbf{c})$. In particular, if all functions have
quasi-polynomially bounded integral range then all maximal feasible vectors
for the system can be enumerated in quasi-polynomial time. This, as well as
all the above-mentioned results, were established via a (quasi-)polynomial
time reduction to the following dualization problem on integer boxes:

DUAL$(\mathcal{C},\mathcal{A},\mathcal{B})$:

Given an integer box $\mathcal{C}$, an antichain of vectors
$\mathcal{A}\subseteq\mathcal{C}$ and a subset
$\mathcal{B}\subseteq{\mathcal{I}}(\mathcal{A})$ of its minimal non-dominated
vectors, either find a new minimal non-dominated vector
$\mathbf{x}\in{\mathcal{I}}(\mathcal{A})\setminus\mathcal{B}$, or provide an
evidence that no such vector exists, i.e.,
$\mathcal{B}={\mathcal{I}}(\mathcal{A})$.

It is known that problem DUAL$(\mathcal{C},\mathcal{A},\mathcal{B})$ can be
solved in $poly(n)$ $+$ $m^{o(\log m)}$ time, where
$m=|\mathcal{A}|+|\mathcal{B}|$ (see [BEG+02, FK96]). However, it is still
open whether DUAL$(\mathcal{C},\mathcal{A},\mathcal{B})$ has a polynomial-time
algorithm. To recall (at a high level) the reduction from problem
GEN$(\mathcal{F}^{\prime})$ to problem
DUAL$(\mathcal{C},\mathcal{A},\mathcal{B})$, let us follow [BGKM01] in calling
the family $\mathcal{F}$ uniformly dual-bounded, if for every subfamily
$\mathcal{F}^{\prime}\subseteq\mathcal{F}$ we have

$|{\mathcal{I}}(\mathcal{F}^{\prime})\cap{\mathcal{I}}(\mathcal{F})|\leq
q(\mathcal{L},|\mathcal{F}^{\prime}|)$ (4)

for some (quasi-)polynomial $q(\cdot)$, where $\mathcal{L}$ is the total
length of the binary encoding of the parameters defining the system (1). It
was shown in [BEG+02] (extending the similar result in [BI95, GK99], for
binary case) that the incremental joint generation problem of enumerating (in
a non-controlled order) the union family
$\mathcal{F}\cup{\mathcal{I}}(\mathcal{F})$ can be reduced in polynomial time
to the dualization problem DUAL$(\mathcal{C},\cdot,\cdot)$ over an integer box
$\mathcal{C}$. It follows then that for uniformly dual-bounded families
$\mathcal{F}$, problem GEN$(\mathcal{F}^{\prime})$ can be reduced in
(quasi-)polynomial time to the dualization problem by performing joint
generation and discarding the elements of the unwanted family
${\mathcal{I}}(\mathcal{F}^{\prime})\cap{\mathcal{I}}(\mathcal{F})$. Since the
number of discarded elements is bounded by a (quasi-)polynomial
$q(\mathcal{L},|\mathcal{F}^{\prime}|)$ in the input-output size, the overall
running time for enumerating $\mathcal{F}$ is dominated by a
(quasi-)polynomial in $q(\mathcal{L},|\mathcal{F}^{\prime}|)$ and the time
$T_{\text{\em DUAL}}$ needed to solve the dualization problem, resulting in an
overall quasi-polynomial time, if the family $\mathcal{F}$ is uniformly dual-
bounded.

We now state some of the known bounds of the form (4) for families
$\mathcal{F}$ of maximal feasible vectors for (1):

  * (B1)

When the all the functions $f_{i}$ are integer-valued supermodular of range
$\\{0,1,\ldots,R\\}$, we have $q(\mathcal{L},|\mathcal{F}^{\prime}|)\leq
r|\mathcal{F}^{\prime}|^{o(\log(R-t))}$, where
$t:=\min\\{t_{1},\ldots,t_{r}\\}$ [BEGK03].

  * (B2)

If each $f_{i}$ is linear, that is,
$f_{i}(x)=(\mathbf{a}^{i})^{\top}\mathbf{x}$, for some non-negative vector
$\mathbf{a}^{i}$, then $q(\mathcal{L},|\mathcal{F}^{\prime}|)\leq
rn|\mathcal{F}^{\prime}|$ [BEG+02]. In fact, this is also true for the case
when each $f_{i}(\mathbf{x})=\sum_{j=1}^{n}f_{ij}(x_{j})$ is the sum of
single-variable monotone functions [KBE+07].

  * (B3)

More generally, if each $f_{i}$ is the sum of at most $s$ terms each of which
is the product of at most $p$ single-variable monotone functions, then
$q(\mathcal{L},|\mathcal{F}^{\prime}|)\leq rsp(2|\mathcal{F}^{\prime}|+1)^{p}$
[KBE+07]. This is true, in particular, for a system of polynomial inequalities
of the form (2), when the dimension of each hypergraph (that is, the maximum
size of a hyperedge) is bounded by a constant.

### Main results.

We extend the above results (B1)-(B3) as follows:

  * (B4)

We consider real-valued supermodular functions with range $[0,R]$ and obtain a
bound $q(\mathcal{L},|\mathcal{F}^{\prime}|)\leq
r|\mathcal{F}^{\prime}|^{o(\log\frac{R-t}{\tau})}$ that depends on the minimum
traction (i.e., minimum possible positive change) $\tau$ of the functions
$f_{i}$. In particular, when $\frac{R-t}{\tau}=\operatorname{quasi-
poly}(\mathcal{L},|\mathcal{F}^{\prime}|)$, we obtain a quasi-polynomial time
enumeration algorithm.

  * (B5)

As a direct application of the result in (B4), we consider the case when each
function $f_{i}$ is a product of real-valued affine functions with rational
coefficients and the objective is to enumerate the the family of all minimal
feasible solutions of the system $f_{i}(\mathbf{x})\geq t_{i}$ for
$i=1,\ldots,r$. We derive a bound of
$q(\mathcal{L},|\mathcal{F}^{\prime}|)\leq|\mathcal{F}^{\prime}|^{o(\log\mathcal{L})}$
on the size of the dual family, implying that the problem of enumerating all
minimal feasible solutions of such systems can be solved in quasi-polynomial
time.

  * (B6)

We show that, if each $f_{i}$ is an integer-valued polynomial function (as in
(2)) of range $\\{0,1,\ldots,R\\}$ having at most $s$ terms in which each
variable has degree at most $d$, then
$q(\mathcal{L},|\mathcal{F}^{\prime}|)\leq
r|\mathcal{F}^{\prime}|(R-\min_{i}t_{i},$
$s+2^{d+2}n\max_{i}t_{i})|\mathcal{F}^{\prime}|)$. In particular, if
$d=\operatorname{polylog}(\mathcal{L})$ and, for all $i$, either $t_{i}\geq
R_{i}-\operatorname{quasi-poly}(\mathcal{L})$ or
$t_{i}\leq\operatorname{quasi-poly}(\mathcal{L})$, then all maximal feasible
vectors for (1) can be enumerated in quasi-polynomial time. In contrast to the
result in (B3), this does not require the hypergraphs defining the polynomials
in (2) to have fixed dimension.

  * (B7)

We consider the case when (1) is a system of second-order cone inequalities,
that is, when each $f_{i}$ is a real-valued function of the form
$f_{i}(\mathbf{x}):=\|A^{i}\mathbf{x}\|+(\mathbf{b}^{i})^{\top}\mathbf{x}$,
where $A^{i}\in\mathbb{R}_{+}^{d\times n}$ and
$\mathbf{b}^{i}\in\mathbb{R}_{+}^{n}$ are given matrices and vectors, and
$\|\cdot\|$ denotes the $\ell_{2}$-norm. We show in this case that
$q(\mathcal{L},|\mathcal{F}^{\prime}|)\leq
O(n)^{2d+1}r|\mathcal{F}^{\prime}|$. In particular if
$d=\operatorname{polylog}(\mathcal{L})$ then problem
GEN$(\mathcal{F}^{\prime})$ can be solved in quasi-polynomial time.

  * (B8)

Finally, we consider the case when each $f_{i}$ is a real-valued function of
the form $f_{i}=\lambda_{\max}(\sum_{j=1}^{n}A^{i,j}x_{j})$ where
$A^{i,j}\in\mathbb{R}_{+}^{d\times d}$ is a positive semidefinite matrix, and
$\lambda_{\max}(X)$ denotes the maximum eigenvalue of the matrix $X$. This
gives rise to a semidefinite inequality system. We show in this case that
$q(\mathcal{L},|\mathcal{F}^{\prime}|)\leq
O(n)^{2d+1}r|\mathcal{F}^{\prime}|$, and consequently, if
$d=\operatorname{polylog}(\mathcal{L})$ then problem
GEN$(\mathcal{F}^{\prime})$ can be solved in quasi-polynomial time.

We give some motivating applications of these results in the next section.
Proofs of the bounds claimed in (B4), (B5), (B6), (B7) and (B8) are given in
Sections 3, 4, 5, 6 and 7, respectively. To simply our presentation, it will
be enough to establish the bound for a single inequality:

$\displaystyle\displaystyle
f(\mathbf{x})\leq~{}t,~{}\quad\mathbf{x}\in\mathcal{C},$ (5)

where we assume w.l.o.g. that $0\leq t\leq f(\mathbf{c})$. Indeed, given a
system (1), let us denote by $\mathcal{F}_{i}$ is the set of maximal feasible
solutions of the inequality $f_{i}(\mathbf{x})\leq t_{i}$. Suppose that we
manage to show that
$|{\mathcal{I}}(\mathcal{F}^{\prime})\cap{\mathcal{I}}(\mathcal{F}_{i})|\leq
q_{i}(\mathcal{L},|\mathcal{F}^{\prime}|)$ for any
$\mathcal{F}^{\prime}\subseteq\mathcal{F}_{i}$. Then, for any subset
$\mathcal{F}^{\prime}\subseteq\mathcal{F}$ of maximal feasible solutions of
the system, a union bound can be applied to obtain

$\displaystyle|{\mathcal{I}}(\mathcal{F}^{\prime})\cap{\mathcal{I}}(\mathcal{F})|=\left|\bigcup_{i=1}^{r}\left({\mathcal{I}}(\mathcal{F}^{\prime})\cap{\mathcal{I}}(\mathcal{F}_{i})\right)\right|\leq\sum_{i=1}^{r}|{\mathcal{I}}(\mathcal{F}^{\prime})\cap{\mathcal{I}}(\mathcal{F}_{i})|\leq\sum_{i=1}^{r}q_{i}(\mathcal{L},|\mathcal{F}^{\prime}|).$

Thus, in deriving the stated bounds, we will focus on a single inequality in
the system (1).

##  2 Some Applications

### Fair allocation of goods.

Consider a set of $m$ agents and $n$ types of indivisible goods (or items). We
assume there is unlimited supply of each item. Each agent $i$ demands at least
$t_{i}$ items to be allocated to it and its utility for receiving an
allocation $\mathbf{x}^{i}:=(x_{ij}~{}|~{}j\in[n])$ is given by the linear
function $u_{i}(\mathbf{x}):=\sum_{j}a_{ij}x_{ij}$, where
$x_{ij}\in\mathbb{Z}_{+}$ is the number of goods of type $j$ allocated to
agent $i$. Given a threshold parameter $t$, we are interested in finding all
minimal allocations satisfying the demand constraints and achieving a Nash
social welfare of value at least $t$:

$\displaystyle\displaystyle\left(\prod_{i=1}^{m}u_{i}(\mathbf{x})\right)^{1/m}\geq
t,$ (6) $\displaystyle\sum_{j}x_{ij}\geq t_{i},\quad\text{ for }i\in[m],$ (7)
$\displaystyle\mathbf{x}\in\mathbb{Z}_{+}^{mn}.$

This gives rise to a monotone system of inequalities, each of which is
involving either a linear function or a product of linear functions. It
follows from the result in (B5) that the family of minimal feasible solutions
for this system is uniformly dual-bounded and hence can be enumerated in
incremental quasi-polynomial time.

### Chance-constrained muti-dimensional knapsack inequalities.

Consider a system (1) where each
$f_{i}(\mathbf{x}):=(\mathbf{w}^{i})^{\top}\mathbf{x}$ is a linear function
defined by a non-negative weight vector $\mathbf{w}^{i}\in\mathbb{R}^{n}$. The
elements of $[n]$ can be interpreted as items to be packed into $r$ knapsacks
of capacities $t_{1},\ldots,t_{r}$, where $w^{i}_{j}$ represents the size
requirement of item $j$ in knapsack $i$. In the stochastic version, each
vector $\mathbf{w}^{i}$ is drawn from a multivariate normal distribution with
mean $\mathbf{a}^{i}\in\mathbb{R}_{+}^{n}$ and covariance matrix
$\Sigma^{i}\in\SS^{n\times n}_{+}$, i.e., $\mathbf{w}^{i}\sim
N(\mathbf{a}^{i},\Sigma^{i})$. The requirement is to pack the items into the
the knapsacks, such that the $i$th capacity constraint is satisfied with
probability at least $\alpha_{i}\in[0,1]$:

$\displaystyle\displaystyle\Pr[(\mathbf{w}^{i})^{\top}\mathbf{x}\leq~{}t_{i}]\geq\alpha_{i},\quad\text{
for }i\in[r],$ (8) $\displaystyle\mathbf{x}\in\\{0,1\\}^{n}.$

As $(\mathbf{w}^{i})^{\top}\mathbf{x}\sim
N((\mathbf{a}^{i})^{\top}\mathbf{x},\mathbf{x}^{\top}\Sigma^{i}\mathbf{x})$,
we can reformulate the constraints (8) as:

$\displaystyle\displaystyle(\mathbf{a}^{i})^{\top}\mathbf{x}+\Phi^{-1}(\alpha_{i})\sqrt{\mathbf{x}^{\top}\Sigma^{i}\mathbf{x}}\leq
t_{i},\quad\text{ for }i\in[r]:=\\{1,\ldots,r\\},$ (9)
$\displaystyle\mathbf{x}\in\\{0,1\\}^{n},$

where $\Phi(\cdot)$ represents the cumulative distribution function of the
standard normal distribution. While the complexity of enumerating the family
of maximal feasible solutions for (9), in general, remains open at this point,
we can efficiently solve the problem in two special cases described below. In
both cases, we assume that $\alpha_{i}\geq 0.5$ and hence
$\Phi^{-1}(\alpha_{i})\geq 0$.

  * •

Fixed-rank case: this is the case when the covariance matrices $\Sigma^{i}$
have completely positive (cp) rank $d_{i}$, i.e., we can find matrices
$A^{i}\in\mathbb{R}_{+}^{d_{i}\times n}$ such that
$\Sigma^{i}=(A^{i})^{\top}A^{i}$ (this is, for example, the case when
$\mathbf{w}^{i}=(A^{i})^{\top}z+\mathbf{a}^{i}$, where
$z_{1},\ldots,z_{d_{i}}\sim N(0,1)$ are i.i.d.’s.). In such a case, we can
rewrite (9) as a second order cone program:

$\displaystyle\displaystyle(\mathbf{a}^{i})^{\top}\mathbf{x}+\Phi^{-1}(\alpha_{i})\|A^{i}\mathbf{x}\|\leq
t_{i},\quad\text{ for }i\in[r]:=\\{1,\ldots,r\\},$ (10)
$\displaystyle\mathbf{x}\in\\{0,1\\}^{n}.$

It follows then from the result in (B7) that, when $\max_{i}d_{i}=O(1)$, then
the maximal feasible solutions of (8) can be enumerated in quasi-polynomial
time.

  * •

Ordered independent case: this is the case when item sizes are independent:
$A^{i}=D^{i}:=\operatorname{Diag}(d^{i}_{1},\ldots,d^{i}_{n})$ is a full-rank
diagonal matrix, and in addition, we are given permutations
$\sigma_{1},\ldots,\sigma_{r}:[n]\to[n]$ s.t. for each $i\in[r]$:

$\displaystyle a^{i}_{\sigma_{i}(1)}\geq\cdots\geq
a^{i}_{\sigma_{i}(n)}\quad\text{ and }\quad
d^{i}_{\sigma_{i}(1)}\geq\cdots\geq d^{i}_{\sigma_{i}(n)},$ (11)

that is, in each knapsack, the means and standard deviations of the item sizes
can be ordered in the same way (this is true, for example, when $w_{j}^{i}\sim
N(a^{i}_{j},1)$ are independent). In this case, we can verify that the
function
$f_{i}(\mathbf{x}):=(\mathbf{a}^{i})^{\top}\mathbf{x}+\Phi^{-1}(\alpha_{i})\|A^{i}\mathbf{x}\|=(\mathbf{a}^{i})^{\top}\mathbf{x}+\Phi^{-1}(\alpha_{i})\sqrt{\sum_{j}(d_{j}^{i})^{2}x_{j}}$
is 2-monotonic with permutation $\sigma_{i}$; see the definition in Section 6.
Indeed, for any $\mathbf{x}\in\mathcal{C}$ and $k,j\in[n]$ with $k<j$,
$\mathbf{x}_{\sigma_{i}(k)}=0$ and $\mathbf{x}_{\sigma_{i}(j)}=1$, it holds by
(11) that

$\displaystyle
f_{i}(\mathbf{x}+\mathbf{1}^{\sigma(k)}-\mathbf{1}^{\sigma(j)})-f(\mathbf{x})=$
$\displaystyle\qquad
a^{i}_{\sigma_{i}(k)}-a^{i}_{\sigma_{i}(j)}+\frac{\Phi^{-1}(\alpha_{i})\left[(d^{i}_{\sigma_{i}(k)})^{2}-(d^{i}_{\sigma_{i}(j)})^{2}\right]}{\sqrt{\sum_{j^{\prime}\neq
j,k}(d^{i}_{j^{\prime}})^{2}x_{j^{\prime}}+(d^{i}_{\sigma_{i}(k)})^{2}}+\sqrt{\sum_{j^{\prime}\neq
j,k}(d^{i}_{j^{\prime}})^{2}x_{j^{\prime}}+(d^{i}_{\sigma_{i}(j)})^{2}}}\geq
0.$

Thus, we can use Lemma 7 below to derive the the bound
$|{\mathcal{I}}(\mathcal{F}^{\prime})\cap{\mathcal{I}}(\mathcal{F})|\leq
rn|\mathcal{F}^{\prime}|$ for any subset
$\mathcal{F}^{\prime}\subseteq\mathcal{F}$ of the maximal feasible solutions
for (9), and hence conclude that the latter family can be enumerated in quasi-
polynomial time in this case. Note that the same argument does not work if the
ordering property (11) does not hold.

### Chance-constrained covering binary programs.

In a similar setting as in the previous example, we are given $n$-dimensional
normally distributed random vectors $\mathbf{w}^{i}\sim
N(\mathbf{a}^{i},\Sigma^{i})$, for $i\in[r]$, and demands
$t_{1},\ldots,t_{r}\in\mathbb{R}_{+}$. Here, $w^{i}_{j}$ can be interpreted as
the coverage value for the $j$th item with respect to the $i$th demand. The
requirement is to select a subset of the items, such that the $i$th demand
constraint is satisfied with probability at least $\alpha_{i}\in[0,1]$:

$\displaystyle\displaystyle\Pr[(\mathbf{w}^{i})^{\top}\mathbf{x}\geq~{}t_{i}]\geq\alpha_{i},\quad\text{
for }i\in[r],$ (12) $\displaystyle\mathbf{x}\in\\{0,1\\}^{n}.$

As before, we can reformulate the constraints (8) as a second-order cone
program:

$\displaystyle\displaystyle(\mathbf{a}^{i})^{\top}\mathbf{x}+\Phi^{-1}(1-\alpha_{i})\sqrt{\mathbf{x}^{\top}\Sigma^{i}\mathbf{x}}\geq
t_{i},\quad\text{ for }i\in[r]:=\\{1,\ldots,r\\},$ (13)
$\displaystyle\mathbf{x}\in\\{0,1\\}^{n}.$

In the special case when the random variables are independent, that is, when
$\Sigma^{i}:=(D^{i})^{2}:=\operatorname{Diag}((d^{i}_{1})^{2},\ldots,$
$(d^{i}_{n})^{2})$ is a full-rank diagonal matrix, we can enumerate the family
$\mathcal{G}$ of minimal feasible solutions for the system (12) by using the
result in (B4). Indeed, let

$f_{i}(\mathbf{x}):=R_{i}-(\mathbf{a}^{i})^{\top}(\mathbf{1}-\mathbf{x})-\Phi^{-1}(1-\alpha_{i})\|D^{i}(\mathbf{1}-\mathbf{x})\|,$

where
$R_{i}:=(\mathbf{a}^{i})^{\top}\mathbf{1}+\Phi^{-1}(1-\alpha_{i})\sqrt{\mathbf{1}^{\top}\Sigma^{i}\mathbf{1}}$,
and $\mathbf{1}$ is $n$-dimensional the vector of all ones. Assume that
$\alpha_{i}<0.5$ and hence $\Phi^{-1}(1-\alpha_{i})>0$. Then, for any
$\mathbf{x}\in\\{0,1\\}^{n}$ s.t. $x_{j}=0$,

$\displaystyle
f_{i}(\mathbf{x}+\mathbf{1}^{j})-f_{i}(\mathbf{x})=a^{i}_{j}+\frac{\Phi^{-1}(1-\alpha_{i})(d^{i}_{j})^{2}}{\sqrt{\sum_{j^{\prime}\neq
j}(d^{i}_{j^{\prime}})^{2}(1-x_{j^{\prime}})+(d^{i}_{j})^{2}}+\sqrt{\sum_{j^{\prime}\neq
j}(d^{i}_{j^{\prime}})^{2}(1-x_{j^{\prime}})}},$ (14)

which is monotone increasing $\mathbf{x}$. Supermodularity follows. Next we
bound the traction $\tau_{i}$ and maximum range $R_{i}$ of each $f_{i}$. From
(14), we get
$\tau_{i}\geq\min\left\\{a_{\min},\Phi^{-1}(1-\alpha_{i})\frac{d_{\min}^{2}}{2\sqrt{n}d_{\max}}\right\\}$,
where $a_{\min}=\min_{i,j}\\{a^{i}_{j}~{}|~{}a^{i}_{j}>0\\}$,
$d_{\min}=\min_{i,j}\\{d^{i}_{j}~{}|~{}d^{i}_{j}>0\\}$ and
$d_{\max}=\max_{i,j}d^{i}_{j}$. Similarly, we have $R_{i}\leq
na_{\max}+\Phi^{-1}(1-\alpha_{i})\sqrt{n}d_{\max}$. It follows from the result
in (B4) that if $\frac{a_{\max}}{a_{\min}}$, $\frac{d_{\max}}{d_{\min}}$ and
$\Phi^{-1}(1-\alpha_{i})$ are bounded by polynomials in $n$, then all minimal
feasible solutions of the system (12) can be enumerated in quasi-polynomial
time.

### Quantum hypergraph covers.

A quantum hypergraph [AW02, WX08] is a pair $\mathcal{H}=(V,E)$ where
$V\subseteq\mathbb{C}^{d}$ is a $d$-dimensional Hilbert space and
$E:=\\{A_{1},\ldots,A_{n}\\}$ is a finite set of Hermitian matrices, such that
$0\preceq A_{j}\preceq\mathbf{I}_{d}$, where $\mathbf{I}_{d}$ is the
$d$-dimensional identity matrix in $\mathbb{C}^{d}$ and ”$\succeq$“ is the
Löwner (partial) order on matrices: $A\succeq B$ if and only if $A-B$ is
positive semidefinite. A cover of $\mathcal{H}$ is a subset
$E^{\prime}\subseteq E$ of edges such that $\sum_{j\in
E^{\prime}}A_{j}\succeq\mathbf{I}_{d}$. This notion arises in the area of
quantum information theory [AW02]. Note that a minimal quantum hypergraph
cover is a minimal feasible solution for the inequality:

$\displaystyle\displaystyle\sum_{j=1}^{n}A_{j}x_{j}\succeq~{}\mathbf{I}_{d},$
(15) $\displaystyle\mathbf{x}\in\\{0,1\\}^{n}.$

Assuming feasibility of (15), we must have
$T:=\sum_{j=1}^{n}A_{j}x_{j}-\mathbf{I}_{d}\succeq 0$. It follows then that
the minimal quantum hypergraph covers are in one-to-one correspondence with
the maximal feasible binary solutions for the inequality
$\sum_{j=1}^{n}A_{j}x_{j}\preceq T$, which is of the form considered in (B8).
It is not difficult to see that the result in (B8) can be extended to the case
when the matrices $A^{i,j}$ are Hermitian positive semidefinite, while only
increasing the dual bound by a factor of at most $2$ in the exponent (that is,
we get $q(\mathcal{L},|\mathcal{F}^{\prime}|)\leq
O(n)^{4d+1}r|\mathcal{F}^{\prime}|$). We conclude that, if the dimension $d$
is fixed, then all minimal covers for a quantum hypergraph can be enumerated
in quasi-polynomial time.

##  3 Supermodular Inequalities

Given a function $f:\mathcal{C}\to\mathbb{R}_{+}$, one can check if $f$ is
supermodular using the following statement, generalizing the well-known
characterization of supermodular functions over the Boolean cube [Lov83].

######  Proposition 1.

A function $f:\mathcal{C}\to\mathbb{R}$ is supermodular if and only if, for
any $j\in[n]$, for any $z\in\mathcal{C}_{j}\setminus\\{c_{j}\\}$, and for any
$\mathbf{x}\in\mathcal{C}_{1}\times\ldots\times\mathcal{C}_{j-1}\times\\{z\\}\times\mathcal{C}_{j+1}\times\ldots\times\mathcal{C}_{k}$,
the difference

$\displaystyle\partial_{f}(\mathbf{x},j,z):=f(\mathbf{x}+\mathbf{1}^{j})-f(\mathbf{x}),$

is monotone in $\mathbf{x}$.

We include the proof in the appendix for completeness. Define the ”traction”
of $f$, denoted by $\tau(f)$, to be the minimum possible positive increase in
$f$ corresponding to a minimal change in the variables:

$\displaystyle\tau(f):=\min_{\stackrel{{\scriptstyle
j\in[n],~{}\mathbf{x}\in\mathcal{C},~{}x_{j}<c_{j}}}{{f(\mathbf{x}+\mathbf{1}^{j})>f(\mathbf{x})}}}f(\mathbf{x}+\mathbf{1}^{j})-f(\mathbf{x}).$
(16)

Consider a monotone inequality (5), where the function $f$ is supermodular,
and let $\mathcal{F}$ denote the family of all its maximal vectors. We can
extend the result in [BEGK03] as follows.

######  Theorem 1.

Consider the inequality (5) and suppose that
$f:\mathcal{C}\mapsto\mathbb{R}_{+}$ is a monotone supermodular function with
traction $\tau$ and maximum range $R:=f(\mathbf{c})$. Then for any subset
$\mathcal{F}^{\prime}\subseteq\mathcal{F}$ of size $|\mathcal{F}^{\prime}|\geq
2$, it holds that

$\displaystyle|{\mathcal{I}}(\mathcal{F}^{\prime})\cap{\mathcal{I}}(\mathcal{F})|\leq|\mathcal{F}^{\prime}|^{o(\log\frac{R-t}{\tau})}.$
(17)

###### Proof.

Given $\mathcal{F}^{\prime}\subseteq\mathcal{F}$ and
$\mathcal{X}:={\mathcal{I}}(\mathcal{F}^{\prime})\cap{\mathcal{I}}(\mathcal{F})$,
we follow the proof in [BEGK03] by constructing a binary tree $\mathbf{T}$, in
which each leaf $l\in L(\mathbf{T})$ is mapped to an element
$\mathbf{x}^{l}\in\mathcal{X}$, and each internal node $v$ is associated with
the element $\mathbf{x}^{v}=\bigvee_{l\in L(\mathbf{T}(v))}\mathbf{x}^{l}$;
here, $\mathbf{T}(v)$ denotes the binary sub-tree of $\mathbf{T}$ rooted at
node $v$, and $L(\mathbf{T}^{\prime})$ denotes the set of leaves of the
subtree $\mathbf{T}^{\prime}$. Such a mapping
$\phi:L(\mathbf{T})\to\mathcal{X}$ is said to be proper if it assigns
different elements to different leaves, and if
$f(\mathbf{x}^{u}\wedge\mathbf{x}^{v})\leq t$ whenever $u$ and $v$ are
incomparable nodes of $\mathbf{T}$ (that is, when the sub-trees
$\mathbf{T}(u)$ and $\mathbf{T}(v)$ are disjoint). As shown in [BEGK03], a
sufficiently large binary tree admitting a proper mapping can always be
constructed:

######  Lemma 2 (Lemma 11 in [BEGK03]).

Let $\mathcal{A}\subseteq\mathcal{C}$ be an antichain of size
$|\mathcal{A}|\geq 2$ in integral box $\mathcal{C}$ and let
$\mathcal{B}\subseteq{\mathcal{I}}(\mathcal{A})$. Then there exists a binary
tree $\mathbf{T}$ and a proper mapping $\phi:L(\mathbf{T})\to\mathcal{B}$ such
that $|L(\mathbf{T})|\geq|\mathcal{B}|^{1/o(\log|\mathcal{A}|)}.$

To prove the theorem, we consider a partition of
$\mathcal{X}=\mathcal{X}^{\prime}\cup\mathcal{X}^{\prime\prime}$, where
$\mathcal{X}^{\prime}:=\\{\mathbf{x}\in\mathcal{X}:~{}f(\mathbf{x})\geq
t+\frac{\tau}{2}\\}\subseteq{\mathcal{I}}(\mathcal{F}^{\prime})$ and
$\mathcal{X}^{\prime\prime}:=\mathcal{X}\setminus\mathcal{X}^{\prime}\subseteq{\mathcal{I}}(\mathcal{F}^{\prime})$,
and proper mappings
$\phi^{\prime}:L(\mathbf{T}^{\prime})\to\mathcal{X}^{\prime}$ and
$\phi^{\prime\prime}:L(\mathbf{T}^{\prime\prime})\to\mathcal{X}^{\prime\prime}$
as guaranteed by Lemma 2. Consequently, the theorem follows from the following
extension of Lemma 1 in [BEGK03].

######  Lemma 3.

Given binary trees $\mathbf{T}^{\prime}$ and $\mathbf{T}^{\prime\prime}$ and
proper mappings $\phi^{\prime}$ and $\phi^{\prime\prime}$ as above, we have

$|L(\mathbf{T}^{\prime})|\leq\frac{2(R-t)}{\tau}\text{ and
}|L(\mathbf{T}^{\prime\prime})|\leq\frac{2(R-t)}{\tau}+1.$ (18)

###### Proof.

Consider first the tree $\mathbf{T}^{\prime}$ and the mapping $\phi^{\prime}$.
We show by induction that

$f(\mathbf{x}^{w})\geq t+\frac{\tau}{2}|L(\mathbf{T}^{\prime}(w))|.$ (19)

holds for every node $w$ of the binary tree $\mathbf{T}^{\prime}$. Since
$f(\mathbf{x}^{w})\leq R$, it follows that

$|L(\mathbf{T}^{\prime}(w))|\leq\frac{2(R-t)}{\tau}$

which, if applied to the root of $\mathbf{T}^{\prime}$, proves the first part
of the lemma. To see (19), let us apply (backward) induction on the level of
the node $w$ in $\mathbf{T}^{\prime}$. Clearly, if $w=l$ is a leaf of
$\mathbf{T}^{\prime}$, then $|L(\mathbf{T}^{\prime}(l))|=1$, and (19) follows
by the assumption that $\mathbf{x}^{l}\in\mathcal{X}^{\prime}$. Let us assume
now that $w$ is a node of $\mathbf{T}^{\prime}$ with $u$ and $v$ as its
immediate successors. Then
$|L(\mathbf{T}^{\prime}(w))|=|L(\mathbf{T}^{\prime}(u))|+|L(\mathbf{T}^{\prime}(v))|$,
and $\mathbf{x}^{w}=\mathbf{x}^{u}\vee\mathbf{x}^{v}$. By our inductive
hypothesis, and since $f$ is supermodular and
$f(\mathbf{x}^{u}\wedge\mathbf{x}^{v})\leq t$, we have the inequalities

$\begin{array}[]{rl}f(\mathbf{x}^{u}\vee\mathbf{x}^{v})&\geq
f(\mathbf{x}^{u})+f(\mathbf{x}^{v})-f(\mathbf{x}^{u}\wedge\mathbf{x}^{v})\\\
&\geq
t+\frac{\tau}{2}|L(\mathbf{T}(u))|+t+\frac{\tau}{2}|L(\mathbf{T}(v))|-t\\\
&=t+\frac{\tau}{2}|L(\mathbf{T}(w))|.\end{array}$

Consider next the tree $\mathbf{T}^{\prime\prime}$ and the mapping
$\phi^{\prime\prime}$. We prove by induction that

$f(\mathbf{x}^{w})\geq
t-\frac{\tau}{2}+\frac{\tau}{2}|L(\mathbf{T}^{\prime\prime}(w))|.$ (20)

holds for every node $w$ of the binary tree $\mathbf{T}^{\prime}$. If $w=l$ is
a leaf node, then (20) holds as $|L(\mathbf{T}^{\prime\prime}(l))|=1$, and
$f(\mathbf{x}^{l})>t$. If $w$ is a node of $\mathbf{T}^{\prime\prime}$ with as
immediate successors $u$ and $v$, then (as $f(\mathbf{x}^{u})>t$ and
$f(\mathbf{x}^{v})>t$ while $f(\mathbf{x}^{u}\wedge\mathbf{x}^{v})\leq t$),
there must exist a $j\in[n]$ such that
$\mathbf{x}^{u}\wedge\mathbf{x}^{v}\leq\mathbf{x}^{v}-\mathbf{1}^{j}$. The
definition of $\tau$ and the fact that
$\mathbf{x}^{v}\in\mathcal{X}^{\prime\prime}$ imply that
$f(\mathbf{x}^{v}-\mathbf{1}^{j})\leq
f(\mathbf{x}^{v})-\tau<t+\frac{\tau}{2}-\tau=t-\frac{\tau}{2}$. It follows
from this and the inductive hypothesis that

$\begin{array}[]{rl}f(\mathbf{x}^{u}\vee\mathbf{x}^{v})&\geq
f(\mathbf{x}^{u})+f(\mathbf{x}^{v})-f(\mathbf{x}^{u}\wedge\mathbf{x}^{v})\\\
&\geq f(\mathbf{x}^{u})+f(\mathbf{x}^{v})-f(\mathbf{x}^{v}-\mathbf{1}^{j})\\\
&\geq
t-\frac{\tau}{2}+\frac{\tau}{2}|L(\mathbf{T}(u))|+t-\frac{\tau}{2}+\frac{\tau}{2}|L(\mathbf{T}(v))|-(t+\frac{\tau}{2})\\\
&=t-\frac{\tau}{2}+\frac{\tau}{2}|L(\mathbf{T}(w))|.\end{array}$

Applying (20) to the root of $\mathbf{T}^{\prime\prime}$ establishes the
second part of the lemma. ∎

It follows from the above two lemmas that

$\displaystyle|{\mathcal{I}}(\mathcal{F}^{\prime})\cap{\mathcal{I}}(\mathcal{F})|$
$\displaystyle=|\mathcal{X}^{\prime}|+|\mathcal{X}^{\prime\prime}|\leq|L(\mathbf{T}^{\prime})|^{o(\log|\mathcal{F}^{\prime}|)}+|L(\mathbf{T}^{\prime\prime})|^{o(\log|\mathcal{F}^{\prime}|)}$
$\displaystyle\leq
2\left(\frac{2(R-t)}{\tau}+1\right)^{o(\log|\mathcal{F}^{\prime}|)}.$

∎

##  4 Products of Affine Functions

Let $p_{1},\ldots,p_{m}:\mathcal{C}\to\mathbb{Q}_{+}$ be affine functions
given in the form:
$p_{k}(\mathbf{x})=(\mathbf{a}^{k})^{\top}\mathbf{x}+a_{0}^{k}$, where
$\mathbf{a}^{k}\in\mathbb{Q}_{+}^{n}$ are given vectors and
$a_{k}^{0}\in\mathbb{Q}_{+}$ are given numbers. Given $t\in\mathbb{Q}_{+}$, we
are interested in enumerating the family $\mathcal{G}$ of all minimal feasible
vectors for the inequality $g(x)\geq t$ over $\mathbf{x}\in\mathbb{Z}_{+}$,
where $g(x):=\prod_{k=1}^{m}p_{k}(\mathbf{x})$. We may assume without loss of
generality that $\mathbf{a}^{k}_{j},t\in\mathbb{Z}_{+}$ for all $k,j$.
Although $g(\mathbf{x})$ defines a polynomial, we cannot (directly) apply the
result in (B6) since the number of terms $s$ (and possibly also the maximum
degree $d$) is exponential in $m$. Instead, we consider the function

$f(\mathbf{x}):=R-\sum_{k=1}^{m}\log\overline{p}_{k}(\mathbf{c}-\mathbf{x}),$

where $R:=\sum_{k=1}^{m}\log\overline{p}_{k}(\mathbf{c})$,
$\overline{p}_{k}(\mathbf{x}):=p_{k}(\mathbf{x})+\epsilon$, and

$\displaystyle\epsilon:=\frac{1}{2m(1+\max_{k}p_{k}(\mathbf{c}))^{m-1}}$ (21)

is a sufficiently small perturbation parameter that is needed to insure that
the range of the function $f$ remains bounded (which might fail to hold
without perturbation when $\mathbf{x}=\mathbf{c}$). It is not difficult to see
that the family $\mathcal{F}$ of maximal feasible solutions for the inequality
$f(\mathbf{x})\leq t^{\prime}:=R-\log t$ is in one-to-one correspondence with
$\mathcal{G}$. Indeed, given $\mathbf{x}$ such $g(\mathbf{c}-\mathbf{x})\geq
t$, it is immediate that
$R-\sum_{k=1}^{m}\log\overline{p}_{k}(\mathbf{c}-\mathbf{x})\leq t^{\prime}$,
as $\overline{p}_{k}(\mathbf{c}-\mathbf{x})\geq p_{k}(\mathbf{c}-\mathbf{x})$.
Conversely, given $\mathbf{x}$ such that $f(\mathbf{x})\leq t^{\prime}$, it
holds that $\prod_{k=1}^{m}\overline{p}_{k}(\mathbf{c}-\mathbf{x})\geq t$. As

$\displaystyle\prod_{k=1}^{m}\overline{p}_{k}(\mathbf{c}-\mathbf{x})$
$\displaystyle=\prod_{k=1}^{m}p_{k}(\mathbf{c}-\mathbf{x})+\epsilon\cdot\sum_{S\subseteq[m]~{}:~{}|S|<m}\epsilon^{m-1-|S|}\prod_{k\in
S}p_{k}(\mathbf{c}-\mathbf{x})$
$\displaystyle\leq\prod_{k=1}^{m}p_{k}(\mathbf{c}-\mathbf{x})+\epsilon\cdot
m(\epsilon+\max_{k}p_{k}(\mathbf{c}))^{m-1},$

we get by our choice (21) of $\epsilon$ that
$\prod_{k=1}^{m}p_{k}(\mathbf{c}-\mathbf{x})\geq t-\frac{1}{2}$, which in turn
implies that $g(\mathbf{c}-\mathbf{x})\geq t$ by the integrality assumption.

To enumerate the elements of $\mathcal{F}$ in quasi-polynomial time, it would
be enough by (B4) to show that the function $f$ is supermodular and to bound
both the inverse of the traction $\tau$ of $f$ and the difference
$f(\mathbf{c})-t^{\prime}$ by polynomials in the input size. To see that $f$
is supermodular, we apply Proposition 1. For any $\mathbf{x}\in\mathcal{C}$
with $x_{j}<c_{j}$, we have

$\displaystyle
f(\mathbf{x}+\mathbf{1}^{j})-f(\mathbf{x})=\sum_{k}\log\frac{\overline{p}_{k}(\mathbf{c}-\mathbf{x})}{\overline{p}_{k}(\mathbf{c}-\mathbf{x}-\mathbf{1}^{j})}=\log\left(1+\frac{a_{j}^{k}}{p_{k}(\mathbf{c}-\mathbf{x}-\mathbf{1}^{j})+\epsilon}\right),$
(22)

which is monotone increasing in $\mathbf{x}$.

It follows also from (22) that the traction of $f$ can be bounded from below
by

$\displaystyle\min_{k,~{}j~{}|~{}a_{j}^{k}>0}\log\left(\frac{a_{j}^{k}}{(\mathbf{a}^{k})^{\top}\mathbf{c}+a_{0}^{k}+\epsilon}\right)\geq\frac{1}{\mathcal{L}},$

where $\mathcal{L}$ is the total encoding length of the coefficients of the
given functions. It remains to bound the difference
$f(\mathbf{c})-t^{\prime}$, which can be done as follows:

$\displaystyle f(\mathbf{c})-t^{\prime}$ $\displaystyle=\log
t-\sum_{k}\log(p_{k}(0)+\epsilon)\leq\log{t}+m\log\left(\frac{1}{\epsilon}\right)$
$\displaystyle\leq\log
t+m^{2}\log(2m(1+\max_{k}p_{k}(\mathbf{c})))=O(\mathcal{L}^{2}).$

Thus, we arrive at the following result.

######  Corollary 1.

Consider an inequality $\prod_{k=1}^{m}p_{k}(\mathbf{x})\geq t$ where each
$p_{k}:\mathcal{C}\to\mathbb{Q}_{+}$ is an affine function. Then for any
subset $\mathcal{G}^{\prime}\subseteq\mathcal{G}$ of the family $\mathcal{G}$
of minimal feasible solutions of size $|\mathcal{G}^{\prime}|\geq 2$, it holds
that

$\displaystyle|{\mathcal{I}}^{-1}(\mathcal{G}^{\prime})\cap{\mathcal{I}}^{-1}(\mathcal{G})|\leq|\mathcal{G}^{\prime}|^{o(\log\mathcal{L})},$
(23)

where $\mathcal{L}$ is the total encoding length of the coefficients of the
given functions.

It is worth noting that the enumeration of minimal feasible solutions for a
single inequality involving a product of linear functions over binary vectors
is as hard as (and hence polynomially equivalent to) the well known hypergraph
transversal problem for which the best currently known algorithm is quasi-
polynomial [FK96]. Indeed minimal transversals of a given hypergraph
$\mathcal{H}\subseteq 2^{[n]}$ correspond (one-to-one) to the minimal feasible
solutions of the inequality $\prod_{H\in\mathcal{H}}\sum_{i\in H}x_{i}\geq 1,$
over $\mathbf{x}\in\\{0,1\\}^{n}$.

##  5 Separable Monotone Functions and Polynomial Inequalities

A monotone function $f:\mathcal{C}\mapsto\mathbb{R}_{+}$ is said to be
separable if $f(\mathbf{x})$ can be written as the product of single-variable
non-negative monotone functions. For instance, a polynomial function of the
form (2) is the sum of separable monotone functions. A single-variable
function $g:\\{0,1,\ldots,u\\}\to\mathbb{R}_{+}$ is said to be discretely
convex if for all $x,y\in\mathbb{Z}_{+}$ and $\lambda\in[0,1]$,

$\displaystyle\lambda
g(x)+(1-\lambda)g(y)\geq\min_{u\in\mathbb{Z}_{+}:~{}|\lambda
x+(1-\lambda)y-u|\leq 1}g(u).$

A sufficient condition and necessary condition for discrete convexity is that
(see, e.g., [Yüc02]) the difference $\partial_{g}(x)=g(x+1)-g(x)$ is monotone
in $x$.

Let $f:\mathcal{C}\to\mathbb{R}_{+}$ be the sum of separable monotone
functions, that is,

$\displaystyle f(\mathbf{x})=\sum_{H\in\mathcal{H}}a_{H}\prod_{j\in
H}f_{j}^{H}(x_{j}),\quad\text{ for $x\in\mathcal{C}$},$ (24)

where $\mathcal{H}\subseteq 2^{[n]}$ is a given multiset family (repetitions
allowed), $f_{j}^{H}:\mathbb{Z}_{+}\mapsto\mathbb{R}_{+}$ are non-negative
discretely convex monotone functions and $a_{H}>0$ for all $H\in\mathcal{H}$.

Applying Proposition 1 to the function $f$ defined in (24), we see that a
sufficient condition for $f$ to be supermodular is that the difference
function $\partial_{f_{j}^{H}}(x_{j},j,z)$ is monotone in $x_{j}$, or
equivalently, $f_{j}^{H}$ is discretely convex, for all $j\in[n]$, as

$\displaystyle\partial_{f}(\mathbf{x},j,z)=\sum_{H\in\mathcal{H}~{}|~{}j\in
H}a_{H}\big{(}f_{j}^{H}(x_{j}+1)-f_{j}^{H}(x_{j})\big{)}\prod_{j^{\prime}\in
H\setminus\\{j\\}}f_{j^{\prime}}^{H}(x_{j^{\prime}})$

is monotone whenever
$\partial_{f_{j}^{H}}(x_{j},j,z)=f_{j}(x_{j}+1)-f_{j}(x_{j})$ is monotone in
$x_{j}$. As a corollary of this and the bound mentioned in (B1) above, we
obtain the following result.

######  Proposition 2.

Consider the inequality (5) and suppose that the function
$f:\mathcal{C}\mapsto\mathbb{R}_{+}$ has traction $\tau$ and maximum value
$R:=f(\mathbf{c})\geq t$, and is the sum of discretely convex separable
monotone functions of the form (24), defined by a multiset family
$\mathcal{H}$. Then for any $\mathcal{F}^{\prime}\subseteq\mathcal{F}$ of size
$|\mathcal{F}^{\prime}|\geq 2$, it holds that

$\displaystyle|{\mathcal{I}}(\mathcal{F}^{\prime})\cap{\mathcal{I}}(\mathcal{F})|\leq|\mathcal{F}^{\prime}|^{o(\log\frac{R-t}{\tau})}.$
(25)

When the function $f$ is integer-valued, we can drop the requirement of
discrete convexity. In fact, in this case, the bound in Proposition 2 can be
improved as follows.

######  Theorem 4.

Consider the inequality (5) and suppose that
$f:\mathcal{C}\mapsto\\{0,1,\ldots,R\\}$ is the sum of separable monotone
functions $f(\mathbf{x})=\sum_{H\in\mathcal{H}}a_{H}\prod_{j\in
H}f_{j}^{H}(x_{j})$ defined by a multiset family $\mathcal{H}$, such that each
$f_{j}^{H}:\mathcal{C}_{j}\mapsto\\{0,1,\ldots,R\\}$ is monotone for all $j\in
H\in\mathcal{H}$ and $a_{H}\in\mathbb{Z}_{+}$ for all $H\in\mathcal{H}$. Then
for any non-empty subset $\mathcal{F}^{\prime}\subseteq\mathcal{F}$, it holds
that

$\displaystyle|{\mathcal{I}}(\mathcal{F}^{\prime})\cap{\mathcal{I}}(\mathcal{F})|\leq(R-t)|\mathcal{F}^{\prime}|.$
(26)

To prove Theorem 4, we consider the class of functions having non-negative
Möbius coefficients. Recall that the Möbius function
$\mu:\mathcal{C}\times\mathcal{C}\mapsto\\{-1,0,1\\}$ is given by (see, e.g.,
[Bud88]):

$\mu(\mathbf{y},\mathbf{z})=\left\\{\begin{array}[]{ll}(-1)^{|S|}&\mbox{ if
$\mathbf{y}=\mathbf{z}-\mathbf{1}^{S}$ for some $S\subseteq[n]$ }\\\ 0&\mbox{
otherwise}\end{array}\right.$ (27)

for $\mathbf{y},\mathbf{z}\in\mathcal{C}$, where
$\mathbf{1}^{S}\in\\{0,1\\}^{n}$ is the vector having $\mathbf{1}_{j}^{S}=1$
if and only if $j\in S$. Given a function $f:\mathcal{C}\mapsto\mathbb{R}_{+}$
and an $\mathbf{x}\in\mathcal{C}$, the Möbius inversion formula enables us to
express $f(\mathbf{x})$ as the sum of Möbius coefficients
$\hat{f}(\mathbf{y})$ of all elements $\mathbf{y}\leq\mathbf{x}$:

$f(\mathbf{x})=\sum_{\mathbf{0}\leq\mathbf{y}\leq\mathbf{x}}\hat{f}(\mathbf{y})~{}\Longleftrightarrow~{}\hat{f}(\mathbf{y})=\sum_{\mathbf{0}\leq\mathbf{z}\leq\mathbf{y}}f(\mathbf{z})\mu(\mathbf{z},\mathbf{y}).$
(28)

######  Proposition 3.

Suppose $f:\mathcal{C}\mapsto\\{0,1,\ldots,R\\}$ is the sum of separable
monotone functions: $f(\mathbf{x})=\sum_{H\in\mathcal{H}}a_{H}\prod_{j\in
H}f_{j}^{H}(x_{j})$, where
$f_{j}^{H}:\mathcal{C}_{j}\mapsto\\{0,1,\ldots,R\\}$ is a monotone function
and $a_{H}\geq 0$ for all $H\in\mathcal{H}$. Then $\hat{f}(\mathbf{x})\geq 0$
for all $\mathbf{x}\in\mathcal{C}$.

###### Proof.

Consider a term $g_{H}(\mathbf{x}):=\prod_{j\in H}f_{j}^{H}(x_{j})$. If
$x_{j}>0$ for some $j\not\in H$, we have $\hat{g}_{H}(\mathbf{x})=0$.
Otherwise,

$\hat{g}_{H}(\mathbf{x})=\sum_{S\subseteq
H}(-1)^{|S|}g_{H}(\mathbf{x}-\mathbf{1}^{S})=\sum_{S\subseteq
H}(-1)^{|S|}\prod_{j\in H}f_{j}^{H}(\mathbf{x}-\mathbf{1}^{S})=\prod_{j\in
H}[f_{j}^{H}(x_{j})-f_{j}^{H}(x_{j}-1)],$

for any $\mathbf{x}\in\mathcal{C}$, where we assume $f_{j}^{H}(-1):=0$ for all
$j\in H$. The non-negativity of $\hat{g}_{H}(\mathbf{x})$ follows form the
monotonicity of $f_{j}^{H}$. By the linearity of the Möbius transform, it
follows then that
$\hat{f}(\mathbf{x})=\sum_{H\in\mathcal{H}_{i}}a_{H}\hat{g}_{H}(\mathbf{x})\geq
0$. ∎

###### Proof of Theorem 4.

The theorem follows from the following intersection inequality from [BGKM04]:

######  Lemma 5 (Intersection Lemma [BGKM04]).

Let $\mathcal{S},\mathcal{T}\subseteq 2^{U}$ be two families of subsets of a
given set $U$, and let $w:U\rightarrow\mathbb{R}_{+}$ be a given non-negative
weight function on $U$. Suppose $\mathcal{S}$ and $\mathcal{T}$ are threshold
separable, i.e., there are real thresholds $t_{1}<t_{2}$, such that $w(T)\leq
t_{1}$, for all $T\in\mathcal{T}$, and $w(S)\geq t_{2}$, for all
$S\in\mathcal{S}$, where $w(X)=\sum_{v\in X}w(v)$ for $X\subseteq U$. Suppose
further that $|\mathcal{S}|\geq 2$ and $\mathcal{T}$ covers all pairwise
intersections of $\mathcal{S}$, i.e., for all $S,S^{\prime}\in\mathcal{S}$,
$S\neq S^{\prime}$, there exists a $T\in\mathcal{T}$ such that $S\cap
S^{\prime}\subseteq T$. Then

$(i)$ $|\mathcal{S}|\leq\sum_{T\in\mathcal{T}}|U\setminus T|$,

$(ii)$ $|\mathcal{S}|\leq\frac{w(U)-t_{1}}{t_{2}-t_{1}}|\mathcal{T}|$.

The proof of part (i) of Lemma 5 was given in [BGKM04]. The proof of part (ii)
for the unweighted case (i.e., $w(u)=1$ for all $u\in U$) was given (for a
weaker inequality) in [BGKM00]. We include the proof of the weighted case of
part (ii) in the appendix for completeness.

Now to prove Theorem 4, we let ${\mathcal{Y}}:=\mathcal{F}^{\prime}$,
$\mathcal{X}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}{\mathcal{I}}({\mathcal{Y}})\cap{\mathcal{I}}(\mathcal{F})$,
and consider the (one-to-one) monotonic mapping $\phi:\mathcal{C}\mapsto
2^{\mathcal{C}}$ defined by:
$\phi(\mathbf{x})=\\{\mathbf{z}\in\mathcal{C}~{}|~{}\mathbf{z}\leq\mathbf{x}\\}$.
Let $U:=\mathcal{C}$,
$\mathcal{S}:=\\{\phi(\mathbf{x})~{}|~{}\mathbf{x}\in\mathcal{X}\\}$, and
$\mathcal{T}:=\\{\phi(\mathbf{y})~{}|~{}\mathbf{y}\in{\mathcal{Y}}\\}$. Thus
with respect to the non-negative weight function
$w\equiv\hat{f}:U\to\mathbb{R}_{+}$, we obtain the threshold separability

$\displaystyle\begin{array}[]{ll}w(\phi(\mathbf{x}))&=\sum_{\mathbf{0}\leq\mathbf{z}\leq\mathbf{x}}\hat{f}(\mathbf{z})=f(\mathbf{x})\geq
t_{2}:=t+1,\mbox{for all }x\in\mathcal{X};\\\
w(\phi(\mathbf{y}))&=\sum_{\mathbf{0}\leq\mathbf{z}\leq\mathbf{y}}\hat{f}(\mathbf{z})=f(\mathbf{y})\leq
t_{1}:=t,\mbox{for all }y\in{\mathcal{Y}},\end{array}$ (31)

of $\mathcal{S}$ and $\mathcal{T}$. If $|\mathcal{X}|=|\mathcal{S}|=1$, then
$|\mathcal{X}|\leq(f(\mathbf{u})-t)|{\mathcal{Y}}|$ holds, for otherwise we
get the contradiction $t+1\leq f(\mathbf{x})\leq f(\mathbf{u})\leq t$, for the
element $\mathbf{x}\in\mathcal{X}$. Let us assume therefore that
$|\mathcal{S}|\geq 2$, and observe that $\mathcal{T}$ covers all pairwise
intersections of $\mathcal{S}$: for any two distinct elements
$\mathbf{x},\mathbf{x}^{\prime}\in\mathcal{X}$, it follows by
$\mathbf{x},\mathbf{x}^{\prime}\in{\mathcal{I}}({\mathcal{Y}})$ that there is
a $\mathbf{y}\in{\mathcal{Y}}$ such that
$\mathbf{x}\wedge\mathbf{x}^{\prime}\leq\mathbf{y}$, and therefore, we get

$\phi(\mathbf{x})\cap\phi(\mathbf{x}^{\prime})=\phi(\mathbf{x}\wedge\mathbf{x}^{\prime})\subseteq\phi(\mathbf{y}).$

Now we apply Lemma 5(ii) to get

$\left|{\mathcal{I}}(\mathcal{F}^{\prime})\cap{\mathcal{I}}(\mathcal{F})\right|=|\mathcal{S}|\leq\left(\sum_{\mathbf{0}\leq\mathbf{z}\leq\mathbf{u}}\hat{f}(\mathbf{z})-t_{i}\right)|\mathcal{T}|=(f(\mathbf{u})-t)|{\mathcal{Y}}|.$

∎

Theorem 4 implies that, if the threshold $t$ is sufficiently close to the
maximum value of $f$, then the enumeration problem can be solved in quasi-
polynomial time. In the other extreme case, when each
$t=\operatorname{poly}(\mathcal{L})$ is sufficiently far form the maximum
value, we can improve the bound in Theorem 4 (with slightly some more
restrictions on the functions $f_{j}^{H}$) as follows.

######  Theorem 6.

Consider the inequality (5) and suppose that
$f:\mathcal{C}\mapsto\\{0,1,\ldots,R\\}$ is the sum of separable monotone
functions $f(\mathbf{x})=\sum_{H\in\mathcal{H}}a_{H}\prod_{j\in
H}f_{j}^{H}(x_{j})$ defined by a (non-empty) multiset family $\mathcal{H}$,
such that each $f_{j}^{H}:\mathcal{C}_{j}\mapsto\\{0,1,\ldots,R\\}$ is
monotone with $f_{j}^{H}(0)=0$ and $f^{H}_{j}(1)\geq 1$, for all $j\in
H\in\mathcal{H}$ and $a_{H}\in\mathbb{Z}_{+}$ for all $H\in\mathcal{H}$. Then
for any non-empty subset $\mathcal{F}^{\prime}\subseteq\mathcal{F}$, it holds
that

$\displaystyle|{\mathcal{I}}(\mathcal{F}^{\prime})\cap{\mathcal{I}}(\mathcal{F})|\leq\left(|\mathcal{H}|+\big{(}1+(1+\Delta)n\big{)}(t+1)|\mathcal{F}^{\prime}|\right)|\mathcal{F}^{\prime}|,$
(32)

where $\Delta:=\max_{j\in
H\in\mathcal{H},~{}x\in\mathcal{C}_{j}\setminus\\{0\\}}\frac{\partial_{f_{j}^{H}}(x)}{f_{j}^{H}~{}(x)}$.

###### Proof.

Let ${\mathcal{Y}}:=\mathcal{F}^{\prime}$,
$\mathcal{X}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}{\mathcal{I}}({\mathcal{Y}})\cap{\mathcal{I}}(\mathcal{F})$.
We consider a partition of $\mathcal{X}:=\mathcal{X}_{1}\cup\mathcal{X}_{2}$,
where $\mathcal{X}_{1}:=\mathcal{X}\cap\\{0,1\\}^{n}$ and
$\mathcal{X}_{2}:=\mathcal{X}\setminus\mathcal{X}_{1}$, and define
${\mathcal{Y}}_{1}:=\\{\mathbf{y}\wedge\boldsymbol{1}~{}|~{}\mathbf{y}\in{\mathcal{Y}}\\}$,
where $\boldsymbol{1}$ is the vector of all ones. We first bound the size of
$\mathcal{X}_{1}$. Let $U:=\mathcal{H}$,
$\mathcal{S}:=\\{\phi(\mathbf{x})~{}|~{}\mathbf{x}\in\mathcal{X}_{1}\\}$, and
$\mathcal{T}:=\\{\phi(\mathbf{y})~{}|~{}\mathbf{y}\in{\mathcal{Y}}_{1}\\}$,
where the monotonic mapping $\phi:\mathcal{C}\to 2^{\mathcal{H}}$ is defined
by:
$\phi(\mathbf{x}):=\\{H\in\mathcal{H}~{}|~{}\boldsymbol{1}^{H}\leq\mathbf{x}\\}$.
Note that our assumptions imply that, for $\mathbf{x}\in\\{0,1\\}^{n}$,

$\displaystyle f(\mathbf{x})$
$\displaystyle=\sum_{H\in\mathcal{H}}a_{H}\prod_{j\in
H}f_{j}^{H}(1)\prod_{j\in
H}x_{j}=\sum_{H\in\mathcal{H}~{}:~{}\boldsymbol{1}^{H}\leq\mathbf{x}}a_{H}\prod_{j\in
H}f_{j}^{H}(1).$

Thus with respect to the non-negative weight function $w:U\to\mathbb{R}_{+}$,
defined by $w(H):=\prod_{j\in H}f_{j}^{H}(1)$ for $H\in\mathcal{H}$, we obtain
the threshold separability

$\displaystyle w(\phi(\mathbf{x}))$ $\displaystyle=f_{i}(\mathbf{x})\geq
t+1,\mbox{ for all
}x\in\mathcal{X}_{1};~{}~{}~{}~{}~{}w(\phi(\mathbf{y}))=f_{i}(\mathbf{y})\leq
t,\mbox{for all }y\in{\mathcal{Y}}_{1},$

of $\mathcal{S}$ and $\mathcal{T}$. Observe that $\mathcal{T}$ covers all
pairwise intersections of $\mathcal{S}$: for any two distinct elements
$\mathbf{x},\mathbf{x}^{\prime}\in\mathcal{X}_{1}$, it follows by
$\mathbf{x},\mathbf{x}^{\prime}\in{\mathcal{I}}({\mathcal{Y}})\cap\\{0,1\\}^{n}$
that there is a $\mathbf{y}\in{\mathcal{Y}}_{1}$ such that
$\mathbf{x}\wedge\mathbf{x}^{\prime}\leq\mathbf{y}$, and therefore, we get

$\displaystyle\phi(\mathbf{x})\cap\phi(\mathbf{x}^{\prime})=\phi(\mathbf{x}\wedge\mathbf{x}^{\prime})\subseteq\phi(\mathbf{y}).$
(33)

Threshold separability together with (33) also implies that
$|\mathcal{S}|=|\mathcal{X}_{1}|$. If $|\mathcal{S}|=|\mathcal{X}_{1}|=1$,
then $|\mathcal{S}|\leq|\mathcal{H}|\cdot|{\mathcal{Y}}|$ holds by the non-
emptiness of $\mathcal{H}$ and ${\mathcal{Y}}$. Let us assume therefore that
$|\mathcal{S}|\geq 2$, and apply Lemma 5(i) to get

$\displaystyle\left|\mathcal{X}_{1}\right|=|\mathcal{S}|\leq\sum_{\mathbf{y}\in{\mathcal{Y}}_{1}}|\mathcal{H}\setminus\phi(\mathbf{y})|\leq|\mathcal{H}|\cdot|{\mathcal{Y}}|.$
(34)

Next, we will show that

$\displaystyle\left|\mathcal{X}_{2}\right|\leq\big{(}1+(1+\Delta)n\big{)}(t+1)|{\mathcal{Y}}|^{2},$
(35)

which together with (34) would imply the theorem. To see (35), we consider the
monotonic mapping $\phi:\mathcal{C}\mapsto 2^{\mathcal{C}}$ defined by:
$\phi(\mathbf{x})=\\{\mathbf{z}\in\mathcal{C}~{}|~{}\mathbf{z}\leq\mathbf{x}\\}$.
Let $\mathcal{S}:=\\{\phi(\mathbf{x})~{}|~{}\mathbf{x}\in\mathcal{X}_{2}\\}$
and $\mathcal{T}:=\\{\phi(\mathbf{y})~{}|~{}\mathbf{y}\in{\mathcal{Y}}\\}$. By
definition of $\mathcal{X}_{2}$, for any $\mathbf{x}\in\mathcal{X}_{2}$, there
exists a $j=j^{\mathbf{x}}\in[n]$ such that $x_{j}>1$. As
$\mathcal{X}_{2}\subseteq{\mathcal{I}}({\mathcal{Y}})$, for any
$\mathbf{x}\in\mathcal{X}_{2}$, there is a
$\mathbf{y}=\mathbf{y}^{\mathbf{x}}\in{\mathcal{Y}}$ satisfying
$\mathbf{x}-\mathbf{1}^{j^{\mathbf{x}}}\leq\mathbf{y}$. It is important for
the following argument to note that $y^{\mathbf{x}}_{j}\geq 1$ (and hence
$f^{H}_{j}(y_{j}^{\mathbf{x}})\geq 1$), for any $\mathbf{x}\in\mathcal{X}_{2}$
and $j=j^{\mathbf{x}}$, as this implies that, for
$\mathbf{y}=\mathbf{y}^{\mathbf{x}}$,

$\displaystyle f(\mathbf{y}+\mathbf{1}^{j})$
$\displaystyle=f(\mathbf{y})+\sum_{H\in\mathcal{H}~{}|~{}j\in
H}a_{H}\big{(}f_{j}^{H}(y_{j}+1)-f_{j}^{H}(y_{j})\big{)}\prod_{j^{\prime}\in
H\setminus\\{j\\}}f_{j^{\prime}}^{H}(y_{j^{\prime}})$
$\displaystyle=f(\mathbf{y})+\sum_{H\in\mathcal{H}~{}|~{}j\in
H}a_{H}\frac{f_{j}^{H}(y_{j}+1)-f_{j}^{H}(y_{j})}{f_{j}^{H}(y_{j})}\prod_{j^{\prime}\in
H}f_{j^{\prime}}^{H}(y_{j^{\prime}})$ $\displaystyle\leq
f(\mathbf{y})+\Delta\sum_{H\in\mathcal{H}~{}|~{}j\in
H}a_{H}\prod_{j^{\prime}\in H}f_{j^{\prime}}^{H}(y_{j^{\prime}})\leq
f(\mathbf{y})+\Delta f(\mathbf{y})\leq(1+\Delta)t.$

Define
${\mathcal{Y}}_{2}:=\\{\mathbf{y}^{\mathbf{x}}+\boldsymbol{1}^{j^{\mathbf{x}}}~{}|~{}\mathbf{x}\in\mathcal{X}_{2}\\}$,
and $U:=\\{\mathbf{z}\in\mathcal{C}~{}|~{}\mathbf{z}\leq\mathbf{y}\text{ for
}\mathbf{y}\in{\mathcal{Y}}\cup{\mathcal{Y}}_{2}\\}$. The definition of $U$
and the monotonicity of the mapping $\phi$ imply that
$\phi(\mathbf{x}),\phi(\mathbf{y})\subseteq U$ for all
$\mathbf{x}\in\mathcal{X}_{2}$ and $\mathbf{y}\in{\mathcal{Y}}$. Note also
that $|{\mathcal{Y}}_{2}|\leq n|{\mathcal{Y}}|$.

Now we proceed in a way similar to the proof of Theorem 4. We apply Lemma
5(ii) using the non-negative weight function
$w\equiv\hat{f}:U\to\mathbb{R}_{+}$, and the threshold separability (31) of
$\mathcal{S}$ and $\mathcal{T}$. If $|\mathcal{X}_{2}|=|\mathcal{S}|=1$, then
(35) holds trivially. Thus we may assume that $|\mathcal{S}|\geq 2$, and
observe again that $\mathcal{T}$ covers all pairwise intersections of
$\mathcal{S}$. Applying the lemma, we obtain

$\displaystyle\left|\mathcal{X}_{2}\right|$
$\displaystyle=|\mathcal{S}|\leq\left(\sum_{\mathbf{z}\in
U}\hat{f}(\mathbf{z})-t_{i}\right)|\mathcal{T}|\leq\left(\sum_{\mathbf{y}\in{\mathcal{Y}}}\sum_{\mathbf{0}\leq\mathbf{z}\leq\mathbf{y}}\hat{f}(\mathbf{z})+\sum_{\mathbf{y}\in{\mathcal{Y}}_{2}}\sum_{\mathbf{0}\leq\mathbf{z}\leq\mathbf{y}}\hat{f}(\mathbf{z})-t\right)|\mathcal{T}|$
$\displaystyle=\left(\sum_{\mathbf{y}\in{\mathcal{Y}}}{f}(\mathbf{y})+\sum_{\mathbf{y}\in{\mathcal{Y}}_{2}}f(\mathbf{y})-t\right)|\mathcal{T}|\leq\left(t|{\mathcal{Y}}|+(1+\Delta)t|{\mathcal{Y}}_{2}|-t\right)|\mathcal{T}|$
$\displaystyle\leq\big{(}(1+(1+\Delta)n)|{\mathcal{Y}}|-1\big{)}t|{\mathcal{Y}}|,$

establishing (35). ∎

Applying Theorem 6 to a polynomial function of the form (2) with
$f_{j}^{H}(x_{j}):=x_{j}^{d_{H,j}}$ and noting that
$\max_{x\in\mathcal{C}_{j}\setminus\\{0\\}}\frac{\partial_{f_{j}^{H}}(x)}{f_{j}^{H}~{}(x)}\leq\max_{x\geq
1}\frac{(x+1)^{d_{H,j}}}{x^{d_{H,j}}}-1=2^{d_{H,j}}-1$, we arrive at the
following result.

######  Corollary 2.

Consider the inequality (5) and suppose that the function
$f:\mathcal{C}\mapsto\\{0,1,\ldots,R\\}$ is a polynomial of the form (2)
defined by a (non-empty) multiset family $\mathcal{H}$, and coefficients
$a_{H}\in\mathbb{Z}_{+}$ for $H\in\mathcal{H}$. Then for any non-empty subset
$\mathcal{F}^{\prime}\subseteq\mathcal{F}$, it holds that

$\displaystyle|{\mathcal{I}}(\mathcal{F}^{\prime})\cap{\mathcal{I}}(\mathcal{F})|\leq\min\left\\{R-t,|\mathcal{H}|+\big{(}1+2^{d}n)(t+1)|\mathcal{F}^{\prime}|\right\\}|\mathcal{F}^{\prime}|.$
(36)

where $d:=\max_{j\in H\in\mathcal{H}}d_{H,j}$.

Note that, unlike the result in Corollary 2, the result in (B3) requires the
total degree in each monomial to be bounded by a constant (but without any
restriction on $t$) to guarantee quasi-polynomial enumeration.

We complement Corollary 2 with the following negative result, which shows that
the polynomial dependence on $|\mathcal{H}|$ in the bound (36) is necessary.

######  Proposition 4.

There exists a polynomially computable polynomial function
$f:\\{0,1\\}\to\\{0,1\\}$, for which problem
GEN$(\mathcal{F},\mathcal{F}^{\prime})$ of incrementally generating the
maximal feasible solutions of the inequality $f(x)\leq 0$ is NP-hard.

###### Proof.

The result follows from the following reduction from the so-called relay cuts
enumeration problem in a relay circuit with two terminals. Let $G=(V,E)$ be a
graph with vertex set $V$ and edge set $E$, and two distinguished vertices
$s,t\in V$. To each edge in $e\in E$, is assigned a relay $j(e)\in[n]$ from a
given set of relays $[n]$ (two or more distinct edges may be assigned
identical relays). Let $\mathcal{F}$ be the family of all minimal $s$-$t$
relay cuts, i.e., minimal subsets of relays that disconnect $s$ and $t$. It is
known that the problem of incrementally generating $\mathcal{F}$ is NP-hard,
see [GK99]. We define a polynomial $f:\\{0,1\\}\to\mathbb{Z}_{+}^{n}$ as
follows. Let $\mathcal{P}$ be the set of (not necessarily simple) paths
between $s$ and $t$ of length $|V|$ in $G$. We associate a variable $x_{j}$ to
each relay $j\in[n]$, and for $\mathbf{x}\in\\{0,1\\}^{n}$, we let

$\displaystyle f(\mathbf{x})=\sum_{P\in\mathcal{P}}\prod_{e\in P}x_{j(e)}.$
(37)

Given $\mathbf{x}\in\\{0,1\\}^{n}$, we can compute $f(\mathbf{x})$ in
polynomial time (this requires only computing the $n^{th}$ power of the
adjacency matrix of the graph $G(\mathbf{x})$ obtained from $G$ by deleting
all edges $e$ with $x_{j(e)}=0$. In fact, checking the feasibility of
$\mathbf{x}$ is equivalent to checking if there is an $s$-$t$ path in
$G(\mathbf{x})$). This gives a polynomial time evaluation oracle for $f$.
Finally, note that minimal $s$-$t$ relay cuts are exactly the complements of
the maximal feasible solutions $\mathcal{F}$ of the polynomial inequality
$f(\mathbf{x})\leq 0$. ∎

Note that the value of $|\mathcal{H}|$ in the NP-hardness construction above
is exponential in $n$. Whether a bound of the form (36) that is independent of
$t$ (as in the Boolean case [BGKM04], where it is known that
$|{\mathcal{I}}(\mathcal{F}^{\prime})\cap{\mathcal{I}}(\mathcal{F})|\leq|\mathcal{H}|\cdot|\mathcal{F}^{\prime}|$)
exists remains an interesting open question.

##  6 Second-order Cone Inequalities

For a vector $\mathbf{v}\in\mathbb{R}^{n}$, denote by $\|\mathbf{v}\|$ the
$\ell_{2}$ norm of $\mathbf{v}$. Consider the monotone second-order cone
inequality:

$\displaystyle\displaystyle
f(\mathbf{x}):=\|A\mathbf{x}\|+\mathbf{b}^{\top}\mathbf{x}\leq~{}t,$ (38)

where $A\in\mathbb{R}_{+}^{d\times n}$ and $\mathbf{b}\in\mathbb{R}_{+}^{n}$
are given matrix and vector. In the special case when $b=\mathbf{0}$, we can
derive the following bound using (B3) as (38) reduced to a quadratic
inequality.

######  Proposition 5.

Let $\mathcal{F}$ be the set of maximal feasible vectors for (38), where
$\mathbf{b}=\mathbf{0}$. Then, for any non-empty
$\mathcal{F}^{\prime}\subseteq\mathcal{F}$, it holds that

$\displaystyle|{\mathcal{I}}(\mathcal{F}^{\prime})\cap{\mathcal{I}}(\mathcal{F})|\leq
2n^{2}(2|\mathcal{F}^{\prime}|+1)^{2}.$ (39)

###### Proof.

When $\mathbf{b}=\mathbf{0}$, we can write the inequality in (38) as
$(f(\mathbf{x}))^{2}\leq t^{2}$, where
$(f(\mathbf{x}))^{2}=\mathbf{x}^{\top}A^{\top}A\mathbf{x}$ is a quadratic
function with non-negative coefficients. It follows from (B3) (with $s=n^{2}$
and $p=2$) that
$|{\mathcal{I}}(\mathcal{F}^{\prime})\cap{\mathcal{I}}(\mathcal{F})|\leq
2n^{2}(2|\mathcal{F}^{\prime}|+1)^{2}$. ∎

When some $\mathbf{b}\neq\mathbf{0}$, the above argument does not
work222Indeed, squaring does not yield an equivalent problem as taking the
square root results in two possibilities (e.g., consider
$\sqrt{x_{1}+x_{2}}+2x_{1}\leq 1$; squaring yields $x_{1}+x_{2}\leq 1$ which
is not an equivalent inequality). Moreover, squaring both sides of an
inequality like (38) may yield a term with a negative coefficient (indeed we
get
$\mathbf{x}^{\top}A^{\top}A\mathbf{x}+2t\mathbf{b}^{\top}\mathbf{x}-(\mathbf{b}^{\top}\mathbf{x})^{2}\leq
t^{2}$), where the result in (B3) cannot be applied (e.g., consider
$\sqrt{x_{1}+x_{2}}+x_{1}+x_{2}\leq 2$; squaring yields
$2x_{2}+2x_{2}-x_{1}x_{2}\leq 2$ which is an equivalent inequality but with a
negative coefficient).. To bound the number of infeasible vectors for (38), we
use a different argument based on a semi-infinite linear formulation of (38).

Denote by
$\mathbb{B}^{d}_{+}(0,1):=\\{\mathbf{x}\in\mathbb{R}_{+}^{d}:~{}\|\mathbf{x}\|\leq
1\\}$ the non-negative half of the $d$-dimensional unit ball centered at the
origin. We can rewrite (38) in the following equivalent form:

$\displaystyle\displaystyle
f_{\mathbf{u}}(\mathbf{x}):=\mathbf{u}^{\top}A\mathbf{x}+\mathbf{b}^{\top}\mathbf{x}\leq~{}t,\quad\text{
for }\mathbf{u}\in\mathbb{B}^{d}_{+}(0,1).$ (40)

As (40) is a (semi-infinite) monotone system of linear inequalities, we may be
tempted to apply the result in (B2) for a single inequality and then take a
union bound. However, as the number of inequalities in (40) is infinite and
the union is taken over an uncountable set, the union bound does not hold333In
fact, a simple but incorrect proof via the union bound can go as follows.
Using the notation in the proof of Theorem 8, we have
$|{\mathcal{I}}(\mathcal{F}^{\prime})\cap{\mathcal{I}}(\mathcal{F})|=|\bigcup_{i\in[r],~{}\mathbf{u}\in\mathbb{B}^{d_{i}}_{+}(0,1)}{\mathcal{I}}(\mathcal{F}^{\prime})\cap{\mathcal{I}}(\mathcal{F}_{\mathbf{u},i})|\leq\sum_{i=1}^{r}\int_{\mathbb{B}^{d_{i}}_{+}(0,1)}|{\mathcal{I}}(\mathcal{F}^{\prime})\cap{\mathcal{I}}(\mathcal{F}_{\mathbf{u},i})|d\mathbf{u}\leq
n|\mathcal{F}^{\prime}|\sum_{i=1}^{r}\operatorname{vol}(\mathbb{B}^{d_{i}}_{+}(0,1))\sim\frac{n|\mathcal{F}^{\prime}|}{\sqrt{d\pi}}\left(\frac{2\pi
e}{d}\right)^{d/2}$, if $d_{i}=d$ for all $i$. This (incorrect) bound is
counter-intuitive in the sense that it decreases with $d$ (for large $d$)..
Instead, we argue that we can take the union bound only over $O(n^{d})$
inequalities. To see this, we first recall the following definition and a
lemma.

A monotone function $f:\mathcal{C}\rightarrow\mathbb{R}_{+}$ is called
2-monotonic if there exists a permutation $\sigma:[n]\to[n]$ such that, for
all $\mathbf{x}\in\mathcal{C}$ and $k,j\in[n]$ with $k<j$,
$\mathbf{x}_{\sigma(k)}<c_{\sigma(k)}$ and $\mathbf{x}_{\sigma(j)}>0$, it
holds that $f(\mathbf{x}+\mathbf{1}^{\sigma(k)}-\mathbf{1}^{\sigma(j)})\geq
f(\mathbf{x})$. For instance, if $f(\mathbf{x}):=\sum_{j}^{n}w_{j}x_{j}$ is a
linear function with non-negative coefficients (i.e., $\mathbf{w}\geq 0$),
then $f$ is 2-monotonic (with $\sigma=\sigma_{\mathbf{w}}$ being a permutation
satisfying $w_{\sigma(1)}\geq w_{\sigma(2)}\geq\cdots\geq w_{\sigma(n)}$).

######  Lemma 7 ([Cra87, BEG+02]).

Consider the system (1) and suppose that each function
$f_{i}:\mathcal{C}\mapsto\mathbb{R}_{+}$ is a 2-monotonic function as verified
by a permutation $\sigma_{i}:[n]\to[n]$. Let $\mathcal{F}$ be the set of
maximal feasible vectors for (1). Then for any non-empty subset
$\mathcal{F}^{\prime}\subseteq\mathcal{F}$, it holds that

$\displaystyle|{\mathcal{I}}(\mathcal{F}^{\prime})\cap{\mathcal{I}}(\mathcal{F})|\leq
r^{\prime}\sum_{\mathbf{y}\in\mathcal{F}^{\prime}}q(\mathbf{y}),$ (41)

where $r^{\prime}$ is the number of distinct permutations among
$\sigma_{1},\ldots,\sigma_{r}$ and
$q(\mathbf{y}):=|\\{j\in[n]~{}:~{}y_{j}<c_{j}\\}|$.

We give the proof in the appendix for completeness. We will also need the
following geometric fact.

######  Fact 1 (see, e.g., [Mat02]).

Any arrangement of $m$ $d$-dimensional hyperplanes partitions $\mathbb{R}^{d}$
into at most
$\Phi_{d}(m):=\sum_{i=0}^{d}\binom{m}{i}\leq\left(\frac{em}{d}\right)^{d}$
maximal connected regions not intersected by any of the hyperplanes (called
cells of the arrangement).

We are now ready to prove Theorem 8.

######  Theorem 8.

Let $\mathcal{F}$ be the set of maximal feasible vectors for (38). Then for
any non-empty subset $\mathcal{F}^{\prime}\subseteq\mathcal{F}$, it holds that

$\displaystyle|{\mathcal{I}}(\mathcal{F}^{\prime})\cap{\mathcal{I}}(\mathcal{F})|\leq\Phi_{d}(n(n-1)/2)n|\mathcal{F}^{\prime}|=O(n)^{2d+1}|\mathcal{F}^{\prime}|.$
(42)

###### Proof.

For $\mathbf{u}\in\mathbb{B}_{+}^{d}(0,1)$, let
$\mathbf{w}^{\mathbf{u}}:=A^{\top}\mathbf{u}+\mathbf{b}\in\mathbb{R}_{+}^{n}$
and $\mathcal{F}_{\mathbf{u}}$ be the set of maximal feasible solutions for
the inequality
$f_{\mathbf{u}}(\mathbf{x})=(\mathbf{w}^{\mathbf{u}})^{\top}\mathbf{x}\leq
t_{i}$. By Lemma 7, it is enough to show that the number of distinct
permutations defined by the set of weights
$\\{\mathbf{w}^{\mathbf{u}}~{}|~{}\mathbf{u}\in\mathbb{B}^{d}_{+}(0,1)\\}$ is
at most $\Phi_{d}(n(n-1)/2)$. More precisely, to each vector
$\mathbf{w}\in\mathbb{R}^{n}_{+}$, let us assign a permutation
$\sigma=\sigma_{\mathbf{w}}$ satisfying $w_{\sigma(1)}\geq
w_{\sigma(2)}\geq\cdots\geq w_{\sigma(n)}$ (note that that there may be
multiple permutations $\sigma$ satisfying this, in which case
$\sigma_{\mathbf{w}}$ is chosen arbitrarily among them). Then we claim that

$\displaystyle|\\{\sigma_{\mathbf{w}^{\mathbf{u}}}~{}|~{}\mathbf{u}\in\mathbb{B}^{d}_{+}(0,1)\\}|\leq\Phi_{d}(n(n-1)/2).$
(43)

To see (43), let us write $A=[\mathbf{a}^{1},\ldots,\mathbf{a}^{n}]$ where
$\mathbf{a}^{j}\in\mathbb{R}^{d}_{+}$ is the $j$th column of $A$. Then
$w_{j}=w_{j}^{\mathbf{u}}=(\mathbf{a}^{j})^{\top}\mathbf{u}+b_{j}$. Let us
consider the system of inequalities $w_{j}\leq w_{j^{\prime}}$ for
$j,j^{\prime}\in[n]$ (considering $\mathbf{u}$ as a variable in
$\mathbb{R}^{d}$):

$\displaystyle\left(\mathbf{a}^{j}-\mathbf{a}^{j^{\prime}}\right)^{\top}\mathbf{u}\leq
b_{j^{\prime}}-b_{j},\quad\text{ for }j\neq j^{\prime}\in[n].$ (44)

The inequality-defining hyperplanes in (44) form a hyperplane arrangement
that, by Fact 1, partitions $\mathbb{R}^{d}$ into at most $\Phi_{d}(n(n-1)/2)$
cells. Consider any such cell $C$. Any point $\mathbf{u}\in C$ decides, for
each pair $j\neq j^{\prime}$, whether $w^{\mathbf{u}}_{j}\leq
w^{\mathbf{u}}_{j^{\prime}}$ or
$w^{\mathbf{u}}_{j}>w^{\mathbf{u}}_{j^{\prime}}$, and hence can be associated
with a total order on the weights
$w^{\mathbf{u}}_{1},\ldots,w^{\mathbf{u}}_{n}$. Moreover, all points in $C$
give rise to the same total order, while any two points belonging ot two
different cells give rise to two different orders. It follows that the number
of such orders is exactly equal to the number of cells. This establishes (43)
and the theorem. ∎

##  7 Positive Semidefinite Matrix Inequalities

We denote by $\SS^{m}$ the set of all $m\times m$ real symmetric matrices and
by $\SS^{m}_{+}\subseteq\SS^{m}$ the set of all $m\times m$ positive
semidefinite matrices. Consider the monotone positive semidefinite inequality:

$\displaystyle\displaystyle f(\mathbf{x})\preceq~{}T,$ (45)
$\displaystyle\mathbf{x}\in\mathbb{Z}_{+}^{n},$

where $f(\mathbf{x}):=\sum_{j=1}^{n}A^{j}x_{j}$, $A^{j}\in\SS_{+}^{m}$, for
$j\in[n]$, and $T\in\SS^{m}_{+}$ are given positive semidefinite matrices, and
”$\succeq$“ is the Löwner (partial) order on matrices: $A\succeq B$ if and
only if $A-B$ is positive semidefinite.

Let $\mathbf{I}_{m}$ be the $m\times m$ identity matrix. For two matrices
$A\succeq B\succeq 0$, we use the standard notation: $A\bullet
B=\text{Tr}(AB):=\sum_{k=1}^{m}\sum_{j=1}^{m}a_{k,j}b_{kj}$, where $a_{k,j}$
denotes the $kj$th entry of the matrix $A$. We recall the following well-known
facts; see,.e.g., [HJ90]:

######  Fact 2.

Let $A\in\SS^{m}$. Then

  * (i)

$A\in\SS_{+}^{m}$ iff $A\bullet B\geq 0$ for all $B\in\SS_{+}^{m}$;

  * (ii)

if $A\in\SS_{+}^{m}$ then for any $i\in[m]$, $a_{ii}\geq 0$ with $a_{ii}=0$
implying that the entire $i$th row and columns of $A$ are zero;

  * (iii)

$A\in\SS_{+}^{m}$ iff for any invertible matrix $B\in\SS^{m}$,
$BAB^{\top}\succeq 0$;

  * (iv)

if $A\in\SS_{+}^{m}$ and $\operatorname{rank}(A)=k$, then there exists a
(unique) orthonormal matrix $U$ (that is, $UU^{\top}=I_{m}$) such that, upto a
permutation of the rows and columns of $A$, we can write

$\displaystyle UAU^{\top}$
$\displaystyle=\bar{\mathbf{I}}_{k}:=\left[\begin{array}[]{c|c}\mathbf{I}_{k}&0\\\
\hline\cr 0&0\end{array}\right].$ (48)

By Fact 2(i), if $\mathbf{x}$ satisfies (45), then $\mathbf{I}_{m}\bullet
f(\mathbf{x})=\sum_{j=1}^{n}\mathbf{I}_{m}\bullet
A^{j}x_{j}\leq\mathbf{I}_{m}\bullet T$, which in turn implies that $x_{j}\leq
c_{j}^{\prime}:=\frac{\text{Tr}(T)}{\text{Tr}(A^{j})}$. Thus we may restrict
the set of solutions for (45) to the integer box
$\mathcal{C}:=\\{\mathbf{x}\in\mathbb{R}^{n}|~{}0\leq\mathbf{x}\leq\mathbf{c}\\}$,
where $c_{j}:=\lfloor c_{j}^{\prime}\rfloor$. Suppose that
$\operatorname{rank}(T)=d$. By Fact 2(iv), we can write
$UTU^{\top}=\bar{\mathbf{I}}_{d}$, for an orthonormal matrix $U$. Fact 2(iii)
then implies that we can left-multiply by $U$ and right-multiply by $U^{\top}$
both sides of the $i$th inequality in (45) without changing the set of
feasible solutions. In other words, after possibly permuting the rows and
columns of the matrices $A^{j}$, we can write (45) as follows:

$\displaystyle\displaystyle\sum_{j=1}^{n}B^{j}x_{j}\preceq~{}\bar{\mathbf{I}}_{d},$
(49) $\displaystyle\mathbf{x}\in\mathcal{C},$

where $B^{j}:=UA^{j}U^{\top}$. We further note by Fact (1)(ii) that, if
$b^{j}_{kk}>0$ for some $k>d$, then any feasible solution $\mathbf{x}$ to (45)
must have $x_{j}=0$. Let $N:=\\{j\in[n]~{}|~{}b^{j}_{kk}>0\text{ for all
}k\in[d]\\}$. Then, Fact (1)(ii) also implies that, for all $j\in N$, $B^{j}$
can be written as:

$\displaystyle B^{j}$ $\displaystyle:=\left[\begin{array}[]{c|c}C^{j}&0\\\
\hline\cr 0&0\end{array}\right],$ (52)

where $C^{j}\in\SS_{+}^{d}$. Hence, we may consider the following inequality,
equivalent to (49):

$\displaystyle\displaystyle\sum_{j\in N}C^{j}x_{j}\preceq~{}\mathbf{I}_{d},$
(53) $\displaystyle\mathbf{x}\in\mathcal{C}.$

Let $\mathcal{F}$ and $\mathcal{G}$ be the sets of maximal feasible vectors
for (45) and (53), respectively. Then, $|\mathcal{F}|=|\mathcal{G}|$ (as
$\mathcal{F}=\\{(\mathbf{x},\mathbf{0}^{[n]\setminus
N}):~{}\mathbf{x}\in\mathcal{G}\\}$ where $\mathbf{0}^{[n]\setminus N}$
denotes a vector of zeros in positions $i\in[n]\setminus N$), while
$|{\mathcal{I}}(\mathcal{F})|\leq|{\mathcal{I}}(\mathcal{G})|+n-|N|$ (as
${\mathcal{I}}(\mathcal{F})=\\{(\mathbf{x},\mathbf{0}^{[n]\setminus
N}):~{}x\in{\mathcal{I}}(\mathcal{G})\\}\cup\\{\mathbf{1}_{i}:~{}i\in[N]\setminus[n]\\}$).

We will use the following fact, which is a generalization of Fact 1.

######  Fact 3 (see, e.g., [Mat02]).

Let $p_{1},\ldots,p_{m}~{}:~{}\mathbb{R}^{d}\to\mathbb{R}$ be real polynomials
of maximum degree $D$, and denote by
$Z_{i}:=\\{\mathbf{x}\in\mathbb{R}^{d}~{}|~{}p_{i}(\mathbf{x})=0\\}$ the zero
set of $p_{i}$. Then the number of cells (and, in fact, all the faces) in the
arrangement of the surfaces $Z_{1},\ldots,Z_{m}$ is at most
$\Psi_{d,D}(m):=2(2D)^{d}\sum_{i=0}^{d}2^{i}\binom{4m+1}{i}$, which is bounded
by $\left(\frac{50Dm}{d}\right)^{d}$, for$m\geq d\geq 2$.

######  Theorem 9.

Let $\mathcal{F}$ be the set of maximal feasible vectors for (45). Then for
any non-empty subset $\mathcal{F}^{\prime}\subseteq\mathcal{F}$, it holds that

$\displaystyle|{\mathcal{I}}(\mathcal{F}^{\prime})\cap{\mathcal{I}}(\mathcal{F})|\leq\Psi_{d,2}(n(n-1)/2)n|\mathcal{F}^{\prime}|=O(n)^{2d+1}|\mathcal{F}^{\prime}|,$
(54)

where $d:=\operatorname{rank}(T)$.

###### Proof.

By the argument preceding the theorem, we may consider the equivalent
inequality (53). Indeed, if we show the bound
$|{\mathcal{I}}(\mathcal{G}^{\prime})\cap{\mathcal{I}}(\mathcal{G})|\leq\sum_{i=1}^{r}\Psi_{d}(|N|(|N|-1)/2)|N|\cdot|\mathcal{G}^{\prime}|$
for any $\mathcal{G}^{\prime}\subseteq\mathcal{G}$, we get, for
$\mathcal{F}^{\prime}=\\{(\mathbf{x},\mathbf{0}^{[n]\setminus
N}):~{}\mathbf{x}\in\mathcal{G}^{\prime}\\}$,

$\displaystyle|{\mathcal{I}}(\mathcal{F}^{\prime})\cap{\mathcal{I}}(\mathcal{F})|\leq\Psi_{d,2}(|N|(|N|-1)/2)|N|\cdot|\mathcal{G}^{\prime}|+n-|N|\leq\Psi_{d,2}(n(n-1)/2)n|\mathcal{F}^{\prime}|.$

Thus, for simplicity we will consider (45) and assume w.l.o.g. in the
following that $N=[n]$, $T=\mathbf{I}_{d}$ (and hence, $d=m$).

To show (54), we proceed in a way similar to the proof of Theorem 8. Denoting
by $\mathbb{B}^{d}(0,1):=\\{\mathbf{x}\in\mathbb{R}^{d}:~{}\|\mathbf{x}\|\leq
1\\}$ the $d$-dimensional unit ball centered at the origin, we can rewrite
(45) in the following equivalent form:

$\displaystyle\displaystyle
f_{\mathbf{u},i}(\mathbf{x}):=\sum_{j=1}^{n}(A^{i,j}\bullet\mathbf{u}\mathbf{u}^{\top})x_{j}\leq~{}1,\quad\text{
for }\mathbf{u}\in\mathbb{B}^{d}(0,1).$ (55)

For $\mathbf{u}\in\mathbb{B}^{d}(0,1)$, let
$\mathbf{w}^{\mathbf{u},i}\in\mathbb{R}^{n}_{+}$ be the vector whoso $j$th
component is $w_{j}:=A^{j}\bullet\mathbf{u}\mathbf{u}^{\top}$, and
$\mathcal{F}_{\mathbf{u}}$ be the set of maximal feasible solutions for the
inequality
$f_{\mathbf{u}}(\mathbf{x})=(\mathbf{w}^{\mathbf{u}})^{\top}\mathbf{x}\leq 1$.
Then, as in the proof of Theorem 8, it is enough to bound the number of of
distinct permutations defined by the set of weights
$\\{\mathbf{w}^{\mathbf{u}}~{}|~{}\mathbf{u}\in\mathbb{B}^{d}(0,1)\\}$:

$\displaystyle|\\{\sigma_{\mathbf{w}^{\mathbf{u}}}~{}|~{}\mathbf{u}\in\mathbb{B}^{d}(0,1)\\}|\leq\Psi_{d,2}(n(n-1)/2).$
(56)

Consider the system of inequalities $w_{j}\leq w_{j^{\prime}}$ for
$j,j^{\prime}\in[n]$ (considering $\mathbf{u}$ as a variable in
$\mathbb{R}^{d}$):

$\displaystyle\left(A_{j}-A_{j^{\prime}}\right)\bullet\mathbf{u}\mathbf{u}^{\top}\leq
0,\quad\text{ for }j\neq j^{\prime}\in[n].$ (57)

The inequality-defining polynomials in (57) form an arrangement satisfying the
conditions in Fact 3 with $D:=2$ and $m:=n(n+1)/2$,and hence partitions
$\mathbb{R}^{d}$ into $\Psi_{d,2}(n(n-1)/2)$ cells. The theorem follows. ∎

##  8 Some Open Questions

We conclude with some open questions that naturally arise from the preceding
work:

  * (O1)

For a polynomial inequity (5), where the function $f$ is of the form (2), can
we show a dual bound of the form
$q(\mathcal{L},|\mathcal{F}^{\prime}|)=\operatorname{poly}(n,|\mathcal{H}-i|,|\mathcal{F}^{\prime}|,d)$,
independent of $t$, $R$ and polynomial in $d:=\max_{H,J}d_{H,j}$ (in
comparison to the bound in (36))?

  * (O2)

For a single linear inequality of the form (5), it is known that all maximal
feasible solutions can be enumerated in polynomial time [BEG+02, Cra87, PS94].
If $f$ is a polynomial of constant degree, then (B3) implies that all maximal
feasible solutions can be enumerated in quasi-polynomial time via a dual-
boundedness argument. It remains open whether a polynomial-time enumeration
algorithm exists for a single polynomial inequality with fixed degree.

  * (O3)

For a SOC inequity of the form (38), can one show a dual bound of the form
$q(\mathcal{L},|\mathcal{F}^{\prime}|)=\operatorname{poly}(n,d,|\mathcal{F}^{\prime}|)$,
as opposed to the bound in Theorem 8 that depends exponentially on $d$?

  * (O4)

Is there a polynomial time algorithm for enumerating all maximal feasible
solutions for a single SOC inequity (38),when the number of rows $d$ is fixed
(in comparison to a quasi-polynomial time algorithm that we currently know)?

  * (O5)

Similar questions as (O3) and (O4) arise for a PSD inequality of the form
(45), considering the rank $d$ of the matrix $T$ as a parameter that can be
either fixed or a part of the input.

## References

  * [AW02] R. Ahlswede and A. Winter.  Strong converse for identification via quantum channels.  IEEE Transactions on Information Theory, 48(3):569–579, 2002.
  * [BEG+02] E. Boros, K. Elbassioni, V. Gurvich, L. Khachiyan, and K. Makino.  Dual-bounded generating problems: All minimal integer solutions for a monotone system of linear inequalities.  SIAM Journal on Computing, 31(5):1624–1643, 2002.
  * [BEGK03] E. Boros, K. Elbassioni, V. Gurvich, and L. Khachiyan.  An inequality for polymatroid functions and its applications.  Discrete Applied Mathematics, 131:255–281, 2003.
  * [BGKM00] E. Boros, V. Gurvich, L. Khachiyan, and K. Makino.  Dual-bounded generating problems: Partial and multiple transversals of a hypergraph.  SIAM J. Comput., 30(6):2036–2050, 2000.
  * [BGKM01] E. Boros, V. Gurvich, L. Khachiyan, and K. Makino.  Dual-bounded generating problems: Partial and multiple transversals of a hypergraph.  SIAM Journal on Computing, 30(6):2036–2050, 2001.
  * [BGKM04] E. Boros, V. Gurvich, L. Khachiyan, and K. Makino.  Dual-bounded generating problems: weighted transversals of a hypergraph.  Discret. Appl. Math., 142(1-3):1–15, 2004.
  * [BI95] J. C. Bioch and T. Ibaraki.  Complexity of identification and dualization of positive boolean functions.  Information and Computation, 123(1):50–63, 1995.
  * [Bud88] L. Budach.  Algebraic and Topological Properties of Finite Partially Ordered Sets.  Teubner-Texte zur Mathematik. B.G. Teubner, 1988.
  * [Cra87] Y. Crama.  Dualization of regular boolean functions.  Discrete Applied Mathematics, 16(1):79–85, 1987.
  * [FK96] M. L. Fredman and L. Khachiyan.  On the complexity of dualization of monotone disjunctive normal forms.  Journal of Algorithms, 21:618–628, 1996.
  * [GK99] V. Gurvich and L. Khachiyan.  On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions.  Discrete Applied Mathematics, 96-97(1):363–373, 1999.
  * [HJ90] R. A. Horn and C. R. Johnson.  Matrix analysis.  Cambridge University Press, 1990.
  * [KBE+07] L. Khachiyan, E. Boros, K. Elbassioni, V. Gurvich, and K. Makino.  Dual-bounded generating problems: Efficient and inefficient points for discrete probability distributions and sparse boxes for multidimensional data.  Theor. Comput. Sci., 379(3):361–376, 2007.
  * [Lov83] L. Lovasz.  Submodular functions and convexity.  In M. Grotschel A. Bachem and B. Korte, editors, Mathematical Programming: The State of the Art, pages 235–257, New York, 1983. Springer-Verlag.
  * [Mat02] J. Matousek.  Lectures on Discrete Geometry.  Springer-Verlag, Berlin, Heidelberg, 2002.
  * [PS94] U. N. Peled and B. Simeone.  An $o(nm)$-time algorithm for computing the dual of a regular boolean function.  Discrete Applied Mathematics, 49(1-3):309–323, 1994.
  * [WX08] A. Wigderson and D. Xiao.  Derandomizing the ahlswede-winter matrix-valued chernoff bound using pessimistic estimators, and applications.  Theory Comput., 4(1):53–76, 2008.
  * [Yüc02] Ü. Yüceer.  Discrete convexity: convexity for functions defined on discrete spaces.  Discret. Appl. Math., 119(3):297–304, 2002.

##  Appendix A Omitted Proofs

###### Proof of Proposition 1.

Suppose that $f$ is supermodular. Consider $j\in[k]$,
$z\in\mathcal{C}_{j}\setminus\\{c_{j}\\}$, and
$\mathbf{x}^{\prime},\mathbf{x}^{\prime\prime}\in\mathcal{C}_{1}\times\ldots\times\mathcal{C}_{j-1}\times\\{z\\}\times\mathcal{C}_{j+1}\times\ldots\times\mathcal{C}_{k}$
such that $\mathbf{x}^{\prime}\leq\mathbf{x}^{\prime\prime}$. To show that
$\partial_{f}(\mathbf{x}^{\prime},j,z)\leq\partial_{f}(\mathbf{x}^{\prime\prime},j,z)$,
we take $\mathbf{x}:=\mathbf{x}^{\prime}\vee\boldsymbol{1}^{j}$ and
$\mathbf{y}:=\mathbf{x}^{\prime\prime}$ in (3) to get

$\displaystyle
f(\mathbf{x}^{\prime\prime}\vee\boldsymbol{1}^{j})+f(\mathbf{x}^{\prime})$
$\displaystyle=f((\mathbf{x}^{\prime}\vee\boldsymbol{1}^{j})\vee\mathbf{x}^{\prime\prime})+f((\mathbf{x}^{\prime}\vee\boldsymbol{1}^{j})\wedge\mathbf{x}^{\prime\prime})$
$\displaystyle\geq
f(\mathbf{x}^{\prime}\vee\boldsymbol{1}^{j})+f(\mathbf{x}^{\prime\prime}),$

giving the desired inequality. On the other hand, suppose that
$\partial_{f}(\mathbf{x},j,z)$ is monotone in
$\mathbf{x}\in\mathcal{C}_{1}\times\ldots\times\mathcal{C}_{j-1}\times\\{z\\}\times\mathcal{C}_{j+1}\times\ldots\times\mathcal{C}_{k}$,
for any $j\in[n]$ and $z\in\mathcal{C}_{j}\setminus\\{c_{j}\\}$. Consider
$\mathbf{x},\mathbf{y}\in\mathcal{C}$. We need to show that (3) holds. Let
$S(\mathbf{x},\mathbf{y}):=\\{j\in[k]:~{}x_{j}>y_{j}\\}$. The proof is by
induction on the size of $S(\mathbf{x},\mathbf{y})$. If
$S(\mathbf{x},\mathbf{y})=\emptyset$ (meaning that $\mathbf{x}\leq\mathbf{y}$)
then (3) holds as an equality and there is nothing to prove. Otherwise, taking
any $j\in S(\mathbf{x},\mathbf{y})$ and using montonicity of
$\partial_{f}(\cdot,j,z)$ for
$z:=(\mathbf{x}\wedge\mathbf{y})_{j}+(\ell-1)\boldsymbol{1}^{j}=y_{j}+(\ell-1)\boldsymbol{1}^{j}$
and $\ell\in\\{1,\ldots,x_{j}-y_{j}\\}$, we obtain

$\displaystyle
f(\mathbf{y}+\ell\boldsymbol{1}^{j})-f(\mathbf{y}+(\ell-1)\boldsymbol{1}^{j})\geq
f(\mathbf{x}\wedge\mathbf{y}+\ell\boldsymbol{1}^{j})-f(\mathbf{x}\wedge\mathbf{y}+(\ell-1)\boldsymbol{1}^{j}).$
(58)

Summing (58) over all $\ell\in\\{1,\ldots,x_{j}-y_{j}\\}$, we get

$\displaystyle f(\mathbf{y}^{\prime})-f(\mathbf{y})\geq
f(\mathbf{x}\wedge\mathbf{y}+(x_{j}-y_{j})\boldsymbol{1}^{j})-f(\mathbf{x}\wedge\mathbf{y}).$
(59)

where $\mathbf{y}^{\prime}:=\mathbf{y}+(x_{j}-y_{j})\boldsymbol{1}^{j}$. As
$|S(\mathbf{x},\mathbf{y}^{\prime})|<S(\mathbf{x},\mathbf{y})|$, we get by
induction that

$\displaystyle
f(\mathbf{x}\vee\mathbf{y}^{\prime})+f(\mathbf{x}\wedge\mathbf{y}^{\prime})\geq
f(\mathbf{x})+f(\mathbf{y}^{\prime}).$ (60)

Summing (59) and (60) and noting that
$\mathbf{x}\wedge\mathbf{y}+(x_{j}-y_{j})\boldsymbol{1}^{j}=\mathbf{x}\wedge\mathbf{y}^{\prime}$
and $\mathbf{x}\vee\mathbf{y}^{\prime}=\mathbf{x}\vee\mathbf{y}$ yields the
claim. ∎

###### Proof of Lemma 5(ii).

The proof is by induction on $|U|\geq 1$ with the base case, $|U|=1$, being
trivial.

For $u\in U$, let $\mathcal{S}(u):=\\{S\in\mathcal{S}:~{}u\in S\\}$ and
$\mathcal{T}(u):=\\{T\in\mathcal{T}:~{}u\in T\\}$. Let $U_{1}:=\\{u\in
U~{}:~{}|\mathcal{S}(u)|\leq 1\\}$ and $U_{2}=U\setminus U_{1}$. We may assume
without loss of generality that $|\mathcal{T}(u)|=0$ for all $u\in U_{1}$.

For any $u\in U_{2}$, letting $U^{\prime}(u):=U\setminus\\{u\\}$,
$\mathcal{S}^{\prime}(u):=\\{S\setminus\\{u\\}:~{}S\in\mathcal{S}(u)\\}$ and
$\mathcal{T}^{\prime}(u):=\\{T\setminus\\{u\\}:~{}T\in\mathcal{T}(u)\\}$, the
sets $\mathcal{S}^{\prime}(u)$ and $\mathcal{T}^{\prime}(u)$ satisfy the
preconditions of the lemma with respect to the weight function
$w:U^{\prime}(u)\to\mathbb{R}_{+}$ and thresholds $t_{1}^{\prime}:=t_{1}-w(u)$
and $t_{2}^{\prime}:=t_{2}-w(u)$. Thus, we get by induction that

$\displaystyle|\mathcal{S}(u)|=|\mathcal{S}^{\prime}(u)|\leq\frac{w(U^{\prime}(u))-t_{1}^{\prime}}{t_{2}^{\prime}-t_{1}^{\prime}}|\mathcal{T}^{\prime}(u)|=\frac{w(U)-t_{1}}{t_{2}-t_{1}}|\mathcal{T}(u)|.$
(61)

Let $\alpha=\max_{T\in\mathcal{T}}w(T)$. Then $w(U_{1})\leq w(U)-\alpha$.
Multiplying both sides of (61) by $w(u)$ and summing up the resulting
inequalities over $u\in U_{2}$, we get by the threshold separability of
$\mathcal{S}$ and $\mathcal{T}$

$\displaystyle t_{2}|\mathcal{S}|\leq\sum_{S\in\mathcal{S}}w(S)$
$\displaystyle\leq w(U_{1})+\sum_{u\in U_{2}}w(u)|\mathcal{S}(u)|\leq
w(U_{1})+\sum_{u\in U_{2}}w(u)\frac{w(U)-t_{1}}{t_{2}-t_{1}}|\mathcal{T}(u)|$
$\displaystyle=w(U_{1})+\frac{w(U)-t_{1}}{t_{2}-t_{1}}\sum_{T\in\mathcal{T}}w(T)\leq
w(U_{1})+\frac{w(U)-t_{1}}{t_{2}-t_{1}}\alpha|\mathcal{T}|$ $\displaystyle\leq
w(U)-\alpha+\frac{w(U)-t_{1}}{t_{2}-t_{1}}\alpha|\mathcal{T}|,$ (62)

where $\alpha\leq t_{1}$. Note that the right hand side of (A) is monotone
increasing in $\alpha$ and hence is maximized at $\alpha=t_{1}$. It follows
that

$\displaystyle|\mathcal{S}|\leq\frac{w(U)-t_{1}}{t_{2}}+\frac{w(U)-t_{1}}{t_{2}-t_{1}}\cdot\frac{t_{1}}{t_{2}}|\mathcal{T}|.$
(63)

Using $t_{1}<t_{2}$ in (63), we obtain the stated claim. ∎

###### Proof of Lemma 7.

For a vector $\mathbf{x}\in\mathcal{C}\setminus\\{\mathbf{0}\\}$ let us denote
by $j^{\mathbf{x}}_{i}$ the index of the last component, in the order given by
$\sigma_{i}$, which is larger than $0$, i.e.,
$j_{i}^{\mathbf{x}}=\max\\{j\in[n]~{}|~{}x_{\sigma_{i}(j)}>0\\}$. For a vector
$\mathbf{y}\in\mathcal{C}$ and a permutation $\sigma$, denote by
$\mathbf{y}^{\sigma,j}$ the vector $\mathbf{y}^{\prime}$ with components:

$y^{\prime}_{\sigma(j^{\prime})}=\left\\{\begin{array}[]{ll}y_{\sigma(j^{\prime})}&\text{
for }j^{\prime}<j,\\\ y_{\sigma_{i}(j^{\prime})}+1&\text{ for
}j^{\prime}=j,\\\ 0&\text{ otherwise}.\end{array}\right.$ (64)

Let $\mathcal{F}_{i}$ be the set of maximal feasible solutions of the
inequality $f_{i}(\mathbf{x})\leq t_{i}$. We claim that for every
$\mathbf{x}\in\mathcal{X}:={\mathcal{I}}(\mathcal{F}^{\prime})\cap{\mathcal{I}}(\mathcal{F})$
there exists an $i\in[r]$ and a $\mathbf{y}\in\mathcal{F}^{\prime}$ such that
$\mathbf{x}=\mathbf{y}^{\sigma_{i},j^{\mathbf{x}}_{i}}$. To see this claim,
let us consider
$\mathbf{x}\in{\mathcal{I}}(\mathcal{F}^{\prime})\cap{\mathcal{I}}(\mathcal{F})$
and observe that $\mathbf{x}\neq\mathbf{0}$ because
$\mathbf{x}\in{\mathcal{I}}(\mathcal{F})$ and $\mathcal{F}\neq\emptyset$. As
${\mathcal{I}}(\mathcal{F}^{\prime})\cap{\mathcal{I}}(\mathcal{F})=\bigcup_{i=1}^{r}\left({\mathcal{I}}(\mathcal{F}^{\prime})\cap{\mathcal{I}}(\mathcal{F}_{i})\right)$,
there exists an $i\in[r]$ such that
$\mathbf{x}\in\mathcal{X}:={\mathcal{I}}(\mathcal{F}^{\prime})\cap{\mathcal{I}}(\mathcal{F}_{i})$.
Let $j:=j_{i}^{\mathbf{x}}$. Then, as
$\mathbf{x}\in{\mathcal{I}}(\mathcal{F}^{\prime})$, there exists a
$\mathbf{y}\in\mathcal{F}^{\prime}$ such that
$\mathbf{y}\geq\mathbf{x}-\mathbf{1}^{j}$. For any $j^{\prime}<j$, we must
have $x_{\sigma_{i}(j^{\prime})}=y_{\sigma_{i}(j^{\prime})}$, since if
$x_{\sigma_{i}(j^{\prime})}<y_{\sigma_{i}(j^{\prime})}$ for some
$j^{\prime}<j$, then $f_{i}(\mathbf{y})\geq
f_{i}(\mathbf{x}+\mathbf{1}^{\sigma_{i}(j^{\prime})}-\mathbf{1}^{\sigma_{i}(j)})\geq
f(\mathbf{x})>t_{i}$ would follow by the 2-monotonicity of $f$, and yielding a
contradiction with $f_{i}(\mathbf{y})\leq t_{i}$ (which follows from
$y\in\mathcal{F}$). Finally, the definition of $j=j^{\mathbf{x}}_{i}$ implies
that $x_{\sigma_{i}(j^{\prime})}=0$ for all $j^{\prime}>j$. Hence, our claim
and the equality (64) follow.

The above claim implies that

$\mathcal{X}\subseteq\\{\mathbf{y}^{\sigma_{i},j}~{}|~{}\mathbf{y}\in\mathcal{F}^{\prime},~{}i\in[r^{\prime}],~{}j\in[n],~{}y_{{\sigma_{i}(j)}}<c_{\sigma_{i}(j)}\\},$

and hence (41) and thus the lemma follow. ∎