# Superpolynomial Lower Bounds for Learning Monotone Classes

Nader H. Bshouty
Dept. of Computer Science, Technion, Haifa, Israel.111 Center for Theoretical
Sciences, Guangdong Technion, (GTIIT), China.
<EMAIL_ADDRESS>
###### Abstract

Koch, Strassle, and Tan [SODA 2023], show that, under the randomized
exponential time hypothesis, there is no distribution-free PAC-learning
algorithm that runs in time $n^{\tilde{O}(\log\log s)}$ for the classes of
$n$-variable size-$s$ DNF, size-$s$ Decision Tree, and $\log s$-Junta by DNF
(that returns a DNF hypothesis). Assuming a natural conjecture on the hardness
of set cover, they give the lower bound $n^{\Omega(\log s)}$. This matches the
best known upper bound for $n$-variable size-$s$ Decision Tree, and $\log
s$-Junta.

In this paper, we give the same lower bounds for PAC-learning of $n$-variable
size-$s$ Monotone DNF, size-$s$ Monotone Decision Tree, and Monotone $\log
s$-Junta by DNF. This solves the open problem proposed by Koch, Strassle, and
Tan and subsumes the above results.

The lower bound holds, even if the learner knows the distribution, can draw a
sample according to the distribution in polynomial time, and can compute the
target function on all the points of the support of the distribution in
polynomial time.

##  1 Introduction

In the distribution-free PAC learning model [12], the learning algorithm of a
class of functions $C$ has access to an unknown target function $f\in C$
through labeled examples $(x,f(x))$ where $x$ are drawn according to an
unknown but fixed probability distribution ${\cal D}$. For a class of
hypothesis $H\supseteq C$, we say that the learning algorithm ${\cal A}$ PAC-
learns $C$ by $H$ in time $T$ and error $\epsilon$ if for every target $f\in
C$ and distribution ${\cal D}$, ${\cal A}$ runs in time $T$ and outputs a
hypothesis $h\in H$ which, with probability at least $2/3$, is
$\epsilon$-close to $f$ with respect to ${\cal D}$. That is, satisfies ${\bf
Pr}_{\boldsymbol{x}\sim{\cal
D}}[f(\boldsymbol{x})\not=h(\boldsymbol{x})]\leq\epsilon$.

Koch et al., [9], show that, under the randomized exponential time hypothesis
(ETH), there is no PAC-learning algorithm that runs in time
$n^{\tilde{O}(\log\log s)}$ for the classes of $n$-variable size-$s$ DNF,
size-$s$ Decision Tree and $\log s$-Junta by DNF. Assuming a natural
conjecture on the hardness of set cover, they give the lower bound
$n^{\Omega(\log s)}$. Their lower bound holds, even if the learner knows the
distribution, can draw a sample according to the distribution in polynomial
time and can compute the target function on all the points of the support of
the distribution in polynomial time.

In this paper, we give the same lower bounds for PAC-learning of the classes
$n$-variable size-$s$ Monotone DNF, size-$s$ Monotone Decision Tree and
Monotone $\log s$-Junta by DNF. This solves the open problem proposed by Koch,
Strassle, and Tan [9].

###  1.1 Our Results

In this paper, we prove the following three Theorems.

Theorem 1. Assuming randomized ETH, there is a constant $c$ such that any PAC
learning algorithm for $n$-variable Monotone $(\log s)$-Junta, size-$s$
Monotone DT and size-$s$ Monotone DNF by DNF with $\epsilon=1/(16n)$ must take
at least

$n^{c\frac{\log\log s}{\log\log\log s}}$

time.

Theorem 2. Assuming a plausible conjecture on the hardness of Set-Cover 222See
Conjecture 1., there is a constant $c$ such that any PAC learning algorithm
for $n$-variable Monotone $(\log s)$-Junta, size-$s$ Monotone DT and size-$s$
Monotone DNF by DNF with $\epsilon=1/(16n)$ must take at least

$n^{c\log s}$

time.

Theorem 3. Assuming randomized ETH, there is a constant $c$ such that any PAC
learning algorithm for $n$-variable Monotone $(\log s)$-Junta, size-$s$
Monotone DT and size-$s$ Monotone DNF by size-$s$ DNF with $\epsilon=1/(16n)$
must take at least

$n^{c\log s}$

time.

All the above lower bound holds, even if the learner knows the distribution,
can draw a sample according to the distribution in polynomial time and can
compute the target on all the points of the support of the distribution in
polynomial time.

In the following two subsections, we give the technique used in [9] to prove
Theorem 1 for $(\log s)$-Junta, and the technique we use here to extend the
result to Monotone $(\log s)$-Junta.

###  1.2 Previous Technique

In [9], Koch, Strassle, and Tan show that under the randomized exponential
time hypothesis, there is no PAC-learning algorithm that runs in time
$n^{\tilde{O}(\log\log n)}$ for the class of $\log n$-Junta333$k$-Junta are
Boolean functions that depend on at most $k$ variables by DNF. The results for
the other classes follow immediately from this result, since all other classes
contain $\log n$-Junta. All prior works [1, 5] ruled out only $poly(n)$ time
algorithms.

The result in [9] uses the hardness result of $(k,k^{\prime})$-Set-Cover where
one needs to distinguish between instances that have set cover of size at most
$k$ from instances that have minimum-size set cover greater than $k^{\prime}$:

  1. 1.

For some parameters $k$ and $k^{\prime}$, assuming randomized ETH, there is a
constant $\lambda<1$ such that $(k,k^{\prime})$-Set-Cover cannot be solved in
time $n^{\lambda k}$.

First, for each set cover instance ${\cal S}$, they identify each element in
the universe with an assignment in $\\{0,1\\}^{n}$ and construct in polynomial
time a target function $\Gamma^{\cal S}:\\{0,1\\}^{n}\to\\{0,1\\}$ and a
distribution ${\cal D}^{\cal S}$ that satisfies:

  1. 2.

The instance ${\cal S}$ has minimum-size set cover ${\rm opt}({\cal S})$ if
and only if the function $\Gamma^{\cal S}$ is a conjunction of ${\rm
opt}({\cal S})$ unnegated variables444Their reduction gives a conjunction of
negated variable. So here, we are referring to the dual function. over the
distribution ${\cal D}^{\cal S}$.555That is, there is a term $T$ with ${\rm
opt}({\cal S})$ variables such that for every $x$ in the support of ${\cal
D}^{\cal S}$, $\Gamma^{\cal S}(x)=T(x)$.

For a DNF $F$ and $x\in\\{0,1\\}^{n}$, they define $0pt_{F}(x)$ to be the size
of the smallest term $T$ in $F$ that satisfies $T(x)=1$. They then show that

  1. 3.

Any DNF $F$ with expected width ${\bf E}_{\boldsymbol{x}\sim{\cal D}^{\cal
S}}[0pt_{F}(\boldsymbol{x})]\leq{\rm opt}({\cal S})/2$ is $(1/(2N))$-far from
$\Gamma^{\cal S}$ with respect to ${\cal D}^{\cal S}$ where $N$ is the
size666$N$ is the number of sets plus the size of the universe in ${\cal S}$.
of ${\cal S}$. That is, ${\bf Pr}_{\boldsymbol{x}\sim{\cal D}^{\cal
S}}[F(\boldsymbol{x})\not=\Gamma^{\cal S}(\boldsymbol{x})]\geq 1/(2N)$.

They then use the following gap amplification technique. They define the
function $\Gamma^{\cal S}_{\oplus\ell}:(\\{0,1\\}^{\ell})^{n}\to\\{0,1\\}$
where for $y=(y_{1},\ldots,y_{n})$,
$y_{i}=(y_{i,1},\ldots,y_{i,\ell})\in\\{0,1\\}^{\ell}$, $i\in[n]$, we have
$\Gamma^{\cal S}_{\oplus\ell}(y)=\Gamma^{\cal S}(\oplus y_{1},\ldots,\oplus
y_{n})$ and $\oplus y_{i}=y_{i,1}+\cdots+y_{i,\ell}$. They also extend the
distribution ${\cal D}^{\cal S}$ to a distribution ${\cal D}^{\cal
S}_{\oplus\ell}$ over domain $(\\{0,1\\}^{\ell})^{n}$ and prove that

  1. 4.

$\Gamma^{\cal S}_{\oplus\ell}(y)$ is a $({\rm opt}({\cal S})\ell)$-Junta over
${\cal D}^{\cal S}_{\oplus\ell}$.

  2. 5.

Any DNF formula $F$ with expected depth ${\bf E}_{\boldsymbol{y}\sim{\cal
D}^{\cal S}_{\oplus\ell}}[0pt_{F}(\boldsymbol{y})]\leq{\rm opt}({\cal
S})\ell/4$ is $(1/(4N))$-far from $\Gamma^{\cal S}_{\oplus\ell}$ with respect
to ${\cal D}_{\oplus\ell}^{\cal S}$.

Item 4 follows from the definition of $\Gamma^{\cal S}_{\oplus\ell}$ and item
2. To prove Item 5, they show that if, to the contrary, there is a DNF $F$ of
expected width at most ${\rm opt}({\cal S})\ell/4$ that is $1/(4N)$-close to
$\Gamma^{\cal S}_{\oplus\ell}$ with respect to ${\cal D}_{\oplus\ell}^{\cal
S}$, then there is $j\in[\ell]$ and a projection of all the variables that are
not of the form $y_{i,j}$ that gives a DNF $F^{*}$ of expected width at most
${\rm opt}({\cal S})/2$ that is $1/(2N)$-close to $\Gamma^{\cal S}$ with
respect to ${\cal D}^{\cal S}$. Then, by item 3, we get a contradiction.

They then show that

  1. 6.

Any size-$s$ DNF that is $(1/(4N))$-close to $\Gamma^{\cal S}_{\oplus\ell}$
with respect to ${\cal D}^{\cal S}_{\oplus\ell}$ has average width ${\bf
E}_{\boldsymbol{y}\sim{\cal D}^{\cal S}_{\oplus\ell}}$
$[0pt_{F}(\boldsymbol{y})]\leq 4\log s$.

If $F$ is $(1/(4N))$-close to $\Gamma^{\cal S}_{\oplus\ell}$ with respect to
${\cal D}^{\cal S}_{\oplus\ell}$, then, by items 5 and 6, $4\log s\geq{\bf
E}_{\boldsymbol{y}\sim{\cal D}^{\cal S}_{\oplus\ell}}$
$[0pt_{F}(\boldsymbol{y})]\geq{\rm opt}({\cal S})\ell/4$ and then $s\geq
2^{{\rm opt}({\cal S})\ell/16}$. Therefore,

  1. 7.

Any DNF of size less than $2^{{\rm opt}({\cal S})\ell/16}$ is $(1/(4N))$-far
from $\Gamma^{\cal S}_{\oplus\ell}$ with respect to ${\cal
D}_{\oplus\ell}^{\cal S}$.

Now, let $k=\tilde{O}(\log\log n)$. Suppose, to the contrary, that there is a
PAC-learning algorithm for $\log n$-Junta by DNF with error $\epsilon=1/(8N)$
that runs in time $t=n^{\lambda k/2}=n^{\tilde{O}(\log\log n)}$, where
$\lambda$ is the constant in item 1. Given a $(k,k^{\prime})$-Set-Cover
instance, we run the learning algorithm for $\Gamma^{\cal S}_{\oplus\ell}$ for
$\ell=\log n/k$. If the instance has set cover at most $k$, then by item 4,
$\Gamma^{\cal S}_{\oplus\ell}$ is $\log n$-Junta. Then the algorithm learns
the target and outputs a hypothesis that is $(1/(8N))$-close to
$\Gamma_{\oplus\ell}^{\cal S}$ with respect to ${\cal D}^{\cal
S}_{\oplus\ell}$.

On the other hand, if the instance has a minimum-size set cover of at least
$k^{\prime}$, then any learning algorithm that runs in time $t=n^{\lambda
k/2}=n^{\tilde{O}(\log\log n)}$ cannot output a DNF of size more than $t$
terms. By item 7, any DNF of size less than $2^{k^{\prime}\log n/(16k)}\leq
2^{{\rm opt}({\cal S})\ell/16}$ is $(1/(4N))$-far from $\Gamma^{\cal
S}_{\oplus\ell}$ with respect to ${\cal D}^{\cal S}_{\oplus\ell}$. By choosing
the right parameters $k$ and $k^{\prime}$, we have $2^{k^{\prime}\log
n/(16k)}>t$, and therefore, any DNF that the algorithm outputs has error of at
least $1/(4N)$.

Therefore, by estimating the distance of the output of the learning algorithm
from $\Gamma_{\oplus\ell}^{\cal S}$ with respect to ${\cal
D}_{\oplus\ell}^{\cal S}$, we can distinguish between instances that have set
cover of size less than or equal to $k$ from instances that have a minimum-
size set cover greater than $k^{\prime}$ in time $t=n^{\lambda k/2}$. Thus, we
got an algorithm for $(k,k^{\prime})$-Set-Cover that runs in time $n^{\lambda
k/2}<n^{\lambda k}$. This contradicts item 1 and finishes the proof of the
first lower bound.

Assuming a natural conjecture on the hardness of set cover, they give the
lower bound $n^{\Omega(\log s)}$. We will discuss this in Section 5.

###  1.3 Our Technique

In this paper, we also use the hardness result of $(k,k^{\prime})$-Set-Cover .
As in [9], we identify each element in the universe with an assignment in
$\\{0,1\\}^{n}$ and use the function $\Gamma^{\cal S}$ and the distribution
${\cal D}^{\cal S}$ that satisfies:

  1. 1.

The instance ${\cal S}$ has minimum-size set cover ${\rm opt}({\cal S})$ if
and only if the function $\Gamma^{\cal S}$ is a conjunction of ${\rm
opt}({\cal S})$ variables over the distribution ${\cal D}^{\cal S}$.

We then build a monotone target function $\Gamma^{\cal S}_{\ell}$ and use a
different approach to show that any DNF of size less than $2^{{\rm opt}({\cal
S})\ell/20}$ is $(1/(8N)-2^{-{\rm opt}({\cal S})\ell/20})$-far from
$\Gamma^{\cal S}_{\ell}$ with respect to ${\cal D}^{\cal S}_{\ell}$.

We define, for any odd $\ell$, the monotone function $\Gamma^{\cal
S}_{\ell}:(\\{0,1\\}^{\ell})^{n}\to\\{0,1\\}$ where for
$y=(y_{1},\ldots,y_{n})$, $y_{i}=(y_{i,1},\ldots,y_{i,\ell})$ we have
$\Gamma^{\cal S}_{\ell}(y)=\Gamma^{\cal
S}({\textsc{Majority}}(y_{1}),\ldots,{\textsc{Majority}}(y_{n}))$ where
Majority is the majority function. A distribution ${\cal D}^{\cal S}_{\ell}$
is also defined such that

  1. 2.

${\bf Pr}_{\boldsymbol{y}\sim{\cal D}_{\ell}^{\cal S}}[\Gamma_{\ell}^{\cal
S}(\boldsymbol{y})=0]={\bf Pr}_{\boldsymbol{y}\sim{\cal D}_{\ell}^{\cal
S}}[\Gamma_{\ell}^{\cal S}(\boldsymbol{y})=1]=1/2$.

It is clear from the definition of $\Gamma^{\cal S}_{\ell}$ and item 1 that

  1. 3.

$\Gamma^{\cal S}_{\ell}(y)$ is a monotone $({\rm opt}({\cal S})\ell)$-Junta
over ${\cal D}^{\cal S}_{\ell}$.

We then define the monotone size of a term $T$ to be the number of unnegated
variables that appear in $T$. We first show that

  1. 4.

For every DNF $F:(\\{0,1\\}^{\ell})^{n}\to\\{0,1\\}$ of size $|F|\leq 2^{{\rm
opt}({\cal S})\ell/5}$ that is $\epsilon$-far from $\Gamma^{\cal S}_{\ell}$
with respect to ${\cal D}_{\ell}^{\cal S}$, there is another DNF $F^{\prime}$
of size $|F^{\prime}|\leq 2^{{\rm opt}({\cal S})\ell/5}$ with terms of
monotone size at most ${\rm opt}({\cal S})\ell/5$ that is $(\epsilon-2^{-{\rm
opt}({\cal S})\ell/20})$-far from $\Gamma_{\ell}^{\cal S}$ with respect to
${\cal D}_{\ell}^{\cal S}$.

This is done by simply showing that terms of large monotone size in the DNF
$F$ have a small weight according to the distribution ${\cal D}_{\ell}^{\cal
S}$ and, therefore, can be removed from $F$ with the cost of $-2^{-{\rm
opt}({\cal S})\ell/20}$ in the error.

We then, roughly speaking, show that

  1. 5.

Let $F^{\prime}$ be a DNF of size $|F^{\prime}|\leq 2^{{\rm opt}({\cal
S})\ell/5}$ with terms of monotone size at most ${\rm opt}({\cal S})\ell/5$.
For every $y\in(\\{0,1\\}^{\ell})^{n}$ in the support of ${\cal
D}_{\ell}^{\cal S}$ that satisfies $\Gamma_{\ell}^{\cal S}(y)=1$, either

     * •

$F^{\prime}(y)=0$ or

     * •

$F^{\prime}(y)=1$, and at least $1/(2N)$ fraction of the points $z$ below $y$
in the lattice $(\\{0,1\\}^{\ell})^{n}$ that are in the support of ${\cal
D}_{\ell}^{\cal S}$ satisfies $F^{\prime}(z)=1$ and $\Gamma_{\ell}^{\cal
S}(z)=0$.

By item 5, either $1/(4N)$ fraction of the vectors $y$ that satisfy
$\Gamma_{\ell}^{\cal S}(y)=1$ satisfy $F^{\prime}(y)=0$ or
$(1-1/(4N))/(2N)>1/(4N)$ fraction of the points $z$ that satisfy
$\Gamma_{\ell}^{\cal S}(z)=0$ satisfy $F^{\prime}(z)=1$. Therefore, with item
2, we get that $F^{\prime}$ is $1/(8N)$-far from $\Gamma^{\cal S}_{\ell}$ with
respect to ${\cal D}_{\ell}^{\cal S}$. This, with item 4, implies that

  1. 6.

If $F:(\\{0,1\\}^{\ell})^{n}\to\\{0,1\\}$ is a DNF of size $|F|<2^{{\rm
opt}({\cal S})\ell/20}$, then $F$ is $(1/(8N)-2^{-{\rm opt}({\cal
S})\ell/20})$-far from $\Gamma^{\cal S}_{\ell}$ with respect to ${\cal
D}^{\cal S}_{\ell}$.

The rest of the proof is almost the same as in [9]. See the discussion in
subsection 1.1 after item 7.

###  1.4 Upper Bounds

The only known distribution-free algorithm for $\log s$-Junta is the trivial
algorithm that, for every set of $m=\log s$ variables
$S=\\{x_{i_{1}},\ldots,x_{i_{m}}\\}$, checks if there is a function that
depends on $S$ and is consistent with the examples. This algorithm takes
$n^{O(\log s)}$ time.

For size-$s$ decision tree and monotone size-$s$ decision tree, the classic
result of Ehrenfeucht and Haussler [4] gives a distribution-free time
algorithm that runs in time $n^{O(\log s)}$ and outputs a decision tree of
size $n^{O(\log s)}$.

The learning algorithm is as follows: Let $T$ be the target decision tree of
size $s$. First, the algorithm guesses the variable at the root of the tree
$T$ and then guesses which subtree of the root has size at most $s/2$. Then,
it recursively constructs the tree of size $s/2$. When it succeeds, it
continues to construct the other subtree.

For size-$s$ DNF and monotone size-$s$ DNF, Hellerstein et al. [6] gave a
distribution-free proper learning algorithm that runs in time
$2^{\tilde{O}(\sqrt{n})}$.

To the best of our knowledge, all the other results in the literature for
learning the above classes are either restricted to the uniform distribution
or use, in addition, a black box queries or returns hypotheses that are not
DNF.

##  2 Definitions and Preliminaries

In this section, we give the definitions and preliminary results that are
needed to prove our results.

###  2.1 Set Cover

Let ${\cal S}=(S,U,E)$ be a bipartite graph on $N=n+|U|$ vertices where
$S=[n]$, and for every $u\in U$, $\deg(u)>0$. We say that $C\subseteq S$ is a
set cover of ${\cal S}$ if every vertex in $U$ is adjacent to some vertex in
$C$. The Set-Cover problem is to find a minimum-size set cover. We denote by
${\rm opt}({\cal S})$ the size of a minimum-size set cover for ${\cal S}$.

We identify each element $u\in U$ with the vector
$(u_{1},\ldots,u_{n})\in\\{0,1\\}^{n}$ where $u_{i}=0$ if and only if
$(i,u)\in E$. We will assume that those vectors are distinct. If there are two
distinct elements $u,u^{\prime}\in U$ that have the same vector, then you can
remove one of them from the graph. This is because every set cover that covers
one of them covers the other.

######  Definition 1.

The $(k,k^{\prime})$-Set-Cover problem is the following: Given as input a set
cover instance ${\cal S}=(S,U,E)$, and parameters $k$ and $k^{\prime}$. Output
Yes if ${\rm opt}({\cal S})\leq k$ and No if ${\rm opt}({\cal S})>k^{\prime}$.

###  2.2 Hardness of Set-Cover

Our results are conditioned on the following randomized exponential time
hypothesis (ETH)

Hypothesis: [2, 3, 7, 8, 11]. There exists a constant $c\in(0,1)$ such that
$3$-SAT on $n$ variables cannot be solved by a randomized algorithm in
$O(2^{cn})$ time with success probability at least $2/3$.

The following is proved in [10]. See also Theorem 7 in [9]

######  Lemma 1.

[10]. Let $k\leq\frac{1}{2}\frac{\log\log N}{\log\log\log N}$ and
$k^{\prime}=\frac{1}{2}\left(\frac{\log N}{\log\log N}\right)^{1/k}$ be two
integers. Assuming randomized ETH, there is a constant $\lambda\in(0,1)$ such
that there is no randomized $N^{\lambda k}$ time algorithm that can solve
$\left(k,k^{\prime}\right)$-Set-Cover on $N$ vertices with high probability.

###  2.3 Concept Classes

For the lattice $\\{0,1\\}^{n}$, and $x,y\in\\{0,1\\}^{n}$, we define the
partial order $x\leq y$ if $x_{i}\leq y_{i}$ for every $i$. When $x\leq y$ and
$x\not=y$, we write $x<y$. If $x<y$, we say that $x$ is below $y$, or $y$ is
above $x$. A Boolean function $f:\\{0,1\\}^{n}\to\\{0,1\\}$ is monotone if,
for every $x\leq y$, we have $f(x)\leq f(y)$. A literal is a variable or
negated variable. A term is a conjunction ($\wedge$) of literals. A clause is
a disjunction ($\vee$) of literals. A monotone term (resp. clause) is a
conjunction (resp. disjunction) of unnegated variables. The size of a term
$T$, $|T|$, is the number of literals in the term $T$. A DNF (resp. CNF) is a
disjunction (resp. conjunction) of terms (resp. clauses). The size $|F|$ of a
DNF (resp. CNF) $F$ is the number of terms (resp. clauses) in $F$. A monotone
DNF (resp. monotone CNF) is a DNF (resp. CNF) with monotone terms (resp.
clauses).

We define the following classes

  1. 1.

size-$s$ DNF and size-$s$ Monotone DNF are the classes of DNF and monotone
DNF, respectively, of size at most $s$.

  2. 2.

size $s$-DT and size-$s$ Monotone DT are the classes of decision trees and
monotone decision trees, respectively, with at most $s$ leaves.

  3. 3.

$k$-Junta and Monotone $k$-Junta are the classes of Boolean functions and
monotone Boolean functions that depend on at most $k$ variables.

It is well known that

$\displaystyle\mbox{{Monotone ($\log s$)-Junta$\subset$ {\rm size}-$s$
Monotone DT }$\subset$ {\rm size}-$s$ {Monotone} DNF }.$ (1)

###  2.4 Functions and Distributions

For any set $R$, we define ${\cal U}(R)$ to be the uniform distribution over
$R$. For a distribution ${\cal D}$ over $\\{0,1\\}^{n}$ and two Boolean
functions $f$ and $g$, we define ${\rm dist}_{\cal D}(f,g)={\bf
Pr}_{\boldsymbol{x}\sim{\cal D}}[f(\boldsymbol{x})\not=g(\boldsymbol{x})]$.
Here, bold letters denote random variables. If ${\rm dist}_{\cal D}(f,g)=0$,
then we say that $f=g$ over ${\cal D}$. For a class of functions $C$, we say
that $f$ is $C$ over ${\cal D}$ if there is a function $g\in C$ such that
$f=g$ over ${\cal D}$.

######  Definition 2.

($\Gamma^{{\cal S}}$ and ${\cal D}^{{\cal S}}$) Let ${\cal S}=(S,U,E)$ be a
set cover instance with $S=[n]$. Recall that we identify each element $u\in U$
with the vector $(u_{1},\ldots,u_{n})\in\\{0,1\\}^{n}$ where $u_{i}=0$ if and
only if $(i,u)\in E$. We define the partial function $\Gamma^{\cal
S}:\\{0,1\\}^{n}\to\\{0,1\\}$ where $\Gamma^{\cal S}(x)=0$ if $x\in U$ and
$\Gamma^{\cal S}(1^{n})=1$. We define the distribution ${\cal D}^{\cal S}$
over $\\{0,1\\}^{n}$ where ${\cal D}^{\cal S}(x)=1/2$ if $x=1^{n}$, ${\cal
D}^{\cal S}(x)=1/(2|U|)$ if $x\in U$, and ${\cal D}^{\cal S}(x)=0$ otherwise.
We will remove the superscript ${\cal S}$ when it is clear from the context
and write $\Gamma$ and ${\cal D}$.

######  Fact 1.

We have

  1. 1.

$C\subseteq S$ is a set cover of ${\cal S}=(S,U,E)$, if and only if
$\Gamma(x)=\bigwedge_{i\in C}x_{i}$ over ${\cal D}$.

  2. 2.

In particular, If $T$ is a monotone term of size $|T|<{\rm opt}({\cal S})$,
then there is $u\in U$ such that $T(u)=1$.

###### Proof.

Let $C$ be a set cover of ${\cal S}$. First, we have $\Gamma(1^{n})=1$. Now,
since $C$ is a set cover, every vertex $u\in U$ is adjacent to some vertex in
$C$. This is equivalent to: for every assignment $u\in U$, there is $i\in C$
such that $u_{i}=0$. Therefore, $\wedge_{i\in C}u_{i}=0$ for all $u\in U$.
Thus, $\Gamma(x)=\bigwedge_{i\in C}x_{i}$ over ${\cal D}$.

The other direction can be easily seen by tracing backward in the above proof.
∎

For an odd $\ell$, define $\Delta^{0}=\\{a\in\\{0,1\\}^{\ell}|{\rm
wt}(a)=\lfloor\ell/2\rfloor\\}$ and $\Delta^{1}=\\{a\in\\{0,1\\}^{\ell}|{\rm
wt}(a)=\lceil\ell/2\rceil\\}$, where ${\rm wt}(a)$ is the Hamming weight of
$a$. Notice that
$|\Delta^{0}|=|\Delta^{1}|={\ell\choose\lfloor\ell/2\rfloor}$.

######  Definition 3.

($\Gamma_{\ell}$, ${\cal D}_{\ell}$, $\Delta^{0}_{n}$ and $\Delta^{1}_{n}$)
For an odd $\ell$, define $\Delta^{1}_{n}=(\Delta^{1})^{n}$ and777Here
$\Delta^{\xi}=\Delta^{0}$ if $\xi=0$ and $\Delta^{1}$ if $\xi=1$.
$\Delta^{0}_{n}:=\cup_{u\in U}\prod_{i=1}^{n}\Delta^{u_{i}}=\cup_{u\in
U}(\Delta^{u_{1}}\times\Delta^{u_{2}}\times\cdots\times\Delta^{u_{n}})$.
Define the distribution ${\cal D}_{\ell}:(\\{0,1\\}^{\ell})^{n}\to[0,1]$ to be
${\cal D}_{\ell}(y)=1/(2|\Delta^{1}_{n}|)=1/(2|\Delta^{1}|^{n})$ if
$y\in\Delta^{1}_{n}$, ${\cal
D}_{\ell}(y)=1/(2|\Delta^{0}_{n}|)=1/(2|U|\cdot|\Delta^{0}|^{n})$ if
$y\in\Delta^{0}_{n}$, and ${\cal D}_{\ell}(y)=0$ otherwise. We define the
partial function $\Gamma_{\ell}$ over the support
$\Delta^{0}_{n}\cup\Delta^{1}_{n}$ of ${\cal D}_{\ell}$ to be $1$ if
$y\in\Delta^{1}_{n}$ and $0$ if $y\in\Delta^{0}_{n}$.

We note here that the distribution ${\cal D}_{\ell}$ is well-defined. This is
because: First, the sum of the distribution of the points in $\Delta_{n}^{1}$
is $1/2$. Second, for two different $u,u^{\prime}\in U$, we have that
$\prod_{i=1}^{n}\Delta^{u_{i}}$ and $\prod_{i=1}^{n}\Delta^{u^{\prime}_{i}}$
are disjoint sets. Therefore, $|\Delta_{n}^{0}|=|U|\cdot|\Delta^{0}|^{n}$, and
therefore, the sum of the distribution of all the points in $\Delta_{n}^{0}$
is half. In particular,

######  Fact 2.

We have $\underset{\ \boldsymbol{y}\sim{\cal D}_{\ell}}{{\bf
Pr}}[\Gamma_{\ell}(\boldsymbol{y})=1]=\underset{\ \boldsymbol{y}\sim{\cal
D}_{\ell}}{{\bf Pr}}[\Gamma_{\ell}(\boldsymbol{y})=0]=\underset{\ {\cal
D}_{\ell}}{{\bf Pr}}[\Delta^{1}_{n}]=\underset{\ {\cal D}_{\ell}}{{\bf
Pr}}[\Delta^{0}_{n}]=\frac{1}{2}.$

For $y\in(\\{0,1\\}^{\ell})^{n}$, we write $y=(y_{1},\ldots,y_{n})$, where
$y_{j}=(y_{j,1},y_{j,2},\ldots,y_{j,\ell})\in\\{0,1\\}^{\ell}$. Let
$({\textsc{Majority}}(y_{i}))_{i\in[n]}=({\textsc{Majority}}(y_{1}),\ldots,{\textsc{Majority}}(y_{n}))$
where Majority is the majority function.

######  Fact 3.

If $C\subseteq S$ is a set cover of ${\cal S}$, then
$\Gamma_{\ell}(y)=\Gamma(({\textsc{Majority}}(y_{i}))_{i\in[n]})=\bigwedge_{i\in
C}{\textsc{Majority}}(y_{i})$ over ${\cal D}$. In particular, $\Gamma_{\ell}$
is Monotone ${\rm opt}({\cal S})\ell$-Junta over ${\cal D}$.

###### Proof.

First notice that ${\textsc{Majority}}(x)=1$ if $x\in\Delta^{1}$ and
${\textsc{Majority}}(x)=0$ if $x\in\Delta^{0}$. Therefore, for
$x\in\Delta^{\xi}$, $\xi\in\\{0,1\\}$ we have ${\textsc{Majority}}(x)=\xi$.

For $y\in\Delta_{n}^{1}=(\Delta^{1})^{n}$,
$({\textsc{Majority}}(y_{i}))_{i\in[n]}=1^{n}$ and
$\Gamma_{\ell}(y)=1=\Gamma(1^{n})$.

For $y\in\Delta^{0}_{n}=\cup_{u\in
U}(\Delta^{u_{1}}\times\Delta^{u_{2}}\times\cdots\times\Delta^{u_{n}})$, there
is $u$ such that
$y\in\Delta^{u_{1}}\times\Delta^{u_{2}}\times\cdots\times\Delta^{u_{n}}$.
Then, $({\textsc{Majority}}(y_{i}))_{i\in[n]}=u$ and
$\Gamma_{\ell}(y)=\Gamma(({\textsc{Majority}}(y_{i}))_{i\in[n]})=\Gamma(u)=0$.
∎

For $t\in[\ell],\xi\in\\{0,1\\}$ and $u\in\\{0,1\\}^{\ell}$, we define
$u^{t\leftarrow\xi}\in\\{0,1\\}^{\ell}$ the vector that satisfies

$u^{t\leftarrow\xi}_{i}=\left\\{\begin{array}[]{ll}u_{i}&i\not=t\\\
\xi&i=t\end{array}\right..$

Let $z\in(\\{0,1\\}^{\ell})^{n}$. For $j\in[\ell]^{n}$ and
$a\in\\{0,1\\}^{n}$, define $z^{j\leftarrow a}=(z_{1}^{j_{1}\leftarrow
a_{1}},\ldots,z_{n}^{j_{n}\leftarrow a_{n}})$. For a set
$V\subseteq\\{0,1\\}^{n}$, we define $z^{j\leftarrow V}=\\{z^{j\leftarrow
v}|v\in V\\}$.

We define ${\rm
one}(z)=\prod_{i=1}^{n}\\{m_{i}|z_{i,m_{i}}=1\\}=\\{m_{1}|z_{1,m_{1}}=1\\}\times\cdots\times\\{m_{n}|z_{n,m_{n}}=1\\}$.

######  Fact 4.

Let $w\in\Delta_{n}^{1}$, $j\in{\rm one}(w)$, and $T$ be a term that satisfies
$T(w)=1$. Then

  1. 1.

$w^{j\leftarrow U}\subseteq\Delta_{n}^{0}$.

  2. 2.

$|w^{j\leftarrow U}|=|U|$.

  3. 3.

If $T^{j}(y_{1,j_{1}},\ldots,y_{n,j_{n}})$ is the conjunction of all the
variables that appear in $T$ of the form $y_{i,j_{i}}$, then $T(w^{j\leftarrow
a})=T^{j}(a)$.

###### Proof.

We first prove item 1. Let $u\in U$ and $i$ be any integer in $[n]$. Since
$w\in\Delta_{n}^{1}$, we have $w_{i}\in\Delta^{1}$. Since $j\in one(w)$, we
have $w_{i,j_{i}}=1$. Therefore, $w_{i}^{j_{i}\leftarrow
u_{i}}\in\Delta^{u_{i}}$ for all $i\in[n]$ and $w^{j\leftarrow
u}\in\prod_{i=1}^{n}\Delta^{u_{i}}$. Thus, $w^{j\leftarrow
u}\in\Delta_{n}^{0}$ for all $u\in U$.

To prove item 2, let $u,u^{\prime}$ be two distinct elements of $U$. There is
$i$ such that $u_{i}\not=u^{\prime}_{i}$. Therefore $w_{i}^{j_{i}\leftarrow
u_{i}}\not=w_{i}^{j_{i}\leftarrow u^{\prime}_{i}}$ and $w^{j\leftarrow
u}\not=w^{j\leftarrow u^{\prime}}$.

We now prove item 3. Let $T^{\prime}$ be the conjunction of all the variables
that appear in $T$ that are not of the form $y_{i,j_{i}}$. Then
$T=T^{\prime}\wedge T^{j}$. Since $T(w)=1$, we have $T^{\prime}(w)=1$. Since
the entries of $w^{j\leftarrow a}$ are equal to those in $w$ on all the
variables that are not of the form $y_{i,j_{i}}$, we have
$T^{\prime}(w^{j\leftarrow a})=1$. Therefore, $T(w^{j\leftarrow
a})=T^{\prime}(w^{j\leftarrow a})\wedge T^{j}(w^{j\leftarrow
a}_{1,j_{1}},\ldots,w^{j\leftarrow a}_{n,j_{n}})=T^{j}(a)$. ∎

We now give a different way of sampling according to the distribution ${\cal
D}_{\ell}$.

######  Fact 5.

Let ${\cal S}$ be a Set-Cover instance. The following is an equivalent way of
sampling from ${\cal D}_{\ell}$.

  1. 1.

Draw $\xi\in\\{0,1\\}$ u.a.r.888Uniformly at random.

  2. 2.

Draw $w\in\Delta^{1}_{n}$ u.a.r.

  3. 3.

If $\xi=1$ then output $y=w$.

  4. 4.

If $\xi=0$ then

    1. (a)

draw $j\in{\rm one}(w)$ u.a.r.

    2. (b)

draw $v\in w^{j\leftarrow U}$ u.a.r.

    3. (c)

output $y=v$.

In particular, for any event $X$,

$\underset{\ \boldsymbol{y}\sim{\cal U}(\Delta_{n}^{0})}{{\bf
Pr}}[X]=\underset{\ \boldsymbol{w}\sim{\cal
U}(\Delta^{1}_{n}),{\boldsymbol{j}}\sim{\cal U}({\rm
one}(\boldsymbol{w})),\boldsymbol{y}\sim{\cal
U}(\boldsymbol{w}^{{\boldsymbol{j}}\leftarrow U})}{{\bf Pr}}[X].$

###### Proof.

Denote the above distribution by ${\cal D}^{\prime}$. By Item 1 in Fact 4, if
$w\in\Delta_{n}^{1}$ and $j\in{\rm one}(w)$, then $w^{j\leftarrow
U}\subseteq\Delta^{0}_{n}$. Therefore, for $z\in\Delta^{1}_{n}$, ${\bf
Pr}_{\boldsymbol{y}\sim{\cal
D}^{\prime}}[\boldsymbol{y}=z|\boldsymbol{\xi}=0]=0$ and then

$\underset{\ \boldsymbol{y}\sim{\cal D}^{\prime}}{{\bf
Pr}}[\boldsymbol{y}=z]=\underset{\ \boldsymbol{\xi}\sim{\cal
U}({\\{0,1\\})}}{{\bf Pr}}{[\boldsymbol{\xi}=1]}\cdot\underset{\
\boldsymbol{y}\sim{\cal U}({\Delta^{1}_{n}})}{{\bf
Pr}}[\boldsymbol{y}=z]=\frac{1}{2|\Delta^{1}_{n}|}=\frac{1}{2|\Delta^{1}|^{n}}.$

For $z\in\Delta^{0}_{n}$, suppose
$z\in\Delta^{u_{1}}\times\cdots\times\Delta^{u_{n}}$ where $u\in U$. In the
sampling according to ${\cal D}^{\prime}$ and when $\xi=0$, since for
$j\in{\rm one}(w)$, the elements of $w^{j\leftarrow U}$ are below $w$, we have
$\underset{\ \boldsymbol{y}\sim{\cal D}^{\prime}}{{\bf
Pr}}[\boldsymbol{y}=z|\boldsymbol{w}\not>z]=0$. Therefore,

$\displaystyle\underset{\ \boldsymbol{y}\sim{\cal D}^{\prime}}{{\bf
Pr}}[\boldsymbol{y}=z]$ $\displaystyle=$ $\displaystyle\underset{\
\boldsymbol{\xi}\sim{\cal U}({\\{0,1\\}})}{{\bf
Pr}}[\boldsymbol{\xi}=0]\cdot\underset{\ \boldsymbol{w}\sim{\cal
U}({\Delta^{1}_{n}})}{{\bf Pr}}[\boldsymbol{w}>z]\cdot$ (2)
$\displaystyle\cdot\underset{\ {\boldsymbol{j}}\sim{\cal
U}(one(\boldsymbol{w}))}{{\bf
Pr}}[z\in\boldsymbol{w}^{{\boldsymbol{j}}\leftarrow
U}|\boldsymbol{w}>z,\boldsymbol{w}\in\Delta^{1}_{n}]\cdot\underset{\
\boldsymbol{v}\sim{\cal U}(\boldsymbol{w}^{{\boldsymbol{j}}\leftarrow
U})}{{\bf Pr}}[\boldsymbol{v}=z|z\in\boldsymbol{w}^{{\boldsymbol{j}}\leftarrow
U}].$

Now, since, for $x\in\Delta^{0}$, the number of elements in $\Delta^{1}$ that
are above $x$ is $\lceil\ell/2\rceil$, we have that the number of
$w\in\Delta^{1}_{n}=(\Delta^{1})^{n}$ that are above
$z\in\Delta^{u_{1}}\times\cdots\times\Delta^{u_{n}}$ is
$\lceil\ell/2\rceil^{n-{\rm wt}(u)}$. Therefore,

$\displaystyle\underset{\ \boldsymbol{w}\sim{\cal U}({\Delta^{1}_{n}})}{{\bf
Pr}}[\boldsymbol{w}>z]=\frac{\lceil\ell/2\rceil^{n-{\rm
wt}(u)}}{|\Delta^{1}_{n}|}.$ (3)

Now let $w>z$ and $w\in\Delta^{1}_{n}$. Since for two different
$u,u^{\prime}\in U$, we have $\prod_{i=1}^{n}\Delta^{u_{i}}$ and
$\prod_{i=1}^{n}\Delta^{u^{\prime}_{i}}$ are disjoint sets, and since
$z\in\Delta^{u_{1}}\times\cdots\times\Delta^{u_{n}}$, we have $z\in
w^{j\leftarrow U}$ if and only if $z=w^{j\leftarrow u}$. Therefore, the number
of elements $j\in{\rm one}(w)$ that satisfy $z\in w^{j\leftarrow U}$ is the
number of elements $j\in{\rm one}(w)$ that satisfy $z=w^{j\leftarrow u}$. This
is the number of elements $j\in{\rm one}(w)$ that satisfies for every
$u_{i}=0$, $z_{i,j_{i}}=0$. For a $j$ u.a.r. and a fixed $i$ where $u_{i}=0$,
the probability that $z_{i}$ and $w_{i}$ differ only in entry $j_{i}$ is
$1/\lceil\ell/2\rceil$. Therefore,

$\displaystyle\underset{\ {\boldsymbol{j}}\sim{\cal
U}(one(\boldsymbol{w}))}{{\bf
Pr}}[z\in\boldsymbol{w}^{{\boldsymbol{j}}\leftarrow
U}|\boldsymbol{w}>z,\boldsymbol{w}\in\Delta^{1}_{n}]=\frac{1}{\lceil\ell/2\rceil^{n-{\rm
wt}(u)}}.$ (4)

Finally, by item 2 in Fact 4, since $|w^{j\leftarrow U}|=|U|$, we have

$\displaystyle\underset{\ \boldsymbol{v}\sim{\cal
U}(\boldsymbol{w}^{j\leftarrow U})}{{\bf
Pr}}[\boldsymbol{v}=z|z\in\boldsymbol{w}^{j\leftarrow
U}]=\frac{1}{|\boldsymbol{w}^{j\leftarrow U}|}=\frac{1}{|U|}.$ (5)

By (2), (3), (4), and (5), we have

$\displaystyle\underset{\ \boldsymbol{y}\sim{\cal D}^{\prime}}{{\bf
Pr}}[\boldsymbol{y}=z]$ $\displaystyle=$
$\displaystyle\frac{1}{2}\cdot\frac{\lceil\ell/2\rceil^{n-{\rm
wt}(u)}}{|\Delta_{n}^{1}|}\cdot\frac{1}{\lceil\ell/2\rceil^{n-{\rm
wt}(u)}}\cdot\frac{1}{|U|}=\frac{1}{2|U|\cdot|\Delta_{n}^{1}|}=\frac{1}{2|U|\cdot|\Delta^{0}|^{n}}.$

∎

##  3 Main Lemma

In this section, we prove

######  Lemma 2.

Let ${\cal S}=(S,U,E)$ be a set cover instance. If
$F:(\\{0,1\\}^{\ell})^{n}\to\\{0,1\\}$ is a DNF of size $|F|<2^{{\rm
opt}({\cal S})\ell/20}$, then ${\rm dist}_{{\cal
D}_{\ell}}(F,\Gamma_{\ell})\geq 1/(8|U|)-2^{-{\rm opt}({\cal S})\ell/20}$.

Note that Lemma 2 is used to prove Theorem 1 and 2. To prove Theorem 3, we
will need Lemma 4, a stronger version of Lemma 2.

To prove the lemma, we first establish some results.

For a term $T$, let $T_{\cal M}$ be the conjunction of all the unnegated
variables in $T$. We define the monotone size of $T$ to be $|T_{\cal M}|$.

######  Claim 1.

Let ${\cal S}=(S,U,E)$ be a set cover instance and $\ell\geq 5$. If
$F:(\\{0,1\\}^{\ell})^{n}\to\\{0,1\\}$ is a DNF of size $|F|<2^{{\rm
opt}({\cal S})\ell/20}$, then there is a DNF, $F^{\prime}$, of size
$|F^{\prime}|\leq 2^{{\rm opt}({\cal S})\ell/20}$ with terms of monotone size
at most ${\rm opt}({\cal S})\ell/5$ such that ${\rm dist}_{{\cal
D}_{\ell}}(\Gamma_{\ell},F^{\prime})\leq{\rm dist}_{{\cal
D}_{\ell}}(\Gamma_{\ell},F)+2^{-{\rm opt}({\cal S})\ell/20}$.

###### Proof.

Let $T$ be a term of monotone size at least ${\rm opt}({\cal S})\ell/5$. Let
$b_{i}$ denote the number of unnegated variables of $T$ of the form $y_{i,j}$
and let $T_{i}$ be their conjunction. Then $T_{\cal M}=\wedge_{i=1}^{n}T_{i}$
and $\sum_{i=1}^{n}b_{i}=|T_{\cal M}|\geq{\rm opt}({\cal S})\ell/5$. If, for
some $i$, $b_{i}>\lceil\ell/2\rceil$, then the term $T_{i}$ is zero on all
$\Delta^{0}\cup\Delta^{1}$, and therefore, $T$ is zero on all
$\Delta^{0}_{n}\cup\Delta^{1}_{n}$. Thus, it can be just removed from $F$. So,
we may assume that $b_{i}\leq\lceil\ell/2\rceil$ for all $i$. First,

$\displaystyle\underset{\ \boldsymbol{y}\sim{\cal D}_{\ell}}{{\bf
Pr}}[T(\boldsymbol{y})=1|\Gamma_{\ell}(\boldsymbol{y})=1]$ $\displaystyle=$
$\displaystyle\underset{\ \boldsymbol{y}\sim{\cal U}({\Delta^{1}_{n}})}{{\bf
Pr}}[T(\boldsymbol{y})=1]\leq\underset{\ \boldsymbol{y}\sim{\cal
U}({\Delta^{1}_{n}})}{{\bf Pr}}[T_{\cal M}(\boldsymbol{y})=1]$ (6)
$\displaystyle=$ $\displaystyle\prod_{i=1}^{n}\underset{\
\boldsymbol{y}_{i}\sim{\cal U}({\Delta^{1}})}{{\bf
Pr}}[T_{i}(\boldsymbol{y}_{i})=1]$ $\displaystyle=$
$\displaystyle\prod_{i=1}^{n}\frac{{\ell-b_{i}\choose\lceil\ell/2\rceil-
b_{i}}}{{\ell\choose\lceil\ell/2\rceil}}$ $\displaystyle=$
$\displaystyle\prod_{i=1}^{n}\left(1-\frac{b_{i}}{\ell}\right)\left(1-\frac{b_{i}}{\ell-1}\right)\cdots\left(1-\frac{b_{i}}{\lceil\ell/2\rceil+1}\right)$
$\displaystyle\leq$
$\displaystyle\prod_{i=1}^{n}\prod_{j=\lceil\ell/2\rceil+1}^{\ell}{\rm
exp}({-b_{i}/j})=\prod_{i=1}^{n}{\rm
exp}\left({-b_{i}\sum_{j=\lceil\ell/2\rceil+1}^{\ell}1/j}\right)$
$\displaystyle=$ $\displaystyle{\rm exp}\left({-|T_{\cal
M}|\sum_{j=\lceil\ell/2\rceil+1}^{\ell}1/j}\right)\leq 2^{-|T_{\cal M}|/2}\leq
2^{-{\rm opt}({\cal S})\ell/10}.$

Let $F^{\prime}$ be the disjunction of all the terms in $F$ of monotone size
at most ${\rm opt}({\cal S})\ell/5$. Let $T^{(1)},\ldots,T^{(m)}$ be all the
terms of monotone size greater than ${\rm opt}({\cal S})\ell/5$ in $F$. Then,
by (6) and the union bound,

$\displaystyle\underset{\ \boldsymbol{y}\sim{\cal D}_{\ell}}{{\bf
Pr}}[F(\boldsymbol{y})\not=F^{\prime}(\boldsymbol{y})|\Gamma_{\ell}(\boldsymbol{y})=1]$
$\displaystyle\leq$ $\displaystyle\underset{\ \boldsymbol{y}\sim{\cal
D}_{\ell}}{{\bf
Pr}}[\vee_{i=1}^{m}T^{(i)}(\boldsymbol{y})=1|\Gamma_{\ell}(\boldsymbol{y})=1]$
(7) $\displaystyle\leq$ $\displaystyle 2^{-{\rm opt}({\cal S})\ell/10}m\leq
2^{-{\rm opt}({\cal S})\ell/20}.$

and (Here we abbreviate $F^{\prime}(\boldsymbol{y}),F(\boldsymbol{y})$ and
$\Gamma_{\ell}(\boldsymbol{y})$ by $F^{\prime},F$ and $\Gamma_{\ell}$)

$\displaystyle{\rm dist}_{{\cal D}_{\ell}}(\Gamma_{\ell},F^{\prime})$
$\displaystyle=$ $\displaystyle\underset{\ \boldsymbol{y}\sim{\cal
D}_{\ell}}{{\bf Pr}}[F^{\prime}\not=\Gamma_{\ell}]$ (9) $\displaystyle=$
$\displaystyle\frac{1}{2}\underset{\ \boldsymbol{y}\sim{\cal D}_{\ell}}{{\bf
Pr}}[F^{\prime}\not=\Gamma_{\ell}|\Gamma_{\ell}=1]+\frac{1}{2}\underset{\
\boldsymbol{y}\sim{\cal D}_{\ell}}{{\bf
Pr}}[F^{\prime}\not=\Gamma_{\ell}|\Gamma_{\ell}=0]$ $\displaystyle=$
$\displaystyle\frac{1}{2}\underset{\ \boldsymbol{y}\sim{\cal D}_{\ell}}{{\bf
Pr}}[F^{\prime}\not=F|\Gamma_{\ell}=1]+$ $\displaystyle\frac{1}{2}\underset{\
\boldsymbol{y}\sim{\cal D}_{\ell}}{{\bf
Pr}}[F\not=\Gamma_{\ell}|\Gamma_{\ell}=1]+\frac{1}{2}\underset{\
\boldsymbol{y}\sim{\cal D}_{\ell}}{{\bf
Pr}}[F^{\prime}\not=\Gamma_{\ell}|\Gamma_{\ell}=0]$ $\displaystyle\leq$
$\displaystyle 2^{-{\rm opt}({\cal S})\ell/20}+\frac{1}{2}\underset{\
\boldsymbol{y}\sim{\cal D}_{\ell}}{{\bf
Pr}}[F\not=\Gamma_{\ell}|\Gamma_{\ell}=1]+\frac{1}{2}\underset{\
\boldsymbol{y}\sim{\cal D}_{\ell}}{{\bf
Pr}}[F\not=\Gamma_{\ell}|\Gamma_{\ell}=0]$ $\displaystyle=$ $\displaystyle
2^{-{\rm opt}({\cal S})\ell/20}+{\rm dist}_{{\cal
D}_{\ell}}(\Gamma_{\ell},F).$

In (9), we used Fact 2. In (9), we used the probability triangle inequality.
In (3), we used (7) and the fact that if $F^{\prime}(\boldsymbol{y})\not=0$,
then $F(\boldsymbol{y})\not=0$. ∎

We now prove

######  Claim 2.

Let $z\in\Delta_{n}^{1}$. Let $F$ be a DNF with terms of monotone size at most
$\lceil\ell/2\rceil({\rm opt}({\cal S})-1)/2$ that satisfies $F(z)=1$. Then

$\underset{\ {\boldsymbol{j}}\sim{\cal U}({\rm
one}(z)),\boldsymbol{y}\sim{\cal U}(z^{{\boldsymbol{j}}\leftarrow U})}{{\bf
Pr}}[F(\boldsymbol{y})=1]\geq\frac{1}{2|U|}.$

###### Proof.

Since $F(z)=1$, there is a term $T$ in $F$ that satisfies $T(z)=1$. Let
$Y_{0}=\\{y_{i,m}|z_{i,m}=0\\}$ and $Y_{1}=\\{y_{i,m}|z_{i,m}=1\\}$. Since
$T(z)=1$, every variable in $Y_{0}$ that appears in $T$ must be negated, and
every variable in $Y_{1}$ that appears in $T$ must be unnegated. For $j\in{\rm
one}(z)$, define $q(j)$ to be the number of variables in
$\\{y_{1,j_{1}},\ldots,y_{n,j_{n}}\\}$ that appear in $T(y)$. All those
variables appear unnegated in $T$ because $j\in{\rm one}(z)$. Recall that
$T_{\cal M}$ is the conjunction of all unnegated variables in $T$. Then
$|T_{\cal M}|\leq\lceil\ell/2\rceil({\rm opt}({\cal S})-1)/2$. Each variable
in $T_{\cal M}$ contributes $\lceil\ell/2\rceil^{n-1}$ to the sum $\sum_{j\in
one(z)}q(j)$ and $|{\rm one}(z)|=\lceil\ell/2\rceil^{n}$. Therefore,

$\underset{{\boldsymbol{j}}\sim{\cal U}({\rm
one}(z))}{\mathbb{E}}[q({\boldsymbol{j}})]=\frac{|T_{\cal
M}|}{\lceil\ell/2\rceil}\leq\frac{{\rm opt}({\cal S})-1}{2}.$

By Markov’s bound, at least half the elements $j\in{\rm one}(z)$ satisfies
$q(j)\leq{\rm opt}({\cal S})-1$. Let $J=\\{j\in{\rm one}(z)|q(j)<{\rm
opt}({\cal S})\\}$. Then ${\bf Pr}_{{\boldsymbol{j}}\sim{\cal U}({\rm
one}(z))}[{\boldsymbol{j}}\in J]\geq 1/2$. Consider $j\in J$ and let $T^{j}$
be the conjunction of all the variables that appear in $T$ of the form
$y_{i,j_{i}}$. Then $|T^{j}|=q(j)\leq{\rm opt}({\cal S})-1$. By Fact 1, there
is $u\in U$ such that $T^{j}(u)=1$. By Fact 4, we have $T(z^{j\leftarrow
u})=T^{j}(u)=1$. Then $F(z^{j\leftarrow u})=1$. Since by item 1 in Fact 4,
$|z^{j\leftarrow U}|=|U|$, we have

${\bf Pr}_{{\boldsymbol{j}}\sim{\cal U}(one(z)),\boldsymbol{y}\sim{\cal
U}(z^{{\boldsymbol{j}}\leftarrow U})}[F(\boldsymbol{y})=1|{\boldsymbol{j}}\in
J]\geq\frac{1}{|U|}.$

Therefore,

$\underset{\ {\boldsymbol{j}}\sim{\cal U}({\rm
one}(z)),\boldsymbol{y}\sim{\cal U}(z^{{\boldsymbol{j}}\leftarrow U})}{{\bf
Pr}}[F(\boldsymbol{y})=1]\geq\underset{\ {\boldsymbol{j}}\sim{\cal U}({\rm
one}(z))}{{\bf Pr}}[{\boldsymbol{j}}\in J]\cdot\underset{\
{\boldsymbol{j}}\sim{\cal U}({\rm one}(z)),\boldsymbol{y}\sim{\cal
U}(z^{j\leftarrow U})}{{\bf Pr}}[F(\boldsymbol{y})=1|{\boldsymbol{j}}\in
J]\geq\frac{1}{2|U|}.$

∎

We are now ready to prove

######  Lemma 2.

Let ${\cal S}=(S,U,E)$ be a set cover instance, and let $\ell\geq 5$. If
$F:(\\{0,1\\}^{\ell})^{n}\to\\{0,1\\}$ is a DNF of size $|F|<2^{{\rm
opt}({\cal S})\ell/20}$, then ${\rm dist}_{{\cal
D}_{\ell}}(F,\Gamma_{\ell})\geq 1/(8|U|)-2^{-{\rm opt}({\cal S})\ell/20}$.

###### Proof.

By Claim 1, there is a DNF, $F^{\prime}$, of size $|F^{\prime}|\leq 2^{{\rm
opt}({\cal S})\ell/20}$ with terms of monotone size at most ${\rm opt}({\cal
S})\ell/5$ such that ${\rm dist}_{{\cal
D}_{\ell}}(\Gamma_{\ell},F^{\prime})\leq{\rm dist}_{{\cal
D}_{\ell}}(\Gamma_{\ell},F)+2^{-{\rm opt}({\cal S})\ell/20}$. Therefore, it is
enough to prove that ${\rm dist}_{{\cal
D}_{\ell}}(\Gamma_{\ell},F^{\prime})\geq 1/(8|U|)$.

If $\underset{\ \boldsymbol{y}\sim{\cal U}(\Delta_{n}^{1})}{{\bf
Pr}}[F^{\prime}(\boldsymbol{y})\not=1]\geq 1/(4|U|)$, then by Fact 2, we have

${\rm dist}_{{\cal D}_{\ell}}(\Gamma_{\ell},F^{\prime})\geq\underset{\
\boldsymbol{y}\sim{\cal D}_{\ell}}{{\bf
Pr}}[\Gamma_{\ell}(\boldsymbol{y})\not=F^{\prime}(\boldsymbol{y})|\Gamma_{\ell}(\boldsymbol{y})=1]\underset{\
\boldsymbol{y}\sim{\cal D}_{\ell}}{{\bf
Pr}}[\Gamma_{\ell}(\boldsymbol{y})=1]=\frac{1}{2}\underset{\
\boldsymbol{y}\sim{\cal U}(\Delta^{1}_{n})}{{\bf
Pr}}[F^{\prime}(\boldsymbol{y})\not=1]\geq\frac{1}{8|U|}.$

If $\underset{\ \boldsymbol{y}\sim{\cal U}(\Delta_{n}^{1})}{{\bf
Pr}}[F^{\prime}(\boldsymbol{y})\not=1]<1/(4|U|)$, then by Fact 2 and 5, and
Claim 2,

$\displaystyle{\rm dist}_{{\cal D}_{\ell}}(\Gamma_{\ell},F^{\prime})$
$\displaystyle\geq$ $\displaystyle\underset{\ \boldsymbol{y}\sim{\cal
D}_{\ell}}{{\bf
Pr}}[\Gamma_{\ell}(\boldsymbol{y})\not=F^{\prime}(\boldsymbol{y})|\Gamma_{\ell}(\boldsymbol{y})=0]\underset{\
\boldsymbol{y}\sim{\cal D}_{\ell}}{{\bf Pr}}[\Gamma_{\ell}(\boldsymbol{y})=0]$
$\displaystyle=$ $\displaystyle\frac{1}{2}\underset{\ \boldsymbol{y}\sim{\cal
U}(\Delta_{n}^{0})}{{\bf Pr}}[F^{\prime}(\boldsymbol{y})=1]$ $\displaystyle=$
$\displaystyle\frac{1}{2}\underset{\ \boldsymbol{z}\sim{\cal
U}(\Delta^{1}_{n}),{\boldsymbol{j}}\sim{\cal U}({\rm
one}(\boldsymbol{z})),\boldsymbol{y}\sim{\cal
U}(\boldsymbol{z}^{{\boldsymbol{j}}\leftarrow U})}{{\bf
Pr}}[F^{\prime}(\boldsymbol{y})=1]$ $\displaystyle\geq$
$\displaystyle\frac{1}{2}\underset{\ \boldsymbol{z}\sim{\cal
U}(\Delta^{1}_{n}),{\boldsymbol{j}}\sim{\cal U}({\rm
one}(\boldsymbol{z})),\boldsymbol{y}\sim{\cal
U}(\boldsymbol{z}^{{\boldsymbol{j}}\leftarrow U})}{{\bf
Pr}}[F^{\prime}(\boldsymbol{y})=1|F^{\prime}(\boldsymbol{z})=1]\cdot\underset{\
\boldsymbol{z}\sim{\cal U}(\Delta^{1}_{n})}{{\bf
Pr}}[F^{\prime}(\boldsymbol{z})=1]$ $\displaystyle\geq$
$\displaystyle\frac{1}{2}\frac{1}{2|U|}\left(1-\frac{1}{4|U|}\right)\geq\frac{1}{8|U|}.$

∎

##  4 Superpolynomial Lower Bound

In this section, we prove the first results of the paper. First, we prove the
following result for Monotone $(\log n)$-Junta.

######  Lemma 3.

Assuming randomized ETH, there is a constant $c$ such that any PAC learning
algorithm for $n$-variable Monotone $(\log n)$-Junta by DNF with
$\epsilon=1/(16n)$ must take at least

$n^{c\frac{\log\log n}{\log\log\log n}}$

time.

The lower bound holds, even if the learner knows the distribution, can draw a
sample according to the distribution in polynomial time and can compute the
target on all the points of the support of the distribution in polynomial
time.

###### Proof.

Consider the constant $\lambda$ in Lemma 1. Let $c=\min(1/40,\lambda/4)$.
Suppose there is a PAC learning algorithm ${\cal A}$ for Monotone $(\log
n)$-Junta by DNF with $\epsilon=1/(16n)$ that runs in time $n^{c\frac{\log\log
n}{\log\log\log n}}$. We show that there is $k$ such that for

$k^{\prime}=\frac{1}{2}\left(\frac{\log N}{\log\log N}\right)^{1/k},$

$(k,k^{\prime})$-Set-Cover can be solved in time $N^{4ck}\leq N^{\lambda k}$.
By Lemma 1, the result then follows.

Let ${\cal S}=(S,U,E)$ be an $N$-vertex $(k,k^{\prime})$-Set-Cover instance
where

$k=\frac{1}{2}\frac{\log\log N}{\log\log\log N}\mbox{\ and\
}k^{\prime}=\frac{1}{2}\left(\frac{\log N}{\log\log N}\right)^{1/k}.$

Let

$\ell=\frac{\log N}{k}$

and consider $\Gamma_{\ell}$ and ${\cal D}_{\ell}$.

Consider the following algorithm ${\cal B}$

  1. 1.

Input ${\cal S}=(S,U,E)$ an instance for $(k,k^{\prime})$-Set-Cover .

  2. 2.

Construct $\Gamma_{\ell}$ and ${\cal D}_{\ell}$.

  3. 3.

Run ${\cal A}$ using $\Gamma_{\ell}$ and ${\cal D}_{\ell}$. If it runs more
than $N^{4ck}$ steps, then output No .

  4. 4.

Let $F$ be the output DNF.

  5. 5.

Estimate $\eta={\rm dist}_{{\cal D}_{\ell}}(F,\Gamma_{\ell})$.

  6. 6.

If $\eta\leq\frac{1}{16N}$, output Yes , otherwise output No .

The running time of this algorithm is $N^{4ck}\leq N^{\lambda k}$. Therefore,
it is enough to prove the following

######  Claim 3.

Algorithm ${\cal B}$ solves $(k,k^{\prime})$-Set-Cover .

###### Proof.

Yes case: Let ${\cal S}=(S,U,E)$ be a $(k,k^{\prime})$-Set-Cover instance and
${\rm opt}({\cal S})\leq k$. Then, ${\rm opt}({\cal S})\cdot\ell\leq
k\ell=\log N$, and by Fact 3, $\Gamma_{\ell}$ is Monotone $\log N$-Junta.
Therefore, w.h.p., algorithm ${\cal A}$ learns $\Gamma_{\ell}$ and outputs a
DNF that is $\eta=1/(16N)$ close to the target with respect to ${\cal
D}_{\ell}$. Since ${\cal B}$ terminates ${\cal A}$ after $N^{4ck}$ time, we
only need to prove that ${\cal A}$ runs at most $N^{4ck}$ time.

The running time of ${\cal A}$ is

$N^{c\frac{\log\log N}{\log\log\log N}}<N^{4ck}.$

No Case: Let ${\cal S}=(S,U,E)$ be a $(k,k^{\prime})$-Set-Cover instance and
${\rm opt}({\cal S})>k^{\prime}$. By Lemma 2, any DNF, $F$, of size
$|F|<2^{k^{\prime}\ell/20}$ satisfies ${\rm dist}_{{\cal
D}_{\ell}}(F,\Gamma_{\ell})\geq 1/(8|U|)-2^{-k^{\prime}\ell/20}$. First, we
have

$(2k)^{2k}=\left(\frac{\log\log N}{\log\log\log N}\right)^{\frac{\log\log
N}{\log\log\log N}}<\frac{\log N}{\log\log N}.$

Therefore, since $c\leq 1/40$,

$k^{\prime}=\frac{1}{2}\left(\frac{\log N}{\log\log
N}\right)^{1/k}>\frac{1}{2}(2k)^{2}>80ck^{2}.$

So $k^{\prime}\ell/20>(k\ell)(4ck)$ and

$2^{k^{\prime}\ell/20}>(2^{k\ell})^{4ck}=N^{4ck}.$

Now since the algorithm runs in time $N^{4ck}$, it cannot output a DNF $F$ of
size more than $N^{4ck}<2^{k^{\prime}\ell/20}$, and by Lemma 2,

${\rm dist}_{{\cal
D}_{\ell}}(F,\Gamma_{\ell})\geq\frac{1}{8|U|}-\frac{1}{N^{4ck}}\geq\frac{1}{9N}.$

So it either runs more than $N^{4ck}$ steps and then outputs No in step 3 or
outputs a DNF with an error greater than $1/(9N)>1/(16N)$ and outputs No in
step 6. ∎

Notice that the learning algorithm knows $\Gamma_{\ell}$ and ${\cal
D}_{\ell}$. It is also clear from the definition of $\Gamma_{\ell}$ and ${\cal
D}_{\ell}$ that the learning algorithm can draw a sample according to the
distribution ${\cal D}_{\ell}$ in polynomial time and can compute the target
$\Gamma_{\ell}$ on all the points of the support of the distribution in
polynomial time. ∎

We now prove

######  Theorem 1.

Assuming randomized ETH, there is a constant $c$ such that any PAC learning
algorithm for $n$-variable size-$s$ Monotone DT and size-$s$ Monotone DNF by
DNF with $\epsilon=1/(16n)$ must take at least

$n^{c\frac{\log\log s}{\log\log\log s}}$

time.

The lower bound holds, even if the learner knows the distribution, can draw a
sample according to the distribution in polynomial time and can compute the
target on all the points of the support of the distribution in polynomial
time.

###### Proof.

By Lemma 3, assuming randomized ETH, there is a constant $c$ such that any PAC
learning algorithm for $n$-variable Monotone $(\log n)$-Junta by DNF with
$\epsilon=1/(16n)$ runs in time

$n^{c\frac{\log\log n}{\log\log\log n}}.$

Now by (1) and since $s=n$, the result follows. ∎

##  5 Tight Bound Assuming some Conjecture

A plausible conjecture on the hardness of Set-Cover is the following.

######  Conjecture 1.

[9] There are constants $\alpha,\beta,\lambda\in(0,1)$ such that, for
$k<N^{\alpha}$, there is no randomized $N^{\lambda k}$ time algorithm that can
solve $\left(k,(1-\beta)\cdot k\ln N\right)$-Set-Cover on $N$ vertices with
high probability.

We now prove

######  Theorem 2.

Assuming Conjecture 1, there is a constant $c$ such that any PAC learning
algorithm for $n$-variable Monotone $(\log s)$-Junta, size-$s$ Monotone DT and
size-$s$ Monotone DNF by DNF with $\epsilon=1/(16n)$ must take at least

$n^{c\log s}$

time.

The lower bound holds, even if the learner knows the distribution, can draw a
sample according to the distribution in polynomial time and can compute the
target on all the points of the support of the distribution in polynomial
time.

###### Proof.

We give the proof for Monotone $(\log s)$-Junta. As in the proof of Theorem 1,
the result then follows for the other classes.

Consider the constants $\alpha,\beta$ and $\lambda$ in Conjecture 1. Let
$c=\min(\lambda/10,(1-\beta)/(20\log e))$. Suppose there is a PAC learning
algorithm ${\cal A}$ for Monotone $(\log s)$-Junta by DNF with
$\epsilon=1/(16n)$ that runs in time $n^{c\log s}$. We show that there is
$k<N^{\alpha}$, $k=\omega(1)$, such that $(k,k^{\prime})$-Set-Cover can be
solved in time $N^{\lambda k}$ where $k^{\prime}=(1-\beta)k\ln N$. By
Conjecture 1, the result then follows.

Consider the following algorithm ${\cal B}$

  1. 1.

Input ${\cal S}=(S,U,E)$ an instance for $(k,k^{\prime})$-Set-Cover .

  2. 2.

Construct $\Gamma_{5}$ and ${\cal D}_{5}$.

  3. 3.

Run ${\cal A}$ using $\Gamma_{5}$ and ${\cal D}_{5}$ with $s=2^{5k}$. If it
runs more than $N^{5ck}$ steps, then output No .

  4. 4.

Let $F$ be the output DNF.

  5. 5.

Estimate $\eta={\rm dist}_{{\cal D}_{5}}(F,\Gamma_{5})$.

  6. 6.

If $\eta\leq\frac{1}{16N}$, output Yes , otherwise output No .

Since $c<\lambda/10$, the running time of this algorithm is
$N^{5ck}<N^{\lambda k}$. Therefore, it is enough to prove the following

######  Claim 4.

Algorithm ${\cal B}$ solves $(k,k^{\prime})$-Set-Cover .

###### Proof.

Yes case: Let ${\cal S}=(S,U,E)$ be a $(k,k^{\prime})$-Set-Cover instance and
${\rm opt}({\cal S})\leq k$. Then, $5\cdot{\rm opt}({\cal S})\leq 5k=\log s$,
and by Fact 3, $\Gamma_{5}$ is Monotone $\log s$-Junta. Therefore, w.h.p.,
algorithm ${\cal A}$ learns $\Gamma_{5}$ and outputs a DNF that is
$\eta=1/(16N)$ close to the target with respect to ${\cal D}_{5}$. Since
${\cal B}$ terminates ${\cal A}$ after $N^{5ck}$ time, we only need to prove
that ${\cal A}$ runs at most $N^{5ck}$ time.

The running time of ${\cal A}$ is

$n^{c\log s}\leq N^{5ck}.$

No Case: Let ${\cal S}=(S,U,E)$ be a $(k,k^{\prime})$-Set-Cover instance and
${\rm opt}({\cal S})>k^{\prime}=(1-\beta)k\ln N$. By Lemma 2, any DNF, $F$, of
size $|F|<2^{k^{\prime}/4}$ satisfies ${\rm dist}_{{\cal
D}_{5}}(F,\Gamma_{5})\geq 1/(8|U|)-2^{-k^{\prime}/4}$. Since,
$c<(1-\beta)/(20\log e)$,

$2^{k^{\prime}/4}=2^{\frac{(1-\beta)k\ln N}{4}}=N^{\frac{(1-\beta)k}{4\log
e}}>N^{5ck},$

any DNF, $F$, that the learning outputs satisfies

${\rm dist}_{{\cal
D}_{5}}(F,\Gamma_{5})\geq\frac{1}{8|U|}-2^{-k^{\prime}/4}\geq\frac{1}{8N}-\frac{1}{N^{5ck}}\geq\frac{1}{9N}.$

Therefore, with high probability the algorithm answer No . ∎

∎

##  6 Strictly Proper Learning

In this section, we prove

######  Theorem 3.

Assuming randomized ETH, there is a constant $c$ such that any PAC learning
algorithm for $n$-variable Monotone $(\log s)$-Junta, size-$s$ Monotone DT and
size-$s$ Monotone DNF by size-$s$ DNF with $\epsilon=1/(16n)$ must take at
least

$n^{c\log s}$

time.

The lower bound holds, even if the learner knows the distribution, can draw a
sample according to the distribution in polynomial time and compute the target
on all the points of the support of the distribution in polynomial time.

We first prove the following stronger version of Lemma 2

######  Lemma 4.

Let ${\cal S}=(S,U,E)$ be a set cover instance, and let $\ell\geq 5$. If
$F:(\\{0,1\\}^{\ell})^{n}\to\\{0,1\\}$ is a DNF of size $|F|<2^{{\rm
opt}({\cal S})\ell/16}$, then ${\rm dist}_{{\cal
D}_{\ell}}(F,\Gamma_{\ell})\geq 1/(8|U|)$.

To prove this lemma, we will give some more results.

Recall that, for a term $T$, $T_{\cal M}$ is the conjunction of all the
unnegated variables in $T$. We define the monotone size of $T$ to be $|T_{\cal
M}|$. For a DNF $F=T_{1}\vee T_{2}\vee\cdots\vee T_{s}$ and
$z\in(\\{0,1\\}^{\ell})^{n}$, we define the monotone width of $z$ in $F$ as

${\rm{mwidth}}_{F}(z):=\left\\{\begin{array}[]{ll}\min_{T_{i}(z)=1}|(T_{i})_{\cal
M}|&F(z)=1\\\ 0&F(z)=0\end{array}.\right.$

We define $F^{-1}(1)=\\{z|F(z)=1\\}$ and

$\Omega=\Delta^{1}_{n}\cap F^{-1}(1).$

######  Claim 5.

Let $F$ be a DNF with

$\underset{\boldsymbol{z}\sim{\cal
U}(\Omega)}{\mathbb{E}}\left[{\rm{mwidth}}_{F}(\boldsymbol{z})\right]\leq{\rm
opt}(S)\cdot\ell/4.$

Then

$\underset{\ \boldsymbol{z}\sim{\cal U}(\Omega),{\boldsymbol{j}}\sim{\cal
U}({\rm one}(\boldsymbol{z})),\boldsymbol{y}\sim{\cal
U}(\boldsymbol{z}^{{\boldsymbol{j}}\leftarrow U})}{{\bf
Pr}}[F(\boldsymbol{y})=1]\geq\frac{1}{2|U|}.$

###### Proof.

Let $z\in\Omega$. Then $F(z)=1$ and $z\in\Delta^{1}_{n}$. Let $T^{z}$ be the
term in $F$ with $|T^{z}_{\cal M}|={\rm{mwidth}}_{F}(z)$ that satisfies
$T^{z}(z)=1$. Let $Y_{0}=\\{y_{i,m}|z_{i,m}=0\\}$ and
$Y_{1}=\\{y_{i,m}|z_{i,m}=1\\}$. Since $T^{z}(z)=1$, every variable in $Y_{0}$
that appears in $T^{z}$ must be negated, and every variable in $Y_{1}$ that
appears in $T^{z}$ must be unnegated. For $j\in{\rm one}(z)$, define
$q_{z}(j)$ to be the number of variables in
$\\{y_{1,j_{1}},\ldots,y_{n,j_{n}}\\}$ that appear in $T^{z}(y)$. All those
variables appear unnegated in $T$ because $j\in{\rm one}(z)$. Each variable in
$T^{z}_{\cal M}$ contributes $\lceil\ell/2\rceil^{n-1}$ to the sum $\sum_{j\in
one(z)}q_{z}(j)$ and $|{\rm one}(z)|=\lceil\ell/2\rceil^{n}$. Therefore,

$\underset{{\boldsymbol{j}}\sim{\cal U}({\rm
one}(z))}{\mathbb{E}}[q_{z}({\boldsymbol{j}})]=\frac{|T^{z}_{\cal
M}|}{\lceil\ell/2\rceil}=\frac{{\rm{mwidth}}_{F}(z)}{\lceil\ell/2\rceil}.$

Now,

$\displaystyle\underset{\boldsymbol{z}\sim{\cal
U}(\Omega),{\boldsymbol{j}}\sim{\cal U}({\rm
one}(\boldsymbol{z}))}{\mathbb{E}}[q_{\boldsymbol{z}}({\boldsymbol{j}})]$
$\displaystyle=$ $\displaystyle\frac{\underset{\boldsymbol{z}\sim{\cal
U}(\Omega)}{\mathbb{E}}\left[{\rm{mwidth}}_{F}(\boldsymbol{z})\right]}{\lceil\ell/2\rceil}$
$\displaystyle\leq$ $\displaystyle\frac{{\rm opt}({\cal S})}{2}.$

By Markov’s bound,

$\underset{\ \boldsymbol{z}\sim{\cal U}(\Omega),{\boldsymbol{j}}\sim{\cal
U}({\rm one}(\boldsymbol{z}))}{{\bf
Pr}}[q_{\boldsymbol{z}}({\boldsymbol{j}})<{\rm opt}({\cal
S})]\geq\frac{1}{2}.$

Suppose for some $z\in\Omega$ and $j\in{\rm one}(z)$, we have $q_{z}(j)<{\rm
opt}({\cal S})$. Let $T^{j}$ be the conjunction of all the variables that
appear in $T_{\cal M}^{z}$ of the form $y_{i,j_{i}}$. Then
$|T^{j}|=q_{z}(j)<{\rm opt}({\cal S})$. By Fact 1, there is $u\in U$ such that
$T^{j}(u)=1$. By Fact 4, we have $T^{z}(z^{j\leftarrow u})=T^{j}(u)=1$. Then
$F(z^{j\leftarrow u})=1$. Since by item 1 in Fact 4, $|z^{j\leftarrow
U}|=|U|$, we have

$\underset{\ \boldsymbol{z}\sim{\cal U}(\Omega),{\boldsymbol{j}}\sim{\cal
U}(one(\boldsymbol{z})),\boldsymbol{y}\sim{\cal
U}(\boldsymbol{z}^{{\boldsymbol{j}}\leftarrow U})}{{\bf
Pr}}[F(\boldsymbol{y})=1|q_{\boldsymbol{z}}({\boldsymbol{j}})<{\rm opt}({\cal
S})]\geq\frac{1}{|U|}.$

Therefore,

$\displaystyle\underset{\ \boldsymbol{z}\sim{\cal
U}(\Omega),{\boldsymbol{j}}\sim{\cal U}({\rm
one}(\boldsymbol{z})),\boldsymbol{y}\sim{\cal
U}(\boldsymbol{z}^{{\boldsymbol{j}}\leftarrow U})}{{\bf
Pr}}[F(\boldsymbol{y})=1]$ $\displaystyle\geq$ $\displaystyle\underset{\
\boldsymbol{z}\sim{\cal U}(\Omega),{\boldsymbol{j}}\sim{\cal U}({\rm
one}(\boldsymbol{z}))}{{\bf Pr}}[q_{\boldsymbol{z}}({\boldsymbol{j}})<{\rm
opt}({\cal S})]\cdot$ $\displaystyle\underset{\ \boldsymbol{z}\sim{\cal
U}(\Omega),{\boldsymbol{j}}\sim{\cal
U}(one(\boldsymbol{z})),\boldsymbol{y}\sim{\cal
U}(\boldsymbol{z}^{{\boldsymbol{j}}\leftarrow U})}{{\bf
Pr}}[F(\boldsymbol{y})=1|q_{\boldsymbol{z}}({\boldsymbol{j}})<{\rm opt}({\cal
S})]$ $\displaystyle\geq$ $\displaystyle\frac{1}{2|U|}.$

∎

######  Claim 6.

Let ${\cal S}=(S,U,E)$ be a set cover instance, and let $\ell\geq 5$. If
$F:(\\{0,1\\}^{\ell})^{n}\to\\{0,1\\}$ is a DNF and
$\underset{\boldsymbol{z}\sim{\cal
U}(\Omega)}{\mathbb{E}}[{\rm{mwidth}}_{F}(\boldsymbol{z})]\leq{\rm opt}({\cal
S})\ell/4$, then ${\rm dist}_{{\cal D}_{\ell}}(F,\Gamma_{\ell})\geq 1/(8|U|)$.

###### Proof.

If $\underset{\ \boldsymbol{y}\sim{\cal U}(\Delta_{n}^{1})}{{\bf
Pr}}[F(\boldsymbol{y})\not=1]\geq 1/(4|U|)$, then by Fact 2, we have

${\rm dist}_{{\cal D}_{\ell}}(\Gamma_{\ell},F)\geq\underset{\
\boldsymbol{y}\sim{\cal D}_{\ell}}{{\bf
Pr}}[\Gamma_{\ell}(\boldsymbol{y})\not=F(\boldsymbol{y})|\Gamma_{\ell}(\boldsymbol{y})=1]\underset{\
\boldsymbol{y}\sim{\cal D}_{\ell}}{{\bf
Pr}}[\Gamma_{\ell}(\boldsymbol{y})=1]=\frac{1}{2}\underset{\
\boldsymbol{y}\sim{\cal U}(\Delta^{1}_{n})}{{\bf
Pr}}[F(\boldsymbol{y})\not=1]\geq\frac{1}{8|U|}.$

If $\underset{\ \boldsymbol{y}\sim{\cal U}(\Delta_{n}^{1})}{{\bf
Pr}}[F(\boldsymbol{y})\not=1]<1/(4|U|)$, then by Fact 2 and 5, and Claim 5,

$\displaystyle{\rm dist}_{{\cal D}_{\ell}}(\Gamma_{\ell},F)$
$\displaystyle\geq$ $\displaystyle\underset{\ \boldsymbol{y}\sim{\cal
D}_{\ell}}{{\bf
Pr}}[\Gamma_{\ell}(\boldsymbol{y})\not=F(\boldsymbol{y})|\Gamma_{\ell}(\boldsymbol{y})=0]\underset{\
\boldsymbol{y}\sim{\cal D}_{\ell}}{{\bf Pr}}[\Gamma_{\ell}(\boldsymbol{y})=0]$
$\displaystyle=$ $\displaystyle\frac{1}{2}\underset{\ \boldsymbol{y}\sim{\cal
U}(\Delta_{n}^{0})}{{\bf Pr}}[F(\boldsymbol{y})=1]$ $\displaystyle=$
$\displaystyle\frac{1}{2}\underset{\ \boldsymbol{z}\sim{\cal
U}(\Delta^{1}_{n}),{\boldsymbol{j}}\sim{\cal U}({\rm
one}(\boldsymbol{z})),\boldsymbol{y}\sim{\cal
U}(\boldsymbol{z}^{{\boldsymbol{j}}\leftarrow U})}{{\bf
Pr}}[F(\boldsymbol{y})=1]$ $\displaystyle\geq$
$\displaystyle\frac{1}{2}\underset{\ \boldsymbol{z}\sim{\cal
U}(\Delta^{1}_{n}),{\boldsymbol{j}}\sim{\cal U}({\rm
one}(\boldsymbol{z})),\boldsymbol{y}\sim{\cal
U}(\boldsymbol{z}^{{\boldsymbol{j}}\leftarrow U})}{{\bf
Pr}}[F(\boldsymbol{y})=1|F(\boldsymbol{z})=1]\cdot\underset{\
\boldsymbol{z}\sim{\cal U}(\Delta^{1}_{n})}{{\bf Pr}}[F(\boldsymbol{z})=1]$
$\displaystyle=$ $\displaystyle\frac{1}{2}\underset{\ \boldsymbol{z}\sim{\cal
U}(\Omega),{\boldsymbol{j}}\sim{\cal U}({\rm
one}(\boldsymbol{z})),\boldsymbol{y}\sim{\cal
U}(\boldsymbol{z}^{{\boldsymbol{j}}\leftarrow U})}{{\bf
Pr}}[F(\boldsymbol{y})=1]\cdot\underset{\ \boldsymbol{z}\sim{\cal
U}(\Delta^{1}_{n})}{{\bf Pr}}[F(\boldsymbol{z})=1]$ $\displaystyle\geq$
$\displaystyle\frac{1}{2}\frac{1}{2|U|}\left(1-\frac{1}{4|U|}\right)\geq\frac{1}{8|U|}.$

∎

######  Claim 7.

Let $F$ be a size-$s$ DNF formula for $s\geq 2$ such that ${\rm dist}_{{\cal
D}_{\ell}}(F,\Gamma_{\ell})\leq 1/4$, then

$\underset{\boldsymbol{y}\sim{\cal
U}(\Omega)}{\mathbb{E}}[{\rm{mwidth}}_{F}(\boldsymbol{y})]\leq 4\log s.$

###### Proof.

First, we have

$\displaystyle\frac{3}{4}$ $\displaystyle\leq$ $\displaystyle\underset{\
\boldsymbol{y}\sim{\cal D}_{\ell}}{{\bf
Pr}}[F(\boldsymbol{y})=\Gamma_{\ell}(\boldsymbol{y})]$ $\displaystyle=$
$\displaystyle\frac{1}{2}\underset{\ \boldsymbol{y}\sim{\cal D}_{\ell}}{{\bf
Pr}}[F(\boldsymbol{y})=\Gamma_{\ell}(\boldsymbol{y})|\Gamma_{\ell}(\boldsymbol{y})=1]+\frac{1}{2}\underset{\
\boldsymbol{y}\sim{\cal D}_{\ell}}{{\bf
Pr}}[F(\boldsymbol{y})=\Gamma_{\ell}(\boldsymbol{y})|\Gamma_{\ell}(\boldsymbol{y})=0]$
$\displaystyle\leq$ $\displaystyle\frac{1}{2}\underset{\
\boldsymbol{y}\sim{\cal U}(\Delta_{n}^{1})}{{\bf
Pr}}[F(\boldsymbol{y})=1]+\frac{1}{2}.$

Therefore, ${\bf Pr}_{\boldsymbol{y}\sim{\cal
U}(\Delta^{1}_{n})}[F(\boldsymbol{y})=1]\geq 1/2.$

Let $F=T_{1}\vee T_{2}\vee\cdots\vee T_{s}$. For $y\in\Omega$, let
$\omega(y)\in[s]$ be the minimum integer such that
${\rm{mwidth}}_{F}(y)=|(T_{\omega(y)})_{\cal M}|$ and $T_{\omega(y)}(y)=1$.

Then, by (6),

$\underset{\ \boldsymbol{y}\sim{\cal U}(\Omega)}{{\bf
Pr}}[T_{i}(\boldsymbol{y})=1]=\underset{\ \boldsymbol{y}\sim{\cal
U}(\Delta^{1}_{n})}{{\bf
Pr}}[T_{i}(\boldsymbol{y})=1|F(\boldsymbol{y})=1]=\frac{\underset{\
\boldsymbol{y}\sim{\cal U}(\Delta^{1}_{n})}{{\bf
Pr}}[T_{i}(\boldsymbol{y})=1]}{\underset{\ \boldsymbol{y}\sim{\cal
U}(\Delta^{1}_{n})}{{\bf Pr}}[F(\boldsymbol{y})=1]}\leq 2^{-|(T_{i})_{\cal
M}|/2+1}.$

Now, by the concavity of $\log$,

$\displaystyle\frac{1}{2}\underset{\boldsymbol{y}\sim{\cal
U}(\Omega)}{\mathbb{E}}[{\rm{mwidth}}_{F}(\boldsymbol{y})]-1$ $\displaystyle=$
$\displaystyle\underset{\boldsymbol{y}\sim{\cal
U}(\Omega)}{\mathbb{E}}\left[\log\left(2^{{\rm{mwidth}}_{F}(\boldsymbol{y})/2-1}\right)\right]$
$\displaystyle\leq$ $\displaystyle\log\left(\underset{\boldsymbol{y}\sim{\cal
U}(\Omega)}{\mathbb{E}}\left[2^{{\rm{mwidth}}_{F}(\boldsymbol{y})/2-1}\right]\right)$
$\displaystyle=$ $\displaystyle\log\left(\sum_{i\in[s]}2^{|(T_{i})_{\cal
M}|/2-1}\underset{\ \boldsymbol{y}\sim{\cal U}(\Omega)}{{\bf
Pr}}[\omega(\boldsymbol{y})=i]\right)$ $\displaystyle\leq$
$\displaystyle\log\left(\sum_{i\in[s]}2^{|(T_{i})_{\cal M}|/2-1}\underset{\
\boldsymbol{y}\sim{\cal U}(\Omega)}{{\bf Pr}}[T_{i}(\boldsymbol{y})=1]\right)$
$\displaystyle\leq$ $\displaystyle\log\left(\sum_{i\in[s]}2^{|(T_{i})_{\cal
M}|/2-1}2^{-|(T_{i})_{\cal M}|/2+1}\right)$ $\displaystyle=$
$\displaystyle\log s.$

Therefore, $\underset{\boldsymbol{y}\sim{\cal
U}(\Omega)}{\mathbb{E}}[{\rm{mwidth}}_{F}(\boldsymbol{y})]\leq 4\log s.$ ∎

We are now ready to prove Lemma 4

###### Proof.

If ${\rm dist}_{{\cal D}_{\ell}}(F,\Gamma_{\ell})>1/4$, then the result
follows. Now suppose ${\rm dist}_{{\cal D}_{\ell}}(F,\Gamma_{\ell})\leq 1/4$.
If $s=|F|<2^{{\rm opt}({\cal S})\ell/16}$, then by Claim 7,
$\underset{\boldsymbol{y}\sim{\cal
U}(\Omega)}{\mathbb{E}}[{\rm{mwidth}}_{F}(\boldsymbol{y})]\leq 4\log s={\rm
opt}({\cal S})\ell/4$. Then by Claim 6, ${\rm dist}_{{\cal
D}_{\ell}}(F,\Gamma_{\ell})\geq 1/(8|U|).$ ∎

The proof of Theorem 3 is the same as the proof of Theorem 14 in [9]. We give
the proof for completeness.

###### Proof.

Consider the constant $\lambda$ in Lemma 1. Let $c=\lambda/6$. Suppose there
is a PAC learning algorithm ${\cal A}$ for Monotone $(\log s)$-Junta by
size-$s$ DNF with $\epsilon=1/(16n)$ that runs in time $n^{c{\log s}}$. We
show that there is $k$ such that for

$k^{\prime}=\frac{1}{2}\left(\frac{\log N}{\log\log N}\right)^{1/k},$

$(k,k^{\prime})$-Set-Cover can be solved in time $N^{5ck}\leq N^{\lambda k}$.
By Lemma 1, the result then follows.

Let ${\cal S}=(S,U,E)$ be an $N$-vertex $(k,k^{\prime})$-Set-Cover instance
where

$k=\frac{1}{2}\frac{\log\log N}{\log\log\log N}\mbox{\ and\
}k^{\prime}=\frac{1}{2}\left(\frac{\log N}{\log\log N}\right)^{1/k}.$

Consider the following algorithm ${\cal B}$

  1. 1.

Input ${\cal S}=(S,U,E)$ an instance for $(k,k^{\prime})$-Set-Cover .

  2. 2.

Construct $\Gamma_{5}$ and ${\cal D}_{5}$.

  3. 3.

Run ${\cal A}$ using $\Gamma_{5}$ and ${\cal D}_{5}$ with $s=2^{5k}$ and
$n=N$. If it runs more than $N^{5ck}$ steps, then output No .

  4. 4.

Let $F$ be the output DNF.

  5. 5.

If $|F|>s$ then output No .

  6. 6.

Estimate $\eta={\rm dist}_{{\cal D}_{5}}(F,\Gamma_{5})$.

  7. 7.

If $\eta\leq\frac{1}{16N}$, output Yes , otherwise output No .

The running time of this algorithm is $N^{5ck}\leq N^{\lambda k}$. Therefore,
it is enough to prove the following

######  Claim 8.

Algorithm ${\cal B}$ solves $(k,k^{\prime})$-Set-Cover .

###### Proof.

Yes case: Let ${\cal S}=(S,U,E)$ be a $(k,k^{\prime})$-Set-Cover instance and
${\rm opt}({\cal S})\leq k$. Then, $size(\Gamma_{5})\leq 2^{5\cdot{\rm
opt}({\cal S})}\leq 2^{5k}=s$, and by Fact 3, $\Gamma_{5}$ is Monotone $\log
s$-Junta. Therefore, w.h.p., algorithm ${\cal A}$ learns $\Gamma_{5}$ and
outputs a DNF that is $\eta=1/(16N)$ close to the target with respect to
${\cal D}_{5}$. Since ${\cal B}$ terminates ${\cal A}$ after $N^{5ck}$ time,
we only need to prove that ${\cal A}$ runs at most $N^{5ck}$ time.

The running time of ${\cal A}$ is

$n^{c\log s}=N^{c\log s}\leq N^{5ck}.$

No Case: Let ${\cal S}=(S,U,E)$ be a $(k,k^{\prime})$-Set-Cover instance and
${\rm opt}({\cal S})>k^{\prime}$. By Lemma 4, any DNF, $F$, of size
$|F|<2^{5k^{\prime}/16}$ satisfies ${\rm dist}_{{\cal
D}_{5}}(F,\Gamma_{5})\geq 1/(8|U|)$. First, we have, for large $N$

$k^{\prime}=\frac{1}{2}\left(\frac{\log N}{\log\log N}\right)^{1/k}>32k.$

Therefore, any DNF, F, of size $|F|<2^{10k}$ satisfies ${\rm dist}_{{\cal
D}_{5}}(F,\Gamma_{5})\geq 1/(8|U|)$.

We have $2^{10k}>s$. So, ${\cal B}$ either runs more than $N^{5ck}$ steps and
then outputs No in step 3 or outputs a DNF of size more than $s$ and then
outputs No in step 4 or outputs a DNF of size at most $s$ with ${\rm
dist}_{{\cal D}_{5}}(F,\Gamma_{5})\geq 1/(8|U|)>1/(8N)>1/(16N)$ and outputs No
in step 6. ∎

∎

## References

  * [1] Michael Alekhnovich, Mark Braverman, Vitaly Feldman, Adam R. Klivans, and Toniann Pitassi.  The complexity of properly learning simple concept classes.  J. Comput. Syst. Sci., 74(1):16–34, 2008.  doi:10.1016/j.jcss.2007.04.011.
  * [2] Chris Calabro, Russell Impagliazzo, Valentine Kabanets, and Ramamohan Paturi.  The complexity of unique k-sat: An isolation lemma for k-cnfs.  J. Comput. Syst. Sci., 74(3):386–393, 2008.  doi:10.1016/j.jcss.2007.06.015.
  * [3] Holger Dell, Thore Husfeldt, Dániel Marx, Nina Taslaman, and Martin Wahlen.  Exponential time complexity of the permanent and the tutte polynomial.  ACM Trans. Algorithms, 10(4):21:1–21:32, 2014.  doi:10.1145/2635812.
  * [4] Andrzej Ehrenfeucht and David Haussler.  Learning decision trees from random examples.  Inf. Comput., 82(3):231–246, 1989.  doi:10.1016/0890-5401(89)90001-1.
  * [5] Thomas R. Hancock, Tao Jiang, Ming Li, and John Tromp.  Lower bounds on learning decision lists and trees.  Inf. Comput., 126(2):114–122, 1996.  doi:10.1006/inco.1996.0040.
  * [6] Lisa Hellerstein, Devorah Kletenik, Linda Sellie, and Rocco A. Servedio.  Tight bounds on proper equivalence query learning of DNF.  In COLT 2012 - The 25th Annual Conference on Learning Theory, June 25-27, 2012, Edinburgh, Scotland, pages 31.1–31.18, 2012.  URL: http://proceedings.mlr.press/v23/hellerstein12/hellerstein12.pdf.
  * [7] Russell Impagliazzo and Ramamohan Paturi.  On the complexity of k-sat.  J. Comput. Syst. Sci., 62(2):367–375, 2001.  doi:10.1006/jcss.2000.1727.
  * [8] Russell Impagliazzo, Ramamohan Paturi, and Francis Zane.  Which problems have strongly exponential complexity?  J. Comput. Syst. Sci., 63(4):512–530, 2001.  doi:10.1006/jcss.2001.1774.
  * [9] Caleb Koch, Carmen Strassle, and Li-Yang Tan.  Superpolynomial lower bounds for decision tree learning and testing.  CoRR, abs/2210.06375, 2022.  arXiv:2210.06375, doi:10.48550/arXiv.2210.06375.
  * [10] Bingkai Lin.  A simple gap-producing reduction for the parameterized set cover problem.  In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, volume 132 of LIPIcs, pages 81:1–81:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.  doi:10.4230/LIPIcs.ICALP.2019.81.
  * [11] Craig A. Tovey.  A simplified np-complete satisfiability problem.  Discret. Appl. Math., 8(1):85–89, 1984.  doi:10.1016/0166-218X(84)90081-7.
  * [12] Leslie G. Valiant.  A theory of the learnable.  Commun. ACM, 27(11):1134–1142, 1984.  doi:10.1145/1968.1972.