text:
\section{Introduction}

For any function $f:\{-1,1\}^n\to\R$, there exist unique real coefficients $\{\hat{f}(S)\}_{S\subseteq\{1,\ldots,n\}}$ such that
\begin{equation}
\forall \ x\in\{-1,1\}^n, \qquad f(x) = \sum_{S\subseteq\{1,\ldots,n\}} \hat{f}(S) w_S(x),
\end{equation}
where the Walsh functions $w_S:\{-1,1\}^n\to\{-1,1\}$ are defined by $w_S(x)=\prod_{i\in S}x_i$. We say that the function $f$ has degree at most $d\in\{0,1,\ldots,n\}$ if $\hat{f}(S)=0$ for all sets $S$ with $|S|>d$.

\vspace{-1.4mm}
\subsection{Learning functions on the hypercube} Let $\mathscr{F}$ be a class of functions on the discrete hypercube of dimension $n$. The learning problem for the class $\mathscr{F}$ can be described as follows. Consider an unknown function $f\in\mathscr{F}$. Given access to \emph{examples} $(X_1,f(X_1)), \ldots, (X_Q, f(X_Q))$, the goal is to algorithmically construct a \emph{hypothesis function} $h:\{-1,1\}^n\to\R$ which effectively approximates $f$. Different access models to examples give rise to concrete versions of the learning problem. The two most standard such models are the \emph{query} model, in which the algorithm can sequentially request the values of $f$ at any $Q$-tuple of points $X_1,\ldots,X_Q$ from $\{-1,1\}^n$, and the \emph{random example} model, in which the data points $X_1,\ldots,X_Q$ are generated uniformly and independently from $\{-1,1\}^n$. In the query model, the goal is to construct a function $h$ satisfying $\|h-f\|^2_{L_2}\leq\varepsilon$ whereas in the random example model, the desired output is a \emph{random} function $h$ satisfying $\|h-f\|^2_{L_2}\leq\varepsilon$ with probability at least $1-\delta$, where $\varepsilon, \delta \in[0,1)$ are pre-fixed accuracy and confidence parameters respectively. The least number $Q$ of examples required to solve the learning problem in each case is called the \emph{query complexity} of the model and shall be denoted by $\mathsf{Q}(\mathscr{F},\varepsilon)$ for the query model and\mbox{ by $\mathsf{Q}_r(\mathscr{F},\varepsilon,\delta)$ for the random example model.}

The query complexity of learning problems has been studied extensively for various classes $\mathscr{F}$ of functions on the discrete hypercube (see \cite{Man94, O'Do14}). One of the first rigorous results of this kind is the \emph{Low-Degree Algorithm} of Linial, Mansour and Nisan \cite{LMN93}, who considered the class
\begin{equation} \label{eq:Fnd}
\mathscr{F}_{n,d} \stackrel{\mathrm{def}}{=} \big\{f:\{-1,1\}^n\to[-1,1]: \ f \mbox{ has degree at most } d\big\}
\end{equation}
and showed the estimate $\mathsf{Q}_r(\mathscr{F}_{n,d},\varepsilon,\delta) \leq \frac{2n^d}{\varepsilon}\log(\tfrac{2n^d}{\delta})$ for any $\varepsilon,\delta\in(0,1)$. In the recent work \cite{EI21}, which followed an intermediate $O_{d,\varepsilon,\delta}(n^{d-1}\log n)$ asymptotic\footnote{We shall use the standard asymptotic notation throughout the article. For $a,b>0$, we write $a=O(b)$ if there exists a universal constant $c>0$ such that $a\leq cb$. Moreover, we shall write $a=\Theta(b)$ for $a=O(b)$ and $b=O(a)$. We shall also write $O_\xi(\cdot)$, $\Theta_\psi(\cdot)$ to indicate that the implicit constants depend on $\xi$ or $\psi$ respectively.} improvement in \cite{IRRRY21}, it was shown that this classical estimate is largely suboptimal as $n\to\infty$ and in fact
\begin{equation} \label{eq:EI}
\mathsf{Q}_r(\mathscr{F}_{n,d},\varepsilon,\delta) \leq \min\left\{ \frac{\exp(C d^{3/2}\sqrt{\log d})}{\varepsilon^{d+1}},\frac{4dn^d}{\varepsilon}\right\} \log\left(\frac{n}{\delta}\right)
\end{equation}

The first goal of the present paper is to investigate lower bounds for the query complexity, which in particular imply that \eqref{eq:EI} is asymptotically optimal as $n\to\infty$, that is
\begin{equation} \label{eq:equiv}
\mathsf{Q}_r(\mathscr{F}_{n,d},\varepsilon,\delta) = \Theta_{d,\varepsilon,\delta}(\log n).
\end{equation}
Consider the class
\begin{equation} \label{eq:Bnd}
\mathscr{B}_{n,d} \stackrel{\mathrm{def}}{=} \big\{f:\{-1,1\}^n\to\{-1,1\}: \ f \mbox{ has degree at most } d\big\}\subset \mathscr{F}_{n,d}.
\end{equation}
We will prove the following lower estimate for the complexities of this class.

\begin{theorem} \label{thm:lb}
For any $n\in\mathbb{N}$, $d\in\{1,\ldots,n\}$,  $\varepsilon\in[0,1)$ and $\delta\in(0,1)$, we have
\begin{equation} \label{eq:EIS-det}
\mathsf{Q}(\mathscr{B}_{n,d},\varepsilon) \geq \max\left\{(1-\sqrt{\varepsilon})2^{d-2}\log_2 n - (d+1)2^{d-2},  d\log_2\left(\frac{n}{d}\right)\right\}
\end{equation}
and
\begin{equation} \label{eq:EIS}
\mathsf{Q}_r(\mathscr{B}_{n,d},\varepsilon,\delta) \geq \max\left\{(1-\sqrt{\varepsilon})2^{d-2}\log_2 n - (d+1)2^{d-2},  d\log_2\left(\frac{n}{d}\right)\right\}+\log_2(1-\delta).
\end{equation}
\end{theorem}
\noindent The equivalence \eqref{eq:equiv} now follows due to the inequality $\mathsf{Q}_r(\mathscr{B}_{n,d},\varepsilon,\delta)\leq\mathsf{Q}_r(\mathscr{F}_{n,d},\varepsilon,\delta)$. The tools used in the proof of Theorem \ref{thm:lb} will be described in Section \ref{sec:1.3}.

The second goal of this paper is to show a more robust version of the upper bound \eqref{eq:EI} that applies to different concept classes $\mathscr{F}$ which are not necessarily of bounded degree.  In order to present this result we shall need some terminology (see also \cite[Chapter~3]{O'Do14}).  If $t\geq0$, we say that the Fourier spectrum of a function $f:\{-1,1\}^n\to\R$ is $t$-concentrated up to degree $d$ if
\begin{equation} \label{tail}
\sum_{|S|>d}\hat{f}(S)^2\leq t.
\end{equation}
More generally, given a family $\mathscr{S}$ of subsets of $\{1,\ldots,n\}$ we say that the spectrum of $f$ is $\eta$-concentrated on $\mathscr{S}$ if
\begin{equation}
\sum_{S\notin\mathscr{S}} \hat{f}(S)^2 \leq \eta.
\end{equation}
Our main upper bound for learning is the following theorem.

\begin{theorem} \label{thm:upper}
Fix $n,m\in\mathbb{N}$, $d\in\{1,\ldots,n\}$ and $t,\eta\in[0,1)$.  Let $\mathscr{F}$ be a class of bounded functions $f:\{-1,1\}^n\to[-1,1]$ such that the Fourier spectrum of any $f\in\mathscr{F}$ is $t$-concentrated up to degree $d$ and is $\eta$-concentrated on a family $\mathscr{S}(f)$ of subsets of $\{1,\ldots,n\}$ satisfying $\#\mathscr{S}(f)\leq m$. Then,
\begin{equation} \label{eq:upper}
\forall \ \varepsilon,\delta\in(0,1),\qquad \mathsf{Q}_r(\mathscr{F},\eta+t+\varepsilon,\delta) \leq \left\lceil\frac{18m}{\varepsilon}\log\left(\frac{2}{\delta} \sum_{r=0}^d\binom{n}{r}\right)\right\rceil.
\end{equation}
\end{theorem}

In Remark \ref{rem:newproof} below we will see how this statement implies the estimate \eqref{eq:EI} of \cite{EI21}.

\subsection{Fourier concentration and learning upper bounds} \label{sec:upper} In this section we shall present concrete applications of Theorem \ref{thm:upper} for various concept classes $\mathscr{F}$.  We start with the class of approximate juntas of a given degree. Recall that a function \mbox{$f:\{-1,1\}^n\to\R$} is called a $(k,\eta)$-junta if there exists a subset $\sigma\subseteq\{1,\ldots,n\}$ with $|\sigma|\leq k$ and a map \mbox{$g:\{-1,1\}^n\to\R$} depending only on the variables $(x_i)_{i\in\sigma}$ such that $\|f-g\|^2_{L_2}\leq \eta$. Consider the class
\begin{equation}
\mathscr{J}_{n,k,\eta} = \big\{f:\{-1,1\}^n\to[-1,1]: \ f \mbox{ is a } (k,\eta)\mbox{-junta} \big\}.
\end{equation}
We shall prove the following estimate on the randomized query complexity of $\mathscr{F}_{n,d}\cap\mathscr{J}_{n,k,\eta}$.

\begin{corollary} \label{thm:junta}
In the setting above, for $\varepsilon,\delta\in(0,1)$ we have
\begin{equation} \label{eq:junta}
\mathsf{Q}_r\big(\mathscr{F}_{n,d} \cap \mathscr{J}_{n,k,\eta}, 2\eta+\varepsilon,\delta\big) \leq \left\lceil \frac{18}{\varepsilon} \sum_{r=0}^{\min\{d,k\}} \binom{k}{r} \log\left(\frac{2}{\delta}\sum_{r=0}^{\min\{d,k\}} \binom{n}{r}\right) \right\rceil.
\end{equation}
In particular, choosing $d=n$, we get
\begin{equation}
\mathsf{Q}_r\big(\mathscr{J}_{n,k,\eta}, 2\eta+\varepsilon,\delta\big) \leq  \frac{2^{k+5}}{\varepsilon} \log\left(\frac{2}{\delta}\sum_{r=0}^{k} \binom{n}{r}\right).
\end{equation}
\end{corollary}

Corollary \ref{thm:junta} can be concretely applied in view of the large available literature on junta theorems in Boolean analysis.  To motivate a first application along these lines, observe that the upper bound \eqref{eq:EI} of \cite{EI21} differs from that of \cite{LMN93} in its dependence on $\varepsilon$ as $\varepsilon\to0^+$.  While we do not know whether the $\varepsilon^{-d-1}$ asymptotic behavior is needed to learn $\mathscr{F}_{n,d}$, Corollary \ref{thm:junta} combined with a  structural result of Nisan and Szegedy \cite{NS94} gives the following upper bound for the complexity of $\mathscr{B}_{n,d}$, alas with a somewhat worse dependence on $d$.

\begin{corollary} \label{prop:boolean}
For any $n\in\mathbb{N}$, $d\in\{1,\ldots,n\}$ and $\varepsilon,\delta\in(0,1)$, we have
\begin{equation}
\mathsf{Q}_r(\mathscr{B}_{n,d},\varepsilon,\delta) \leq  \frac{36\cdot d2^{d^2}}{\varepsilon} \log\left(\frac{n}{\delta}\right).
\end{equation}
\end{corollary}

Combining Theorem \ref{thm:upper} with a deep junta theorem of Dinur, Friedgut, Kindler and O'Donnell \cite{DFKO07}, we will deduce that bounded functions which are sufficiently close to polynomials of degree $d$ can be learned from $O_d(\log n)$ samples. For $t\geq0$, consider the class $\mathscr{F}_{n,d}(t)$ consisting of functions $f:\{-1,1\}^n\to[-1,1]$ whose spectra are $t$-concentrated up to degree $d$.
In other words, $\mathscr{F}_{n,d}(t)$ consists of all bounded functions which are $\sqrt{t}$-close (in $L_2$) to a polynomial of degree at most $d$. Corollary \ref{thm:junta} has the following consequence.

\begin{corollary} \label{cor:robust}
There exists a universal constant $C>0$ such that the following holds. For any $n\in\mathbb{N}$, $d\in\{1,\ldots,n\}$, $t\in[0,1)$ and $\eta\geq\frac{C d^2{\log d}}{{\log(1/t)}}$, we have
\begin{equation} \label{eq:robust}
\forall \ \varepsilon,\delta\in(0,1),\qquad \mathsf{Q}_r\big(\mathscr{F}_{n,d}(t), \eta+\varepsilon,\delta\big) \leq \frac{2^{Cd^2}}{\eta^{2d}\varepsilon}\log\left(\frac{n}{\delta}\right).
\end{equation}
\end{corollary}

It is worth emphasizing that as $t\to0^+$, we can also take $\eta=\eta(t)\to0^+$ in the statement above. Corollary \ref{cor:robust} is a robust version of the main theorem of \cite{EI21}. On the one hand, the method of \cite{EI21} seems unfit to provide estimates for the complexity of $\mathscr{F}_{n,d}(t)$ as it uses the Bohnenblust--Hille inequality \cite{DMP19}, which heavily relies on the fact that the unknown function is a bounded polynomial. On the other hand (see also Remark \ref{rem:newproof}), Corollary \ref{cor:robust} gives a worse estimate on the complexity of $\mathscr{F}_{n,d}=\mathscr{F}_{n,d}(0)$ in terms of $d, \varepsilon$ than the bound \eqref{eq:EI} of \cite{EI21}.

To the best of our knowledge, Corollary \ref{cor:robust} is the best known upper bound for the randomized query complexity of the class $\mathscr{F}_{n,d}(t)$ for $t>0$ after the Low-Degree Algorithm of \cite{LMN93} which gives the  estimate $\mathsf{Q}_r(\mathscr{F}_{n,d}(t),t+\varepsilon,\delta) \leq \frac{2n^d}{\varepsilon} \log\left(\frac{2n^d}{\delta}\right)$. It remains an interesting problem to understand whether one can sharpen the dependence on $d$ of the lower bound for $\eta$ in Corollary \ref{cor:robust}. Specifically for the case of Boolean functions, the implicit dependence of $\eta$ on $t, d$ can be exponentially improved due to an important junta theorem of Bourgain \cite{Bou02}. For $t>0$, denote by $\mathscr{B}_{n,d}(t)$ the class of all Boolean functions $f:\{-1,1\}^n\to\{-1,1\}$ satisfying \eqref{tail}.

\begin{corollary} \label{cor:robust-boolean}
There exists a universal constant $C>0$ such that the following holds. For any $n\in\mathbb{N}$, $d\in\{1,\ldots,n\}$, $t\in[0,1)$ and $\eta\geq t^{1+o(1)}d^{\frac{1}{2}+o(1)}$, we have\footnote{The explicit nature of the $o(1)$-terms in the exponents will be made precise in Section \ref{sec:3}.}
\begin{equation}
\forall \ \varepsilon,\delta\in(0,1),\qquad \mathsf{Q}_r\big(\mathscr{B}_{n,d}(t), \eta+\varepsilon,\delta\big) \leq \frac{2^{Cd^2}}{\varepsilon}\log\left(\frac{n}{\delta}\right).
\end{equation}
\end{corollary}

Finally, we present a concrete application of Corollary \ref{cor:robust-boolean} to Boolean functions which can be represented by constant depth circuits. We refer to \cite[Chapter~4]{O'Do14} for the relevant definitions. For readers which are unfamiliar with this class, we just point out that DNF formulas, i.e.~functions which are representable as logical $\lor$ of terms, each of which is a logical $\land$ of variables $x_i$ or their negations $\lnot x_i$, are circuits of depth 2. Similarly, CNF formulas, in which the roles of $\lor$ and $\land$ are reversed, are also circuits of depth 2. Corollary \ref{cor:robust-boolean} combined with estimates on the Fourier concentration of constant depth circuits \cite{Has87,LMN93,Has01} has the following consequence.

\begin{corollary} \label{cor:circuits}
Let $\mathscr{C}_{n,d,s}$ be the class of all Boolean functions on $\{-1,1\}^n$ computable by a depth-$d$ circuit of size $s>1$. Then, for every $\varepsilon,\delta\in(0,1)$, we have
\begin{equation}
\mathsf{Q}_r(\mathscr{C}_{n,d,s},\varepsilon,\delta) \leq \exp\big(O(\log (s/\varepsilon))^{d-2} \cdot \log s \cdot \log(1/\varepsilon)\big) \log\left(\frac{n}{\delta}\right).
\end{equation}
\end{corollary}

Learning constant depth circuits (also known as $\mathsf{AC}^0$ circuits) in quasi-polynomial time is the main focus of the seminal work \cite{LMN93} of Linial, Mansour and Nisan which prompted them to design the Low-Degree Algorithm. Moreover, it is known (see \cite{Kha93}) that quasi-polynomial time is also \emph{necessary} to learn this class, conditionally on some standard cryptographic assumptions. The contribution of Corollary \ref{cor:circuits} is the fact that the query complexity of this learning problem is (exponentially) smaller than the corresponding running time \cite{LMN93} for large enough $n$. Choosing $d=2$, Corollary \ref{cor:circuits} implies that DNF formulas of polynomial size can be learned from polynomially many samples up to constant error (see \cite{KS04} and the references therein for the long-standing open problem of understanding the running time required to learn DNF). It is worth emphasizing that the reason Corollary \ref{cor:circuits} follows from Corollary \ref{cor:robust-boolean} is that $\mathsf{AC}^0$ circuits have strong enough Fourier concentration. It remains an interesting problem to understand whether Corollary \ref{cor:robust-boolean} can be boosted to encapsulate classes of Boolean functions with weaker concentration such as linear threshold functions or functions of many hyperplanes  \cite{BKS99,Per21}.

\subsection{Metric entropy and learning lower bounds} \label{sec:1.3} Let $(\mathcal{X}, d_\mathcal{X})$ be a metric space and $\varepsilon>0$. A subset $\mathcal{P} \subseteq \mathcal{X}$ is an $\varepsilon$-packing of $\mathcal{X}$ if for any $p\neq p'\in\mathcal{P}$, we have $d_\mathcal{X}(p,p')>\varepsilon$. The largest size of an $\varepsilon$-packing is called the \emph{packing number} of $\mathcal{X}$ and is denoted by $\mathsf{M}(\mathcal{X},d_\mathcal{X},\varepsilon)$. A subset $\mathcal{C}\subseteq\mathcal{X}$ is an $\varepsilon$-cover of $\mathcal{X}$ if for any $q\in\mathcal{X}$, there exists some $p\in\mathcal{C}$ with $d_\mathcal{X}(p,q)\leq \varepsilon$. The smallest size of an $\varepsilon$-cover is called the \emph{covering number} of $\mathcal{X}$ and is denoted by $\mathsf{N}(\mathcal{X},d_\mathcal{X},\varepsilon)$.  The quantity $\log_2\mathsf{N}(\mathcal{X},d_\mathcal{X},\varepsilon)$ is called the $\varepsilon$-\emph{metric entropy} of $\mathcal{X}$.  It is well known (see \cite[Lemma 4.2.8]{Ver18}) that packing and covering numbers are closely related via the elementary inequalities
\begin{equation}
\forall \ \varepsilon>0, \qquad \mathsf{M}(\mathcal{X},d_\mathcal{X},2\varepsilon)\leq \mathsf{N}(\mathcal{X},d_\mathcal{X},\varepsilon) \leq \mathsf{M}(\mathcal{X},d_\mathcal{X},\varepsilon).
\end{equation}

The pertinence of metric entropy in the context of learning lower bounds stems from the classical observation that concept classes with large covering (or packing) numbers cannot be efficiently learned from few queries (see, for instance, the works \cite{BEHW89,LMR91,DKRZ94}). In our setting, we shall need the following concrete estimate which we could not locate in the literature.

\begin{proposition} \label{prop:QM}
Fix $n\in\mathbb{N}$ and let $\mathscr{B}$ be a class of Boolean functions on $\{-1,1\}^n$. Then,
\begin{equation} \label{det}
\forall \ \varepsilon>0, \qquad \mathsf{Q}(\mathscr{B},\varepsilon) \geq \log_2 \mathsf{M}(\mathscr{B},\|\cdot\|_{L_2},2\sqrt{\varepsilon})
\end{equation}
and
\begin{equation} \label{rand}
\forall \ \varepsilon>0 \mbox{, } \forall \ \delta\in(0,1), \qquad \mathsf{Q}_r(\mathscr{B},\varepsilon,\delta) \geq \log_2 \mathsf{M}(\mathscr{B},\|\cdot\|_{L_2},2\sqrt{\varepsilon})+\log_2(1-\delta),
\end{equation}
where $\|\phi-\psi\|_{L_2} = \sqrt{\mathbb{E}_x (\phi(x)-\psi(x))^2}$ is the $L_2$-norm with respect to the uniform probability measure.
\end{proposition}

The class $\mathscr{B}_{n,d}$ defined in \eqref{eq:Bnd} contains all Walsh functions $\{w_S\}_{|S|\leq d}$ and thus
\begin{equation} \label{eq:lb-from-walsh}
\forall \ \varepsilon \in(0,\sqrt{2}), \qquad \mathsf{M}(\mathscr{B}_{n,d},\|\cdot\|_{L_2},\varepsilon) \geq \sum_{k=0}^d \binom{n}{k} \geq \frac{n^d}{d^d},
\end{equation}
as $\|w_S-w_T\|_{L_2} = \sqrt{2}$ for any $S\neq T$. Combining this simple lower bound with Proposition \ref{prop:QM} we already deduce the asymptotic sharpness of \eqref{eq:EI} as $n\to\infty$. In order to derive a sharper estimate for $\mathsf{Q}(\mathscr{F}_{n,d},\varepsilon)$ as a function of the degree $d$, we shall prove the following improved lower bound packing numbers of $\mathscr{B}_{n,d}$ along with a matching upper bound for the metric entropy of $\mathscr{F}_{n,d}$.

\begin{theorem} \label{thm:ent}
Fix $n\in\mathbb{N}$,  $d\in\mathbb{N}$ with $d\leq \log_2n$ and $\varepsilon\in(0,1)$. Then, we have
\begin{equation} \label{eq:ent-lb}
\log_2\mathsf{M}(\mathscr{B}_{n,d},\|\cdot\|_{L_2},2\varepsilon) \geq (1-\varepsilon)2^{d-2}\log_2 n - (d+1)2^{d-2}
\end{equation}
Moreover,
\begin{equation} \label{eq:ent-ub}
\log_2 \mathsf{N}(\mathscr{F}_{n,d},\|\cdot\|_{L_2},\varepsilon) \leq \frac{2^{Cd}}{\varepsilon^4} \log n + \kappa(d,\varepsilon),
\end{equation}
where $C>0$ is a universal constant and $\kappa(d,\varepsilon)>0$ depends only on $d$ and $\varepsilon$.
\end{theorem}

\begin{proof} [Proof of Theorem \ref{thm:lb}]
Inequality \eqref{eq:EIS-det} is a direct consequence of \eqref{det}, \eqref{eq:lb-from-walsh} and \eqref{eq:ent-lb}, while \eqref{eq:EIS} follows from \eqref{rand}, \eqref{eq:lb-from-walsh} and \eqref{eq:ent-lb}.
\end{proof}

 Having presented Theorem \ref{thm:ent}, some observations related to the implicit dependencies in \eqref{eq:equiv} are in order. In \cite{EI21} it was shown that
\begin{equation} \label{eq:EI2}
\mathsf{Q}_r(\mathscr{F}_{n,d},\varepsilon,\delta) \leq \frac{e^8 d^2}{\varepsilon^{d+1}} (B_d^{\{\pm 1\}})^{2d} \log\left(\frac{n}{\delta}\right),
\end{equation}
where $B_d^{\{\pm 1\}}$ is an important approximation theoretic parameter called the \emph{Bohnenblust--Hille} constant of the hypercube (see \cite{BH31,DS14}). While it is widely believed that $B_d^{\{\pm 1\}}$ grows at most polynomially in $d$, the best known upper bound due to \cite{DMP19} states that $B_d^{\{\pm 1\}}\leq \exp(C\sqrt{d\log d})$ for some universal constant $C>0$ which, combined with \eqref{eq:EI2},  leads to \eqref{eq:EI}. A polynomial bound on $B_d^{\{\pm1\}}$ combined with \eqref{eq:EI2} would almost match, up to a logarithmic term in the exponent, the asymptotic behavior as $d\to\infty$ of the lower bound \eqref{eq:EIS} of Theorem \ref{thm:lb}. We mention at this point that we are not aware of any non-constant (as $d\to\infty$) lower bound for the constant $B_d^{\{\pm1\}}$.

The existence of a large separated set attaining the lower bound \eqref{eq:ent-lb} is proven via a probabilistic construction of random decision trees with prescribed depth. On the other hand, the upper bound \eqref{eq:ent-ub} is a consequence of the deep junta theorem of  \cite{DFKO07} but, to the extent of our knowledge, had not been previously observed in the literature. It is quite surprising that while $\mathscr{F}_{n,d}$ lies in a $O_d(n^d)$-dimensional space, its metric entropy is logarithmic in the dimension of this space rather than polynomial. The reason for this is the strong restriction that $\mathscr{F}_{n,d}$ consists of functions which are bounded in $L_\infty$-norm yet it is endowed with the Hilbertian $L_2$-metric. The existence of such \emph{small nets} is often useful in theoretical computer science and probability theory, in particular in the derandomization literature \cite{Mat96,RS10,KZ20} and in the study of suprema of stochastic processes \cite[Chapters 7-8]{Ver18}.

\subsection{Exact learning} Having established reasonable bounds on the number of queries required to learn a function in $\mathscr{F}_{n,d}$ up to error $\varepsilon>0$, we proceed to investigate the exact case $\varepsilon=0$. As it turns out, the number of random queries required to learn a function $f\in\mathscr{F}_{n,d}$ up to a constant error $\varepsilon\in(0,1)$ using the classical Low-Degree Algorithm \cite{LMN93} is in fact the same (up to constants depending only on $d$) as the number of queries required to \emph{exactly} learn the concept class $\mathscr{F}_{n,d}$. Formally, our results is this setting are summarized in the following theorem.

\begin{theorem} \label{thm:exact}
Fix $n\in\mathbb{N}$,  $d\in\{1,\ldots,n\}$ and $\delta\in(0,1)$. Then,
\begin{equation} \label{eq:exact}
\mathsf{Q}(\mathscr{F}_{n,d},0) = \sum_{j=0}^d \binom{n}{j}
\end{equation}
and there exists a universal constant $C>0$ such that
\begin{equation} \label{eq:e=0}
\mathsf{Q}_r(\mathscr{F}_{n,d},0,\delta) \leq Cd2^d n^d \log\left(\frac{n}{\delta}\right).
\end{equation}
\end{theorem}

\subsection*{Structure of the paper} In Section \ref{sec:2}, we prove our main lower bounds for learning, namely Proposition \ref{prop:QM} and Theorem \ref{thm:ent}. In Section \ref{sec:3}, we prove Theorem \ref{thm:upper} and deduce from it the Corollaries of Section \ref{sec:upper}. Finally, in Section \ref{sec:4}, we prove Theorem \ref{thm:exact} on exact learning.

\subsection*{Acknowledgements} We are grateful to Roman Vershynin for providing many helpful pointers to the literature and Srinivasan Arunachalam for constructive feedback.

\section{Metric entropy and query complexity} \label{sec:2}

We start by formalizing the concepts introduced earlier. A \emph{learning algorithm} on $\{-1,1\}^n$ using $Q$ queries is a mapping $H:\left(\{-1,1\}^n\times\R\right)^Q\to L_2(\{-1,1\}^n)$ which, given input of the form $(X_1,f(X_1)), \ldots, (X_Q,f(X_Q))$ produces a hypothesis function for $f$. In this terminology,  the randomized query complexity $\mathsf{Q}_r(\mathscr{F},\varepsilon,\delta)$ of a class of functions $\mathscr{F}$ on the hypercube is the smallest $Q\in\mathbb{N}$ for which there exists a learning algorithm $H$ with the following property:
\begin{equation} \label{eq:dQr}
\forall \ f\in\mathscr{F},\qquad \mathbb{P}_{X_1,\ldots,X_Q\in\{-1,1\}^n} \Big\{\big\| H\big((X_1,f(X_1)),\ldots,(X_Q,f(X_Q))\big) - f\big\|_{L_2}^2 \leq \varepsilon\Big\} \geq 1-\delta.
\end{equation}
In the case of non-randomized algorithms,  we need to ensure that the query points are chosen consistently with respect to the previous data.  In other words,  $X_1$ is always a fixed point on the hypercube and for any $q\geq2$,  there exists a function $\varphi_q:(\{-1,1\}^n\times\R)^{q-1}\to\{-1,1\}^n$ associated to $H$ determining the $q$-th query point as a function of the previous data $X_1,\ldots,X_{q-1}$ and the values $y_1,\ldots,y_{q-1}$ of the unknown function on these points.  Given a learning algorithm $H$ and an unknown function $f\in\mathscr{F}$, we shall denote by $X_1[f], X_2[f],\ldots$ the sequence of points that $H$ queries in order to construct a hypothesis function for $f$. In this terminology,  the deterministic query complexity of the class $\mathscr{F}$ is the least $Q\in\mathbb{N}$ for which there exists a learning algorithm $H$ using $Q$ queries satisfying the following property:
\begin{equation} \label{eq:dQ}
\forall \ f\in\mathscr{F}, \qquad  \big\| H\big(\big(X_1[f],f(X_1[f])\big),\ldots,\big(X_Q[f],f(X_Q[f])\big)\big) - f\big\|_{L_2}^2 \leq \varepsilon.
\end{equation}

Having properly defined these notions, we may proceed to the proof of Proposition \ref{prop:QM}. The argument relies on an information-theoretic consideration: given samples $X_1,\ldots,X_Q$, the outputs $f(X_1),\ldots,f(X_Q)$ provide $Q$ bits of information for $f$ and thus cannot distinguish more than $\log_2Q$ functions  which are reasonably far apart.

\begin{proof} [Proof of Proposition \ref{prop:QM}]
Let $M=\mathsf{M}(\mathscr{B},\|\cdot\|_{L_2},2\sqrt{\varepsilon})$ and consider $f_1,\ldots,f_M\in\mathscr{B}$ with $\|f_i-f_j\|_{L_2} > 2\sqrt{\varepsilon}$ for all $i\neq j$.  We start with the lower bound \eqref{det} in the deterministic case.  Denote by $Q=\mathsf{Q}(\mathscr{B},\varepsilon)$ and let $X_1[f],X_2[f],\ldots,X_Q[f]$ be samples satisfying \eqref{eq:dQ} for some learning algorithm $H$ and all functions $f$ in the class $\mathscr{B}$. Consider the set
\begin{equation}
\Sigma \stackrel{\mathrm{def}}{=} \big\{ \big( f_i(X_1[f_i]),\ldots,f_i(X_Q[f_i]) \big) : \ i=1,\ldots,M\big\}.
\end{equation}
\noindent {\it Claim.} $|\Sigma| = M$.
\smallskip

\noindent {\it Proof.} Clearly $|\Sigma|\leq M$. If $|\Sigma|<M$, then there exist $i\neq j\in\{1,\ldots,M\}$ for which we have
\begin{equation} \label{eq:coincide}
\forall \ k\in\{1,\ldots,Q\},\qquad f_i(X_k[f_i]) = f_j(X_k[f_j]).
\end{equation}
As $X_1[f_i]=X_1[f_j]\stackrel{\mathrm{def}}{=} X_1$ by definition of $H$,  \eqref{eq:coincide} gives $f_i(X_1)=f_j(X_1)$ which then, by consistency of the algorithm, implies that $X_2[f_i]=X_2[f_j]\stackrel{\mathrm{def}}{=} X_2$. Continuing iteratively, we deduce that $X_k[f_i]=X_k[f_j]\stackrel{\mathrm{def}}{=} X_k$ for every $k\in\{1,\ldots,Q\}$ and thus the common output function
\begin{equation}
h \stackrel{\mathrm{def}}{=}  H\big((X_1,f_i(X_1)),\ldots,(X_Q,f_i(X_Q))\big) =  H\big((X_1,f_j(X_1)),\ldots,(X_Q,f_j(X_Q))\big)
\end{equation}
satisfies $\|h-f_i\|_{L_2}^2\leq \varepsilon$ and $\|h-f_j\|_{L_2}^2 \leq \varepsilon$ which is a contradiction as $\|f_i-f_j\|_{L_2} > 2\sqrt{\varepsilon}$. \hfill$\Box$

\smallskip

Finally, observe that as the class $\mathscr{B}$ consists of Boolean functions, we have the trivial inclusion $\Sigma\subseteq \{-1,1\}^Q$ which implies that $M=|\Sigma|\leq 2^Q$ and the proof is complete.

\smallskip

In the random case, denote by $Q=\mathsf{Q}_r(\mathscr{F},\varepsilon,\delta)$ and let  $X=(X_1,\ldots,X_Q)$ where $X_1,X_2,\ldots$ are independent random vectors, each uniformly distributed on $\{-1,1\}^n$, satisfying \eqref{eq:dQr} for some learning algorithm $H$. For every $i\in\{1,\ldots,M\}$, consider the event
\begin{equation}
B_i\stackrel{\mathrm{def}}{=} \Big\{\big\| H\big((X_1,f_i(X_1)),\ldots,(X_Q,f_i(X_Q))\big) - f_i\big\|_{L_2}^2 > \varepsilon\Big\},
\end{equation}
which has probability $\mathbb{P}\{B_i\}\leq\delta$ by \eqref{eq:dQr} and, as before, consider the (random) set
\begin{equation}
\Sigma(X) \stackrel{\mathrm{def}}{=} \big\{ \big( f_i(X_1),\ldots,f_i(X_Q) \big): \ i=1,\ldots,M\big\}.
\end{equation}
\noindent {\it Claim.} $\mathbb{E}|\Sigma(X)| \geq (1-\delta)M$.
\smallskip

\noindent {\it Proof.} Consider the partition $\{1,\ldots,M\} = \sigma_1 \sqcup \cdots \sqcup \sigma_{|\Sigma(X)|}$ depending on $X$ such that for every $r\in\{1,\ldots,|\Sigma(X)|\}$ and all $i,j \in\sigma_r$, we have $f_i\equiv f_j$ on $\{X_1,\ldots,X_Q\}$.  Now, suppose that there exist two distinct $i\neq j\in\sigma_r$ such that $X\notin B_i$ and $X\notin B_j$. Then, the function
\begin{equation}
h \stackrel{\mathrm{def}}{=}  H\big((X_1,f_i(X_1)),\ldots,(X_Q,f_i(X_Q))\big) =  H\big((X_1,f_j(X_1)),\ldots,(X_Q,f_j(X_Q))\big)
\end{equation}
satisfies $\|h-f_i\|_{L_2}^2\leq\varepsilon$ and $\|h-f_j\|_{L_2}^2\leq\varepsilon$ which contradicts $\|f_i-f_j\|_{L_2}>2\sqrt{\varepsilon}$.  Therefore,  for any $r$ and any $X=(X_1,\ldots,X_Q)$, there exists a subset $\tau_r\subseteq\sigma_r$ with $|\tau_r|\geq|\sigma_r|-1$ such that $X\in B_i$ for all $i\in\tau_r$.  Adding up these inequalities and taking the expectation, we deduce that
\begin{equation}
M-\mathbb{E}|\Sigma(X)| = \mathbb{E}\Big[ \sum_{r=1}^{|\Sigma(X)|} \big(|\sigma_r|-1\big) \Big] \leq \mathbb{E}\Big[ \sum_{r=1}^{|\Sigma(X)|} |\tau_r| \Big] \leq \mathbb{E}\Big[ \sum_{r=1}^{|\Sigma(X)|} \sum_{i\in\sigma_r} {\bf 1}_{B_i}(X) \big] = \sum_{i=1}^{M} \mathbb{P}\{B_i\} \leq \delta M,
\end{equation}
which is the desired inequality. \hfill$\Box$

\smallskip

 As the class $\mathscr{B}$ consists of Boolean functions, we have $(1-\delta)M\leq\mathbb{E}|\Sigma(X)|\leq 2^Q$.
\end{proof}

\subsection{Decision trees} Before we estimate the metric entropy of the classes $\mathscr{B}_{n,d}$ and $\mathscr{F}_{n,d}$, we introduce some necessary background. Following \cite[\S 3.2]{O'Do14}, we define a decision tree $T$ to be a representation of a function $f:\{-1,1\}^n\to\R$ as a rooted binary tree in which the internal nodes are labeled by Boolean variables $x_i$, $i\in\{1,\ldots,n\}$, the edges are labeled by -1 and 1 and the leaves are labeled by real numbers. It is required that no Boolean variable $x_i$ appears more than once on any root-leaf path. On input $y\in\{-1,1\}^n$, the tree $T$ computes the value $f(y)$ in the following way. Starting from the root, when the computation path reaches a node labeled by $x_i$, it follows the unique edge labeled by the value $y_i\in\{-1,1\}$. The output $f(y)$ of $T$ is the label of the leaf reached by this path. It is a classical fact (see \cite[Proposition~3.16]{O'Do14}) that if a function $f$ can be represented by a decision tree of depth $d$, then $f$ has degree at most $d$.

In order to prove the lower bound \eqref{eq:ent-lb} on the packing number of $\mathscr{B}_{n,d}$, we shall need the following combinatorial lemma on large families of sets with pairwise small intersections.

\begin{lemma} \label{aux}
Fix $m,k\in\mathbb{N}$ with $k<m$ and $\varepsilon\in(0,1)$.  Then, there exists $t\geq (2k)^{-k/2} m^{(1-\varepsilon)k/2}$ and subsets $\sigma_1,\ldots, \sigma_t \subset \{1,\ldots,m\}$ of size $k$ satisfying
\begin{equation} \label{eq:intersection}
\forall \ i\neq j\in\{1,\ldots,t\},\qquad |\sigma_i\cap \sigma_j| < (1-\varepsilon)k.
\end{equation}
\end{lemma}

\begin{proof}
We shall use the probabilistic method. Suppose that $\boldsymbol{\sigma}$ is a uniformly chosen random subset of $\{1,\ldots,m\}$ of cardinality $k$. Then, we have
\begin{equation}
\mathbb{P}\big\{ |\boldsymbol{\sigma}\cap\{1,\ldots,k\}| \geq (1-\varepsilon)k \big\}=\frac{1}{\binom{m}{k}} \sum_{j\leq\varepsilon k} \binom{k}{k-j} \binom{m-k}{j} \leq \frac{k^k}{m^k} m^{\varepsilon k} \sum_{j\leq\varepsilon k} \binom{k}{k-j} \leq (2k)^k m^{-(1-\varepsilon)k},
\end{equation}
where we used the fact that $\frac{r^s}{s^s} \leq \binom{r}{s} \leq r^s$. If $\boldsymbol{\sigma}_1, \ldots, \boldsymbol{\sigma}_t$ are i.i.d.~copies of $\boldsymbol{\sigma}$, then by homogeneity
\begin{equation}
\forall \ i\neq j\in\{1,\ldots,t\}, \qquad \mathbb{P}\big\{|\boldsymbol{\sigma}_i \cap \boldsymbol{\sigma}_j|\geq(1-\varepsilon) k\big\} \leq (2k)^k m^{-(1-\varepsilon)k}
\end{equation}
and thus
\begin{equation}
\mathbb{E} \left[  \#\{i \neq j: |\boldsymbol{\sigma}_i\cap \boldsymbol{\sigma}_j|\geq(1-\varepsilon) k \} \right] \leq \binom{t}{2} (2k)^k m^{-(1-\varepsilon)k} < t^2(2k)^k m^{-(1-\varepsilon)k}.
\end{equation}
Therefore, if $t\leq (2k)^{-k/2} m^{(1-\varepsilon)k/2}$, there exist $\sigma_1,\ldots,\sigma_t$ with the desired property.
\end{proof}

\tikzstyle{level 1}=[level distance=2cm, sibling distance=3.5cm]
\tikzstyle{level 2}=[level distance=2cm, sibling distance=3.5cm]
\tikzstyle{level 3}=[level distance=2cm, sibling distance=3.5cm]
\tikzstyle{level 4}=[level distance=1.7cm, sibling distance=2.5cm]
\tikzstyle{bag} = [text width=3.5em, text centered]
\tikzstyle{end} = [circle, minimum width=3pt,fill, inner sep=0pt]

\begin{figure}
\begin{center}
\begin{tikzpicture}[grow=down,
emph/.style={edge from parent/.style={black, dashed,thin,draw}},
    norm/.style={edge from parent/.style={solid, black,thin,draw}},
    transp/.style={edge from parent/.style={transparent}}]
\node[bag] {\tiny$\circled{\normalsize$x_1$}$}
    child {
        node[bag] {\tiny$\circled{\normalsize$x_2$}$}
			child[emph] {
				node[bag]  {\tiny$\circled{\normalsize$x_{d-1}$}$}
					child[norm] {
						node[bag]  {\tiny$\circled{\normalsize$x_{i_1}$}$}
							child{
                					node[end, label=below:
                    					{$-1$}] {r}
									edge from parent
               						 node[left] {$-1$}
            							}
            					child {
                					node[end, label=below:
                   				 {$1$}] {r}
                					edge from parent
                					node[right] {$1$}
            						}
            					edge from parent
            					node[left]{$-1$}
            			}
            			child[norm] {
						node[bag]  {\tiny$\circled{\normalsize$x_{i_2}$}$}
							child{
                					node[end, label=below:
                    					{$-1$}] {r}
									edge from parent
               						 node[left] {$-1$}
            							}
            					child {
                					node[end, label=below:
                   				 {$1$}] {r}
                					edge from parent
                					node[right] {$1$}
            						}
            						edge from parent
            					node[right]{$1$}
            			}
            }
            child[emph] {
                node[bag] {$\vdots$}
                child[emph] {
                		node[bag] {\tiny$\circled{\normalsize$x_{i_2}$}$}
                		}
                		child[emph] {
                		node[bag] {\tiny$\circled{\normalsize$x_{i_{k-1}}$}$}
                		}
                edge from parent
            }
            edge from parent
            node[left] {$-1$}
    }
    child {
        node[bag]  {\tiny$\circled{\normalsize$x_2$}$}
         child[emph] {
                node[bag] {$\vdots$}
                		child[transp] {
                		node[bag] {}
                		}
                		child[transp] {
                		node[bag] {}
                		}
                edge from parent
            }
			child[emph] {
				node[bag] {\tiny$\circled{\normalsize$x_{d-1}$}$}
					child[norm] {
						node[bag]  {\tiny$\circled{\normalsize$x_{i_{k-1}}$}$}
							child{
                					node[end, label=below:
                    					{$-1$}] {r}
									edge from parent
               						 node[left] {$-1$}
            							}
            					child {
                					node[end, label=below:
                   				 {$1$}] {r}
                					edge from parent
                					node[right] {$1$}
            						}
            					edge from parent
            					node[left] {$-1$}
            			}
            			child[norm] {
						node[bag]  {\tiny$\circled{\normalsize$x_{i_{k}}$}$}
							child{
                					node[end, label=below:
                    					{$-1$}] {r}
									edge from parent
               						 node[left] {$-1$}
            							}
            					child {
                					node[end, label=below:
                   				 {$1$}] {r}
                					edge from parent
                					node[right] {$1$}
            						}
            					edge from parent
            					node[right]{$1$}
            			}
            }
            edge from parent
            node[right] {$1$}
    };
\end{tikzpicture}
\captionsetup{labelformat=empty}
\caption{The decision tree $T_\sigma$ corresponding to $\sigma=\{i_1<i_2<\cdots<i_k\}$}
\end{center}
\end{figure}

Equipped with Lemma \ref{aux}, we proceed to the proof of the lower bound in Theorem \ref{thm:ent}.

\begin{proof} [Proof of \eqref{eq:ent-lb}]
Let $\sigma$ be a subset of $\{d,d+1,\ldots,n\}$ of cardinality $k=2^{d-1}$. We shall associate to $\sigma$ a Boolean function $f_\sigma:\{-1,1\}^n\to\{-1,1\}$ of degree at most $d$ represented by the decision tree $T_\sigma$ which is constructed as follows. The root of $T_\sigma$ is labeled by $x_1$ and every node which is at distance $i$ from the root is labeled by $x_{i+1}$ for $i\in\{1,\ldots,d-2\}$. If $\sigma=\{i_1,\ldots,i_{k}\}$, then the nodes at distance $d-1$ from the root are labeled by the distinct variables $x_{i_1},\ldots,x_{i_k}$ in accordance with the lexicographic ordering $\leq_L$, meaning that if $(\varepsilon_r(1),\ldots,\varepsilon_r(d-1)), (\varepsilon_s(1),\ldots,\varepsilon_s(d-1))\in\{-1,1\}^{d-1}$ are the labels of the edges joining the root with the nodes labeled by $x_{i_r}$ and $x_{i_s}$, then
\begin{equation} \label{eq:ordering}
i_r \leq i_s \quad \Longleftrightarrow \quad (\varepsilon_r(1),\ldots,\varepsilon_r(d-1)) \leq_L (\varepsilon_s(1),\ldots,\varepsilon_s(d-1)).
\end{equation}
Finally, if given an input $y\in\{-1,1\}^n$ the tree $T_\sigma$ queries the variable $x_{i_j}$ on the $d$-th level, then its output is $y_{i_j}$. This construction is depicted pictorially in the figure above. Observe that in this picture, the restriction \eqref{eq:ordering} is equivalent to $i_1<i_2<\ldots<i_k$.

Using Lemma \ref{aux}, we can find $t\geq 2^{-d2^{d-2}} (n-d+1)^{(1-\varepsilon)2^{d-2}}\geq 2^{-(d+1)2^{d-2}}n^{(1-\varepsilon)2^{d-2}}$ and subsets $\sigma_1,\ldots,\sigma_t$ of $\{d,d+1,\ldots,n\}$ with cardinality $d$ satisfying \eqref{eq:intersection}. We will show that the family of functions $f_{\sigma_1},\ldots,f_{\sigma_t}\in\mathscr{B}_{n,d}$ is well-separated. Indeed, let $r\neq s$ and suppose that $\sigma_r=\{i_1,\ldots,i_k\}$ and $\sigma_s=\{j_1,\ldots,j_k\}$ with $i_1<\ldots<i_k$ and $j_1<\ldots<j_k$. Then, we have
\begin{equation}
\|f_{\sigma_r}-f_{\sigma_s}\|_{L_2}^2 = \frac{1}{2^{d-1}} \sum_{\ell=1}^k \mathbb{E}(x_{i_\ell}-x_{j_\ell})^2 = \frac{1}{2^{d-2}} |\{\ell: \ i_\ell\neq j_\ell\}| \geq \frac{2^{d-1} - |\sigma_r\cap\sigma_s|}{2^{d-2}}\stackrel{\eqref{eq:intersection}}{\geq} 2\varepsilon
\end{equation}
and the proof is complete.
\end{proof}

While Theorem \ref{thm:lb} provides a logarithmic lower bound for the query complexity of learning $\mathscr{F}_{n,d}$ in both the query and the random example models, the upper bound \eqref{eq:EI} of \cite{EI21} is currently known to hold only in the random case. Derandomizing the algorithm used there or finding a different deterministic algorithm whose query complexity is logarithmic in the dimension (and which, ideally,  has reasonable running time) remains an interesting problem.

\subsection{Juntas} A general principle in analysis on the hypercube asserts that functions whose spectrum is not spread out, effectively depend only on few variables. Many concrete instances of this phenomenon have been studied for Boolean functions, such as the important works \cite{Fri99, Bou02, FKN02, KS02}. The definitive junta theorem for general \emph{bounded} functions, is the following deep result of Dinur, Friedgut, Kindler and O'Donnell (DFKO) \cite{DFKO07} (see also \cite{OZ16} for a quantitatively sharp statement in terms of the dependence on $d$).

\begin{theorem} \label{thm:dfko}
Fix $n,d\in\mathbb{N}$, $\varepsilon>0$ and let $f:\{-1,1\}^n\to[-1,1]$ be a function satisfying
\begin{equation}
\sum_{|S|>d} \hat{f}(S)^2 \leq \exp\big(-C(d^2 \log d)/\varepsilon^2\big)
\end{equation}
for a large enough universal constant $C>0$. Then, there exists a subset $\sigma\subseteq\{1,\ldots,n\}$ with $|\sigma|\leq \tfrac{2^{Cd}}{\varepsilon^4}$ and a function $g:\{-1,1\}^n\to\R$ depending only on the variables $(x_i)_{i\in\sigma}$ such that $\|f-g\|_{L_2}\leq \varepsilon$.
\end{theorem}

\begin{proof} [Proof of \eqref{eq:ent-ub}]
Let $\mathsf{m}_{d,\varepsilon}$ be the size of the smallest $\tfrac{\varepsilon}{4}$-net on the space of all bounded functions $h:\{-1,1\}^{k_{d,\varepsilon}}\to[-1,1]$, where $k_{d,\varepsilon} = \tfrac{2^{Cd+2}}{\varepsilon^4}$, equipped with the $L_2$-metric and let $\{h_1,\ldots,h_{\mathsf{m}_{d,\varepsilon}}\}$ be such a net. For a subset $\sigma \subseteq \{1,\ldots,n\}$ of cardinality $k_{d,\varepsilon}$ and $s\in\{1,\ldots,\mathsf{m}_{d,\varepsilon}\}$, denote by
\begin{equation}
\forall \ x\in\{-1,1\}^n,\qquad h_s^\sigma(x) = h_s\big( (x_i)_{i\in\sigma}\big).
\end{equation}
\noindent {\it Claim.} The set $\{h_s^\sigma: \ s=1,\ldots,\mathsf{m}_{d,\varepsilon} \ \mbox{and} \ \sigma\subseteq\{1,\ldots,n\} \mbox{ with } |\sigma|=k_{d,\varepsilon} \}$ is an $\frac{\varepsilon}{2}$-covering of $\mathscr{F}_{n,d}$.
\smallskip

\noindent {\it Proof.} Indeed, let $f:\{-1,1\}^n\to[-1,1]$ be a function of degree at most $d$. By Theorem \ref{thm:dfko}, there exists a subset $\sigma\subseteq\{1,\ldots,n\}$ with $|\sigma|\leq k_{d,\varepsilon}$ and a function $g:\{-1,1\}^n\to\R$ depending only on the variables $(x_i)_{i\in\sigma}$ such that $\|f-g\|_{L_2}\leq \frac{\varepsilon}{4}$. Notice that without loss of generality we can assume that $g$ takes values in $[-1,1]$ as we can otherwise define $\tilde{g}:\{-1,1\}^n\to[-1,1]$ by
\begin{equation}
\forall \ x\in\{-1,1\}^n,\qquad \tilde{g}(x) = \begin{cases} g(x), & g(x)\in[-1,1] \\ \mathrm{sign}(g(x)), & g(x)\notin[-1,1]  \end{cases}
\end{equation}
and observe that $\|\tilde{g}-f\|_{L_2}\leq \|g-f\|_{L_2}\leq \tfrac{\varepsilon}{4}$. Therefore, by  definition of the covering $\{h_1,\ldots,h_{\mathsf{m}_{d,\varepsilon}}\}$ there exists $s\in\{1,\ldots,\mathsf{m}_{d,\varepsilon}\}$ such that $\|g-h_{s}^\sigma\|_{L_2} \leq \frac{\varepsilon}{4}$ and hence $\|f-h_s^\sigma\|_{L_2} \leq  \frac{\varepsilon}{2}$. \hfill$\Box$

\smallskip

To conclude, for every $s$ and $\sigma$, choose an arbitrary point $p_s^\sigma\in \mathscr{F}_{n,d}$ satisfying $\|p_s^\sigma- h_s^\sigma\|_{L_2} \leq \frac{\varepsilon}{2}$, provided that such exists (in the opposite case the corresponding ball can be omitted from the cover). Then,
\begin{equation}
\mathscr{F}_{n,d} \subseteq \bigcup_{s, \sigma} \mathrm{Ball}(h_s^\sigma,\tfrac{\varepsilon}{2}) \subseteq \bigcup_{s,\sigma} \mathrm{Ball}(p_s^\sigma, \varepsilon),
\end{equation}
thus proving that $\mathsf{N}(\mathscr{F}_{n,d},\|\cdot\|_{L_2},\varepsilon) \leq \mathsf{m}_{d,\varepsilon} \binom{n}{k_{d,\varepsilon}} \leq \mathsf{m}_{d,\varepsilon} n^{\frac{2^{Cd+2}}{\varepsilon^4}}$. This concludes the proof.
\end{proof}

\section{Fourier concentration and learning} \label{sec:3}

To prove Theorem \ref{thm:upper}, we shall employ an algorithm of \cite{KM93} with one important twist from the analysis of \cite{EI21}.  We include the argument in full detail for completeness.

\begin{proof} [Proof of Theorem \ref{thm:upper}]
Fix a parameter $b\in(0,\infty)$ to be determined later and denote by
\begin{equation} \label{eq:defQ}
Q_b \stackrel{\mathrm{def}}{=} \left\lceil \frac{2}{b^2} \log\left(\frac{2}{\delta}\sum_{r=0}^{d} \binom{n}{r}\right) \right\rceil.
\end{equation}
Let $X_1,\ldots,X_{Q_b}$ be independent random vectors, each uniformly distributed on $\{-1,1\}^n$. For a subset $S\subseteq\{1,\ldots,n\}$ with $|S|\leq d$, consider the empirical Walsh coefficient of $f$ given by
\begin{equation}
\alpha_S = \frac{1}{Q_b} \sum_{j=1}^{Q_b} f(X_j) w_S(X_j).
\end{equation}
As $\alpha_S$ is a sum of bounded i.i.d.~random variables and $\mathbb{E}[\alpha_S]=\hat{f}(S)$, the Chernoff bound gives
\begin{equation}
\forall \ S\subseteq\{1,\ldots,n\}\mbox{ with } |S|\leq d, \qquad \mathbb{P}\big\{ |\alpha_S-\hat{f}(S)| > b\big\} \leq 2\exp(-Q_bb^2/2).
\end{equation}
Therefore, using the union bound, we get
\begin{equation*} \label{eq:defG}
\mathbb{P}\underbrace{\big\{ |\alpha_S-\hat{f}(S)| \leq b, \ \mbox{for every subset } S  \ \mbox{with} \ |S|\leq  d\big\}}_{G_b} \geq 1-2\sum_{r=0}^{d} \binom{n}{r} \exp(-Q_bb^2/2) \stackrel{\eqref{eq:defQ}}{\geq} 1-\delta.
\end{equation*}
Consider the random collection of sets given by
\begin{equation} \label{eq:defS}
\mathscr{T}_{b} \stackrel{\mathrm{def}}{=} \big\{ S\subseteq\{1,\ldots,n\}: \ |S|\leq d\mbox{ and } |\alpha_S| \geq2b\big\}.
\end{equation}
Observe that if the event $G_b$ holds, then
\begin{equation} \label{eq:notinS}
\forall \ S\notin\mathscr{T}_{b} \mbox{ with }|S|\leq d, \qquad |\hat{f}(S)| \leq |\alpha_S-\hat{f}(S)| + |\alpha_S| \leq 3b
\end{equation}
and
\begin{equation} \label{eq:inS}
\forall \ S\in\mathscr{T}_{b}, \qquad |\hat{f}(S)| \geq |\alpha_S| - |\alpha_S-\hat{f}(S)| \geq b.
\end{equation}
Now, consider the random function \mbox{$h_{b}:\{-1,1\}^n\to\R$}, given by
\begin{equation}
\forall \ x\in\{-1,1\}^n, \qquad h_{b}(x) \stackrel{\mathrm{def}}{=} \sum_{S\in\mathscr{T}_{b}} \alpha_S w_S(x)
\end{equation}
and write
\begin{equation} \label{eq:parseval}
\begin{split}
\|&h_{b}-f\|_{L_2}^2   = \sum_{S\subseteq\{1,\ldots,n\}} \big|\hat{h}_{b}(S)-\hat{f}(S)\big|^2 = \sum_{S\in\mathscr{T}_{b}} |\alpha_S-\hat{f}(S)|^2 + \sum_{S\notin\mathscr{T}_{b}} |\hat{f}(S)|^2
\\ & = \sum_{\substack{S\in\mathscr{T}_{b}\\ S\in\mathscr{S}(f)}} |\alpha_S-\hat{f}(S)|^2 + \sum_{\substack{S\in\mathscr{T}_{b}\\ S\notin\mathscr{S}(f)}} |\alpha_S-\hat{f}(S)|^2\!\!\!\!\!+\sum_{\substack{S\notin\mathscr{T}_b\\S\in\mathscr{S}(f),\ |S|\leq d}}|\hat{f}(S)|^2  +\!\!\!\!\!\sum_{\substack{S\notin\mathscr{T}_b\\S\notin\mathscr{S}(f), \ |S|\leq d}} |\hat{f}(S)|^2 + \sum_{|S|>d} \hat{f}(S)^2.
\end{split}
\end{equation}
On the event $G_b$ we then have
\begin{equation} \label{will-use-BH}
 \sum_{\substack{S\in\mathscr{T}_{b}\\ S\in\mathscr{S}(f)}} |\alpha_S-\hat{f}(S)|^2 + \!\!\!\!\!\sum_{\substack{S\notin\mathscr{T}_b\\S\in\mathscr{S}(f),\ |S|\leq d}}|\hat{f}(S)|^2 \stackrel{\eqref{eq:notinS}}{\leq} (9b^2)\cdot\#\mathscr{S}(f) \leq 9b^2m.
\end{equation}
On the other hand, as $|\alpha_S-\hat{f}(S)|\leq b \leq |\hat{f}(S)|$ for $S\in\mathscr{T}_b$, we get
\begin{equation}
\sum_{\substack{S\in\mathscr{T}_{b}\\ S\notin\mathscr{S}(f)}} |\alpha_S-\hat{f}(S)|^2+\!\!\!\!\!\sum_{\substack{S\notin\mathscr{T}_b\\S\notin\mathscr{S}(f), \ |S|\leq d}} |\hat{f}(S)|^2 \stackrel{\eqref{eq:inS}}{\leq} \sum_{S\notin\mathscr{S}(f)} |\hat{f}(S)|^2\leq  \eta
\end{equation}
by the Fourier concentration property. Combining the above with the assumption that the spectrum of $f$ is $t$-concentrated up to degree $d$, we conclude that
\begin{equation}
\|h_b-f\|_{L_2}^2 \leq \eta + t + 9b^2m \leq \eta + t + \varepsilon
\end{equation}
for $b^2 \leq \varepsilon/9m$. Plugging this choice of $b$ in \eqref{eq:defQ}, we get the conclusion.
\end{proof}

We are now well-equippped to prove Corollary \ref{thm:junta}.

\begin{proof} [Proof of Corollary \ref{thm:junta}]
Let $f\in\mathscr{F}_{n,d}\cap\mathscr{J}_{n,k,\eta}$. Then, there exists a subset $\sigma\subseteq\{1,\ldots,n\}$ with $|\sigma|\leq k$ and a function $g:\{-1,1\}^n\to\R$ depending only on the variables $(x_i)_{i\in\sigma}$ such that $\|f-g\|_{L_2}^2\leq\eta$. Then, $f$ is $\eta$-concentrated on the collection $\mathscr{S}(f) = \{S\subseteq\sigma: \ |S|\leq d\}$, as
\begin{equation}
\sum_{S\nsubseteq\sigma} \hat{f}(S)^2 \leq \|f-g\|_{L_2}^2 \leq \eta.
\end{equation}
Similarly,  the spectrum of $f$ is $\eta$-concentrated up to degree $\min\{d,k\}$ and the conclusion of the corollary follows from Theorem \ref{thm:upper} since $\#\mathscr{S}(f) = \sum_{r=0}^{\min\{d,k\}} \binom{k}{r}$.
\end{proof}

We emphasize that Corollary \ref{thm:junta} does not make any claim about the \emph{running time} required to learn approximate juntas. This is a notoriously difficult problem even for actual juntas that has been investigated in a series of important works, see for instance \cite{MOS03,KLMMV09,ST14}.

Corollary \ref{prop:boolean} follows from Corollary \ref{thm:junta} combined with a classical theorem of Nisan and Szegedy \cite{NS94}, asserting that a Boolean function of degree $d$ depends on at most $d2^{d-1}$ variables. We note in passing that this result has recently been improved in important work of Chiarelli, Hatami and Saks \cite{CHS20} (see also \cite{Wel19} for the best known value of the implicit constant) who derived the optimal conclusion that such a function only depends on $O(2^d)$ variables, but this refinement will be immaterial for our considerations.

\begin{proof} [Proof of Corollary \ref{prop:boolean}]
By \cite[Theorem~1.2]{NS94}, we have the set inclusion $\mathscr{B}_{n,d} \subseteq \mathscr{F}_{n,d}\cap\mathscr{J}_{n,k,0}$ where \mbox{$k=d2^{d-1}$}. Therefore, by Corollary \ref{thm:junta}, we conclude that
\begin{equation}
\mathsf{Q}_r(\mathscr{B}_{n,d},\varepsilon,\delta) \leq \frac{18}{\varepsilon} \sum_{r=0}^d \binom{d2^{d-1}}{r} \log\left( \frac{2}{\delta} \sum_{r=0}^d \binom{n}{r}\right) \leq \frac{36\cdot d2^{d^2}}{\varepsilon} \log\left(\frac{n}{\delta}\right)
\end{equation}
where the last inequality follows by elementary estimates.
\end{proof}

We now proceed to prove Corollary \ref{cor:robust}, which relies on Theorem \ref{thm:upper} and \cite{DFKO07}.

\begin{proof} [Proof of Corollary \ref{cor:robust}]
Let $f\in\mathscr{F}_{n,d}(t)$ and $\eta\geq\frac{C d^2{\log d}}{{\log(1/t)}}$ so that
\begin{equation}
\sum_{|S|>d} \hat{f}(S)^2 \leq t \leq \exp\big(-C(d^2\log d)/\eta\big).
\end{equation}
Instead of using Theorem \ref{thm:dfko} directly, we will use a stronger statement from its proof.  In \cite[p.~405]{DFKO07}, it was shown that there exists a function $h$ of degree at most $d$ which depends only on the variables $(x_i)_{i\in\sigma}$ for a subset $\sigma\subseteq\{1,\ldots,n\}$ with $|\sigma| \leq 2^{O(d)}/\eta^2$ such that $\|f-h\|_{L_2}^2\leq\eta$.  Choosing $\mathscr{S}(f)=\{S\subseteq\sigma: \ |S|\leq d\}$, we deduce that $f$ is $\eta$-concentrated up to degree $d$ and on the collection $\mathscr{S}(f)$. The conclusion follows from Theorem \ref{thm:upper} as $\#\mathscr{S}(f)\leq 2^{O(d^2)}/{\eta^{2d}}$.
\end{proof}

We note in passing that one can replace the use of the DFKO theorem with a result of O'Donnell and Zhao \cite[Corollary~3.5]{OZ16} to improve the dependence of $\eta$ on $d$ to $\eta\geq \frac{Cd^2}{{\log(1/t)}}$ at the expense of an exponentially worse dependence of the complexity on $d$ and $\varepsilon$.

\begin{remark} \label{rem:newproof}
Choosing $t=0$ in Corollary \ref{cor:robust} provides a different proof of the main result of \cite{EI21}, i.e.~that $\mathsf{Q}_r(\mathscr{F}_{n,d},\varepsilon,\delta)  = O_{d,\varepsilon,\delta}(\log n)$, using the DFKO theorem. Indeed, by Theorem \ref{thm:dfko}, we have $\mathscr{F}_{n,d} = \mathscr{F}_{n,d}\cap \mathscr{J}_{n,k(d,\eta),\eta}$ for any $\eta>0$, where $k(d,\eta) = \big\lceil2^{Cd}/\eta^2\big\rceil$. Plugging this in the bound \eqref{eq:junta} and optimizing over $\eta$, we deduce that there exists a universal constant $C >0$ such that
\begin{equation} \label{eq:new-EI}
\forall \ \varepsilon,\delta\in(0,1), \qquad \mathsf{Q}_r(\mathscr{F}_{n,d},\varepsilon,\delta) \leq \frac{2^{Cd^2}}{\varepsilon^{2d+1}} \log\left(\frac{n}{\delta}\right).
\end{equation}
It is worth emphasizing that, while \eqref{eq:new-EI} captures the correct dependence on the dimension $n$, it is asymptotically worse than the bounds \eqref{eq:EI}, \eqref{eq:EI2} both as $d\to\infty$ and as $\varepsilon\to0^+$.

On the other hand, inequality \eqref{eq:EI2} is a special case of the bound \eqref{eq:upper}, up to lower order terms depending only on the degree $d$. Indeed,  if for a function $f\in\mathscr{F}_{n,d}$ we define $\mathscr{S}(f)$ to be the collection of subsets $S$ of $\{1,\ldots,n\}$ for which $|\hat{f}(S)|\geq\varepsilon^{\frac{d+1}{2}}B_d^{-d}$, then we have
\begin{equation}
\#\mathscr{S}(f) \leq \varepsilon^{-d} B_d^{\frac{2d^2}{d+1}}\sum_{S\in\mathscr{S}(f)} |\hat{f}(S)|^{\frac{2d}{d+1}} \leq \frac{B_d^{2d}}{\varepsilon^d}
\end{equation}
and
\begin{equation}
\sum_{S\notin\mathscr{S}(f)} \hat{f}(S)^2 \leq \varepsilon B_d^{-\frac{2d}{d+1}}  \sum_{S\notin\mathscr{S}(f)} |\hat{f}(S)|^{\frac{2d}{d+1}} \leq \varepsilon
\end{equation}
by two applications of the Bohnenblust--Hille inequality. Thus \eqref{eq:EI2} follows from \eqref{eq:upper} with $t=0$.
\end{remark}

To prove Corollary \ref{cor:robust-boolean}, we will use a deep junta theorem of Bourgain \cite[Proposition]{Bou02}. The quantitative version which we employ below follows from \cite[Theorem~7.1]{KN06} (see also \cite{KO12,DJSTW15}).

\begin{theorem} \label{thm:bourgain}
Fix $n,d\in\mathbb{N}$ and $t\in(0,1)$.  For any Boolean function $f\in\mathscr{B}_{n,d}(t)$ and any parameter $\eta\geq \exp\big(C\sqrt{\log(2/t)\log\log d}\big) \big(t\sqrt{d}+\tfrac{1}{2^d}\big)$ there exists a collection of subsets $\mathscr{S}(f)$ of $\{1,\ldots,n\}$ with $\#\mathscr{S}(f) \leq 2^{O(d^2)}$ such that the spectrum of $f$ is $\eta$-concentrated on $\mathscr{S}(f)$.
\end{theorem}

To see how Theorem \ref{thm:bourgain} follows from \cite[Theorem~7.1]{KN06}, choose $\beta=2^{-\Omega(d)}$ in that statement and consider $\mathscr{S}(f)$ to be the collection of subsets $S\subseteq\{1,\ldots,n\}$ with $|S|\leq d$ and $S\subseteq J_\beta$. The fact that $\#\mathscr{S}(f)\leq 2^{O(d^2)}$ then follows since $|J_\beta|\leq 2^{O(d)}$ and the Fourier concentration property on $\mathscr{S}(f)$ follows from the conclusion of \cite[Theorem~7.1]{KN06}.  We note that the lower order terms on the size of $\eta$ with respect to $t,d$ can be removed from Theorem \ref{thm:bourgain} in view of a result of Kindler and O'Donnell \cite{KO12} at the expense of a worse dependence of $\#\mathscr{S}(f)$ on $d$.

\begin{proof} [Proof of Corollary \ref{cor:robust-boolean}]
Let $f\in\mathscr{B}_{n,d}(t)$. If $\eta \geq t^{1+o(1)}d^{\frac{1}{2}+o(1)}$ in the precise sense of Theorem \ref{thm:bourgain}, we have that the spectrum of $f$ is $\eta$-concentrated on a collection of subsets with cardinality $2^{O(d^2)}$. Therefore the conclusion follows from Theorem \ref{thm:upper} since also $t=o(\eta)$ as $t\to0^+$.
\end{proof}

\begin{remark}
It is worth emphasizing that the constraint $\eta\geq t\sqrt{d}$ which follows from \cite{Bou02,KO12} is in some sense optimal if one wishes to learn the class $\mathscr{B}_{n,d}(t)$ from logarithmically many samples. A linear threshold function (LTF) is a Boolean function of the form $f(x)=\mathrm{sign}\langle x,\theta\rangle$, where $x\in\{-1,1\}^n$ and $\theta\in\mathbb{S}^{n-1}$ is a fixed vector. A well-known theorem of Peres \cite{Per21} (see also \cite{BKS99}) asserts that any LTF on $n$ variables belongs in $\mathscr{B}_{n,\Omega(1/t^2)}(t)$ for every $t\in(0,1)$.  We shall argue that there exist $2^{\Omega(n)}$ LTFs which are pairwise $\Omega(1)$-apart which, in vue of Proposition \ref{prop:QM},  will imply that the class of LTFs requires at least $\Omega(n)$ samples to be learned with accuracy $\tfrac{1}{4}$ and confidence $\tfrac{3}{4}$. Equivalently, we will show that there exist $N=2^{\Omega(n)}$ vectors $\theta_1,\ldots,\theta_N\in\mathbb{S}^{n-1}$ such that
\begin{equation} \label{cub}
\forall \ i\neq j, \qquad \big\|\mathrm{sign}\langle x,\theta_i\rangle - \mathrm{sign}\langle x,\theta_j\rangle \big\|_{L_2}^2 = 8\mathbb{P}\big\{ \big(\langle x,\theta_i\rangle, \langle x,\theta_j\rangle\big) \in U\big\} = \Omega(1),
\end{equation}
where $U$ is the second quadrant $\{(s,t): \ s\leq0\leq t\}$. The corresponding estimate in Gauss space follows from classical computations (see, e.g., \cite[Lemme~1]{Kri79}) as
\begin{equation} \label{gauss}
\forall \ u,v\in\mathbb{S}^{n-1}, \qquad \big\|\mathrm{sign}\langle g,u\rangle - \mathrm{sign}\langle g,v\rangle \big\|_{L_2}^2=2-2\mathbb{E}\big[ \mathrm{sign}\big(\langle g,u\rangle \cdot \langle g,v\rangle\big) \big] = 2- \frac{2}{\pi}\arcsin\langle u,v\rangle,
\end{equation}
where $g\sim N(0,\mathsf{Id}_n)$ is a standard Gaussian random vector, and thus it suffices to choose the vectors $\{\theta_i\}_{i=1}^N$ to form an $\Omega(1)$-net in the unit sphere. To pass from the Gaussian statement implied by \eqref{gauss} to the corresponding discrete inequality \eqref{cub} we shall use a classical (multivariate) Berry--Esseen theorem (see, e.g.,  \cite[Theorem~1.1]{Ben04}). In order to apply this result to the random vectors $(\langle x,\theta_i\rangle, \langle x,\theta_j\rangle)$,  it suffices to find an $\Omega(1)$-separated set $\{\theta_i\}_{i=1}^N$ in $\mathbb{S}^{n-1}$ with $N=2^{\Omega(n)}$ points such that $\|\theta_i\|_{\ell_\infty^n} \leq \tau$ for some small enough universal constant $\tau>0$. The existence of such a set can be proven by the probabilistic method in view of standard concentration estimates of $\ell_p^n$-norms on $\ell_q^n$-spheres, see for instance \cite[Remark~2 in p.~223]{SZ90} and \cite[Theorem~1]{AdRBV98}.
\end{remark}

Finally, we prove Corollary \ref{cor:circuits} on the complexity of constant depth circuits.

\begin{proof} [Proof of Corollary \ref{cor:circuits}]
By the main result of \cite{Has01} (which slightly improves \cite[Main Lemma]{LMN93}; see also the exposition in \cite[Section~4.5]{O'Do14}), every $f\in\mathscr{C}_{n,d,s}$ also belongs in $\mathscr{B}_{n,m(d,s,t)}(t)$ for every $t>0$, where $m(d,s,t) = O(\log(s/t))^{d-2}\cdot\log s\cdot \log(1/\varepsilon)$. The conclusion follows by choosing $\eta=\varepsilon$ and $t$ small enough such that $\varepsilon\geq t^{1+o(1)} O(\log(s/t))^{d/2+o(1)}$ and applying Corollary \ref{cor:robust-boolean}.
\end{proof}

\section{Exact learning}  \label{sec:4}

In this section, we shall prove Theorem \ref{thm:exact}. We start with the deterministic case.
\begin{proof} [Proof of \eqref{eq:exact}]
Let $Q=\mathsf{Q}(\mathscr{F}_{n,d},0)$. For the upper bound on $Q$, consider an enumeration $X_1,\ldots,X_k$ of the points in the closed Hamming $\mathrm{Ball}({\bf 1}, d)$, where ${\bf 1}=(1,\ldots,1)$ and $k=\sum_{j=0}^d \binom{n}{j}$.
\smallskip

\noindent {\it Claim.} If $f\in\mathscr{F}_{n,d}$,  then the values $f(X_1),\ldots,f(X_k)$ completely determine $f$.

\smallskip

\noindent {\it Proof.} As usual, for $i\in\{1,\ldots,n\}$ we denote by
\begin{equation} \label{eq:defpart}
\forall \ x\in\{-1,1\}^n, \qquad \partial_i f(x) \stackrel{\mathrm{def}}{=} \frac{f(x_1,\ldots,x_i,\ldots,x_n) - f(x_1,\ldots,-x_i,\ldots,x_n)}{2}
\end{equation}
the discrete partial derivative of $f$. It is straightforward to see that if $f = \sum_S c_s w_S$, then
\begin{equation}
\forall \ x\in\{-1,1\}^n,\qquad \partial_i f(x) = \sum_{S: \ i\in S} c_S w_S(x).
\end{equation}
In particular, if $f$ has degree at most $d$ and $S=\{i_1,\ldots,i_d\}$ has cardinality $d$, then
\begin{equation}
\partial_{i_1}\circ\cdots\circ\partial_{i_d} f({\bf 1}) = c_S.
\end{equation}
On the other hand, \eqref{eq:defpart} implies that $\partial_{i_1}\circ\cdots\circ\partial_{i_d} f({\bf 1})$ is a linear combination of $f(X_1),\ldots,f(X_k)$. In other words, knowing $f(X_1),\ldots,f(X_k)$, we can reconstruct the top-order Walsh coefficients $\{c_S\}_{|S|=d}$. To conclude, we consider the function $f-\sum_{|S|=d} c_S w_S$ and iterate. \hfill$\Box$

\smallskip

Therefore, the claim implies that if the algorithm queries the values of $f$ at $X_1,\ldots,X_k$, then the function can be fully reconstructed, thus proving that $Q\leq k=\sum_{j=0}^d \binom{n}{j}$.

The lower bound is a simple dimension counting argument. Assume, for contradiction, that $\mathscr{F}_{n,d}$ can be learned exactly using $Q$ queries where $Q<k=\sum_{j=0}^d \binom{n}{j}$. Then, for any fixed points $X_1,\ldots,X_Q\in\{-1,1\}^n$, the linear system
\begin{equation} \label{eq:system}
\forall \ r=1,\ldots,Q,\qquad \sum_{|S|\leq d} c_S w_S(X_r) = 0
\end{equation}
with $k$ unknowns $\{c_S\}_{|S|\leq d}$ and $Q$ equations has at least one nonzero solution. In other words, there exists a nonzero function $g\in\mathscr{F}_{n,d}$ which vanishes on $\{X_1,\ldots,X_Q\}$.  If $X_1,\ldots,X_Q$ are the points queried by the algorithm in order to learn $g$, then \eqref{eq:system} shows the same points need to be queried to learn the zero function ${\bf 0}$. This is a contradictions as $H$ would produce the same hypothesis function for both and $g$ is not identically zero.
\end{proof}

Finally,  we prove the upper bound \eqref{eq:e=0} for the random example model.

\begin{proof} [Proof of \eqref{eq:e=0}]
For points $X_1,\ldots,X_Q$ on the hypercube, consider the (linear) evaluation operator $\Phi_{X_1,\ldots,X_Q}:\mathscr{F}_{n,d}\to\R^Q$ given by $\Phi_{X_1,\ldots,X_Q}(f) = (f(X_1),\ldots,f(X_Q))$. In order to prove the upper bound on the query complexity of the random example model without error, it suffices to show that if $Q$ is large enough and $X_1,\ldots,X_Q$ are independent and uniformly distributed random vectors on $\{-1,1\}^n$, then the operator $\Phi_{X_1,\ldots,X_Q}$ is injective with high probability. Indeed, if this is the case then the values of any function $f\in\mathscr{F}_{n,d}$ on a random sequence of samples uniquely determine $f$ with high probability and thus the function can be fully reconstructed by solving a system of linear equations with respect to its Walsh coefficients.

To show that $\Phi_{X_1,\ldots,X_Q}$ is injective with high probability, fix points $P_1,\ldots,P_q\in\{-1,1\}^n$ and let $X$ be a uniform random vector on the hypercube. Suppose that $\Phi_{P_1,\ldots,P_q}$ is not injective and choose a nonzero function $g\in\mathrm{ker}\Phi_{P_1,\ldots,P_q}$.  Then, we have
\begin{equation} \label{eq:pr-dec}
\mathbb{P}\big\{\mathrm{dimker}\Phi_{P_1,\ldots,P_q,X} < \mathrm{dimker}\Phi_{P_1,\ldots,P_q} \big\} \geq \mathbb{P}\{g(X)\neq0\}\geq\frac{1}{2^d},
\end{equation}
where the last inequality is a classical property satisfied by nonzero functions of degree at most $d$ which can be proven inductively, see \cite[Lemma 3.5]{O'Do14}.

To conclude the proof, consider $Q>k\stackrel{\mathrm{def}}{=} \sum_{j=0}^d \binom{n}{j}$ and let $X_1,\ldots,X_Q$ be independent uniformly random points on the hypercube.  Suppose that the operator $\Phi_{X_1,\ldots,X_Q}$ is not injective. Then, at least $Q-k+1$ steps in the following chain of inequalities  are in fact equalities:
\begin{equation}
k \geq \mathrm{dimker}\Phi_{X_1} \geq \mathrm{dimker}\Phi_{X_1,X_2} \geq \cdots \geq \mathrm{dimker}\Phi_{X_1,\ldots,X_Q}.
\end{equation}
By inequality \eqref{eq:pr-dec} and the independence of $X_1,\ldots,X_Q$, we deduce that
\begin{equation*}
\mathbb{P}\big\{\Phi_{X_1,\ldots,X_Q} \ \mbox{is not injective} \big\} \leq \binom{Q}{Q-k+1} \big(1-\tfrac{1}{2^d}\big)^{Q-k+1} \leq Q^{k-1}\big(1-\tfrac{1}{2^d}\big)^{Q-k+1} \leq (2Q)^{k-1}\big(1-\tfrac{1}{2^d}\big)^{Q}.
\end{equation*}
Choosing $Q = C2^d k \log\big(\frac{k}{\delta}\big)$ for a large enough universal constant $C>1$ ensures that $\Phi_{X_1,\ldots,X_Q}$ is injective with probability at least $1-\delta$,  thus completing the proof as $k\leq(d+1)n^d$.
\end{proof}

\begin{remark}
We point out that the query complexity estimate \eqref{eq:e=0} can be realized algorithmically. At every step of the algorithm, one has to compute the rank of the matrix $\Phi_{X_1,\ldots,X_q}$ until it becomes full-rank. Then, the unknown function $f$ can be recovered by solving a system of linear equations with respect to its Walsh coefficients.
\end{remark}

\begin{remark}
Throughout this paper and \cite{EI21}, we have been studying learning algorithms for $\mathscr{F}_{n,d}$ and $\mathscr{B}_{n,d}$ equipped with the Hilbertian $L_2$-metric.
This choice allows us to use Parseval's identity and thus exploit properties of individual Walsh coefficients to study the distance between $f$ and the hypothesis function $h$.
However as the constructed hypothesis functions $h$ are always of degree at most $d$ themselves, this can be generalized to any $L_p$ norm, where $0<p<\infty$, since these are equivalent to the $L_2$ norm on the space of degree-$d$ polynomials up to constants depending only on $d$ (see \cite[\S 9.5]{O'Do14} and \cite{Bou80, Bor84, EI20} for more on moment comparison of polynomials).
\end{remark}

\bibliographystyle{plain}

redpajama_set_name: RedPajamaArXiv


Just kidding world map rug blue kids rugs online. Vintage world map indoor / outdoor rug youcustomizeit. Best 25 map rug ideas on pinterest world map rug, kids. World map country educational fun kids rug kukoon. World map rug amazon gallery word map images and download. World map area rug link italiaorg. World map carpet carpet vidalondon.
Yellow and gray bath rugs cupcakecanyoncom. Lorena canals kid#039;s rug cotton stars (pink). Safavieh anatolia dark grey/brown 6 ft x 6 ft round area. Braided rugs wool roselawnlutheran. Farrow ball rugs handmade by the rug company. Displaying your collections: thinking beyond the shelf. Calvin klein ck211 nevada valley riverstone area rug. French country area rugs : home design decorate french. Small persian rug roselawnlutheran. Safavieh evoke ivy abstract rug, black price tracking. Asterlane flat weave geometric pattern gray/ivory wool.
Kayson custom tonal printed rug red multi pottery barn. Rug masters diamond rug rug masters rug masters inc. Rug masters berkeley, ca 4x6. Bold linocut print as a textured handknotted custom rug. Talia custom printed rug gray pottery barn. Custom printed rugs 37x52quot; setters hunters hint rug. Talia custom printed rug gray pottery barn.


text:
We go where others fear to Tread
Our Mission and Work
Subsidized Neutering
Improving Veterinary Standards
Human Behaviour Change
Improving Welfare Of Captive Animals
Lynx Rehabilitation and Reintroduction
Bear and Tiger Rehabilitation
First Wild Animal Sanctuary
Cities -Companion Animals
Wild Animals Projects
A Gift in Will
Donate Crypto or NFT's
Useful news
Pan-Russian Animal Welfare Organisation with Widest Regional Network says: Stop Going from One Extreme to the Other over Stray Dogs
Position of Forgotten Animals regarding to the media uproar surrounding the death of a child attacked by stray dogs in Chita.
The past few days have seen an increasing furore over the most recent incident in which a person was killed in Russia by stray dogs. Unfortunately, reports of these tragedies have become familiar to us in recent years, but this incident – the death of a child – appears to be a high-water mark. Members of the State Duma have been voicing their opinions and the media has had much to say about the problem of stray dogs. We have seen the federal authorities putting forward laws that have, for reasons that remain unclear, been languishing for years. For example, they have finally enshrined in law the power for municipal administrations to spend some of their budget on capturing stray dogs. The formal lack of that power over the months and years has paralysed efforts to regulate the number of stray dogs in a number of Russian towns and cities. We are hoping that the powers-that-be have realised that it is no good continuing to procrastinate; the problem of stray dogs needs to be addressed at the national level.
Now, on an understandable wave of emotion, calls are being heard (including from the authorities) for stray dogs to be eliminated completely, up to and including a cull by shooting. A hatred and fear of animals is spreading. But methods like shooting have proven not to work over the long-term and they are, in effect, against the law (as courts in various places in Russia have ruled on more than one occasion). Finally, approaches like these provoke an impassioned rejection from the broad ranks of animal lovers and protests from animal-rights advocates.
However, it needs to be acknowledged that Russia's grassroots animal-rights movement often does not fully understand how to address this problem. Inherent in the 'traditional' animal-rights movement is an unbridled radicalism coupled with insufficient knowledge and experience. They usually propose what appears to be the humane method of sterilising homeless dogs then releasing them back onto the street (CSR – capture – sterilisation – release) and a complete prohibition upon euthanasia in shelters. What they forget is that CSR is fundamentally incapable of effectively reducing the number of dogs and is recommended only for poorly developed countries that will inevitably have problems with stray dogs; it has never been used in countries where this problem has been successfully resolved.
The attempt to introduce CSR in a series of Russian regions has only exacerbated the situation – right up to cases in which people have been injured and even killed by stray dogs. Each such tragedy is followed by a reaction from the authorities and the public that is expressed in a resumption of the shooting or mass poisoning of homeless dogs. So attempts to instantly achieve 'total humaneness' have led to the diametric opposite – widespread suffering for people and animals.
Many Russian regions, in effect, constantly lurch between two dead-end approaches: they have capture programmes that are poorly implemented or not implemented at all, sometimes replaced with ineffective CSR programmes, or they go for an extreme 'cleansing' of stray dogs in the aftermath of the latest tragic incident, without ever stopping to really reflect upon what method would be best. This has been going on for years and the stand-off between the 'pro-animal' and 'anti-animal' camps is only growing more intense.
We oppose this vacillation between two extremes.
What we propose is a level-headed, balanced 'third way' that has thoroughly proven itself in every developed country that has successfully resolved the problem of stray dogs or is well on the way to doing so. This approach is entirely workable in our country, too, with certain adjustments for conditions in Russia – there are examples of it but, unfortunately, they are still few. Based on the many years' experience of many international animal welfare organisations, we are certain that only a complex approach will work, one that includes preventative measures: controls over the breeding of domestic pets, pet registration and chipping, subsidised sterilisation services for less advantaged pet owners, a public awareness campaign to encourage the responsible ownership of animals and strict penalties for breaking the rules for keeping animals (incidentally, the question of this sort of liability is not yet sufficiently understood at all levels of government). For homeless animals we propose what is the most effective method – the development of a network of cooperating shelters. These would be private shelters, public shelters and, crucially, municipal shelters that do not turn away any animals brought to them by the public or the animal-control services – 'open-admission' shelters. There are now some examples of these in Moscow.
It has been illustrated in other countries that it is not possible to find a new owner for every animal and, consequently, it is acceptable to euthanize un-homeable animals in open-admission shelters after a certain length of time (if another shelter cannot be found for them). This is regrettable, of course, but to actually reduce the number of animals that are put down what is needed is not an arbitrary prohibition upon euthanasia (in reality, such bans are mere ornaments and what ensues is a horrible death for animals from hunger and illness in overcrowded shelters or on the streets). What is needed is for the authorities and animal-rights advocates to work assiduously over the long-term to educate owners so that they are more responsible, to reduce the production of puppies and kittens and to increase the level of professionalism amongst animal-rights advocates.
Our view is supported by the findings and recommendations of international animal-welfare organisations like ICAM, WAP, Humane Society .
It is also entirely possible to find the funding needed for these programmes. It is not true to say that, in the provinces, money is rarely always used for its intended purpose (that is to say, it is always misappropriated) and therefore nothing good will come of such programmes. As a rule, in the regions, too little money is spent on the problem of stray animals and fundamentally ineffective methods are used – that is why outcomes are so poor! If a sensible, comprehensive approach is taken we will see how well it works and it will then be possible to monitor expenditure more effectively. Also, if there was organised cooperation (rather than opposition) amongst those with concerns about animal welfare, non-government money could be raised more widely in the form of charitable donations.
Unfortunately, at the moment in Russia, the problem of stray dogs is a cause more of endless, overwrought discussions in the media than real debate of the fundamental issues by the authorities, with the involvement of real (not sham) specialists and responsible, experienced campaigners. More often than not, expertise is displaced by the same old 'humaneness' rhetoric from media demagogues, which has proven itself, over many years, to do no good whatsoever. In the regions, decisions are taken without any analysis of what has been done elsewhere or even a cursory assessment of what the consequences of a particular course of action might be. We believe that the time has come to put an end to this wrongheaded way of approaching the problem and formulate, once and for all, clear government policy in this area. We will be happy to put our experience and our activists to work in assisting in any way we can.
£10 will keep an orphan wild bear cub in rehabilitation fed for a day
£20 will spay a shelter cat and greatly raise their chance to be adopted
£50 will help to compile an animal cruelty prosecution case
£100 will fund a piece of equipment for an undercover investigation
£250 will help our Human Behaviour Change programme reach 150 children
Use the slider to see your impact
Tel: +447551396627 (London, UK)
Email: info@forgottenanimals.org
© Forgotten Animals. All Rights Reserved 2022 |
This site uses cookies. Some of the cookies we use are essential for parts of the site to operate and have already been set. You may delete and block all cookies from this site, but parts of the site will not work. To find out more about cookies on this website, see our Privacy Policy, Terms Of Use and Data Protection Policy. I accept cookies from this site

redpajama_set_name: RedPajamaCommonCrawl


Eau Claire (WQOW) — For the 17th time in program history, UW-Eau Claire volleyball is one of the 64 teams to make the NCAA tournament. And for the third time this season, their opponent will be Saint Thomas (MN) in the first round on Friday.
The Blugolds won the first meeting back on September 8th in the Auggie Invite, taking down the Tommies in four sets behind 18 kills from Madelyn Pashibin and 15 from Makenzie Bachmann. However, more than a month later, St. Thomas got their payback at home, giving UWEC one of their three losses of the regular season, with a 3-2 win.
Friday will be the rubber match between these two high-powered teams at a neutral site, and the Blugolds are very familiar with what the Tommies can do.
The Blugolds captured their first regular season and conference tournament championship since 2011, and are playing with a lot of confidence heading into the NCAA tournament.
The regional will be played in St. Peter, Minnesota starting Friday, and run through Sunday. The start time for the first round match-up is still being determined.


text:
Dua Lipa Is Bringing Back the Boyfriend Blazer
Image courtesy of Dua Lipa / @dualipa
After releasing her second album Future Nostalgia to critical acclaim and chart-topping sales back in March, you'd think Dua Lipa might have taken the time to enjoy a well-deserved break. On the contrary, the past few months have seen the singer barely pause for breath. Between promoting the record through virtual appearances and performances, prepping her follow-up remix album Club Future Nostalgia (released tomorrow), and her non-stop carousel of showstopping looks on Instagram, it's safe to say it's been the summer of Dua.
Her latest fashion moment came yesterday with a post of the singer in Los Angeles wearing an oversized lime green blazer, a stretch mesh polo shirt in a plaid print, and a pair of jean shorts with frayed hems undone at the waist. (Oh, and a teeny tiny handbag in a perfectly matching shade of green too.) We know that Lipa is prone to swapping her most beloved pieces with her boyfriend Anwar Hadid, and that she's a fully paid-up fan of the boyfriend jean. Does her oversized men's jacket indicate that she's now making the case for the boyfriend blazer too? It wouldn't be the first trend she's set—and it likely won't be the last, either.
TopicsDua Lipa


text:
Mesa Awarded Grant To Expand 911 Pilot Program
By Mark Brodie
Published: Thursday, December 11, 2014 - 6:07pm
Updated: Thursday, December 11, 2014 - 6:08pm
TS121114 MESA 911.mp3
(Courtesy of Mesa Fire Department)
Mesa officials say the new 911 system has led to faster, more cost-effective responses.
Deputy Fire Chief Steve Ward said responders are focusing more on what callers actually need.
Mesa has been experimenting for the past couple of years with a new way of operating its 911 system.
Officials said it's led to faster, more cost-effective responses and the federal Centers for Medicare and Medicaid Services have awarded the city with a three-year, $12.5 million grant to expand the pilot program and collect data on how it's working.
Steve Ward is Deputy Fire Chief and program manager for the CMS grant. He said responders are focusing more on what callers actually need, calling it a right-sized response.


text:
Hexatoma crystalloptera är en tvåvingeart som först beskrevs av Osten Sacken 1888.  Hexatoma crystalloptera ingår i släktet Hexatoma och familjen småharkrankar.

Artens utbredningsområde är Sri Lanka. Inga underarter finns listade i Catalogue of Life.

Källor

Småharkrankar
crystalloptera

redpajama_set_name: RedPajamaWikipedia


The Trade Promotion Division, of the Ministry of Commerce, Industry and Cooperatives, is responsible for the formulation and development of appropriate policies and strategies, in consultation with national stakeholders, on trade policy and promotion.
A key task of the division is to ensure that Kiribati's obligations in, bilateral, regional and international trading arrangements are effectively implemented to ensure benefits from membership to such agreements are realised.
Kiribati's engagement in regional trading arrangements is motivated by the Kiribati's 20 Year Vision Plan (KV20), Kiribati Development Plan and the Trade Policy Framework which seeks to fast-track and accelerates growth through maximisation of returns from our natural, human and cultural capital.
Kiribati is not a member of the World Trade Organization (WTO) but is party to the Pacific Island Countries Trade Agreement (PICTA) and Pacific Agreement on Closer Economic Relations (PACER) Plus. Kiribati is also considering accession to Interim Economic Partnership Agreement (I-EPA) as guided by the Trade Policy Framework.
The Trade Promotion Division serves as the secretariat for the National Trade Advisory Committee (NTAC).


We're here to help the UNO community tell a consistent story about our contributions and vision for the future. Here is an overview of the award-winning work done by University Communications. Explore our services to see how we can assist you with your next project or event.
University Communications is responsible for the planning and execution of several campuswide events including May and December commencements, Faculty and Student Honors Convocations, and more. These events showcase the university as a whole and its mission on a public stage.
It is critical that email sent from unomaha.edu follow UNO's email and messaging policy. Email follows the brand guide regulations for logos and lockups.
It is important to keep all emails clean, ideally one column or one wide column with a teaser image to optimize on mobile. The campus has preferred tools for sending mass emails.
The Maverick Daily, the Bullseye (formerly the Maverick Weekly), and UNO Alert/Announce emails are all internal communication tools used by University Communications.
Media Relations works to foster knowledge about UNO locally, nationally, and around the globe. This is done by sharing the UNO story through the cultivation of individual campus stories, the exchange of information with members of the media, and coordination of interviews with faculty experts.
Media Relations maintains the UNO News Center, and the UNO News Center Twitter account.
One of the most effective and compelling tools for expressing the character of the UNO brand is the use of dynamic photography. Through careful planning, execution, and application of photography we have the opportunity to raise our visibility within a competitive market.
UNO has a library of photos that can be used by departments, colleges, and programs.
University Communications has created a website to share photos with the UNO community for use in publications, web pages, and other materials.
Social media is an important part of how we, as a university, communicate with our students, alumni, faculty, staff, and other key audiences.
Since January 2013, UNO's website has been undergoing substantial changes. In collaboration with offices, departments, and colleges across campus, University Communications and Administrative Information Services have been working to transition "old" to new pages in order to support our university's goal to grow enrollment and to have a website that accurately reflects the opportunities UNO offers future and current students.
The website renovation is taking place in a series of phases. Priorities are determined by the members of the Digital Communications Executive Committee.
A formal governance policy provides structure, accountability, and a strategic framework to guide our digital communication efforts.
Use our Start Your Project form to begin exploring various communication channels for your project.


text:
Q: Sonarqube adding tags to rules firstly, we have a custom profile with rules from different sources. We want to add some tags to these rules in order to classify them according to our requirements.
We are adding our tags directly into the database with SQL, in the table rule_metadata but the problem is that in the sonarqube interface our new tags works fine when we scan a project (the new tags works in the issues tab) but when we see the rules tab we can not filter the rules or find our tags.
Any idea of how can we add tags to the rules in this way and make the sonar interface works with them? we try restarting sonar, making new projects etc.

A: The database is not an API, you should never directly insert data in it.
You should use UI or Web service to interact with SonarQube.
As a consequence of updating the DB, there's no warranty of what can happen...

redpajama_set_name: RedPajamaStackExchange


text:
Project Censored - 10/21/14
Oct 21st, 2014 by progressiveradionetwork
This episode takes a look at the history of the Free Thought movement in the U-S, from its roots in the time of independence
to its resurgence during the post-Civil War years. The struggle between freethinkers and conservative religious forces played out
on several fronts, including efforts to restrict what publications could be sent through the U-S mail. Among the historical figures
examined in the program are the Free Thought publisher D.M. Bennett and the 'anti-vice crusader' and postal inspector Anthony Comstock,
who lobbied for laws banning the mailing of 'obscene' materials. Bennett was sentenced to prison for mailing a pamphlet called "Cupid's Yokes."
The guests are Roderick Bradford, author and filmmaker, and Tom Flynn, editor of Free Inquiry magazine.
The program includes excerpts from the documentary film, "American Freethought," produced by Bradford and Flynn.


text:
Endurance Athlete Brendan Walsh Climbs and Cycles the Six Tallest Mountains in New England in Under Five Days
Posted on July 12, 2021 by Basil & Salt Magazine	Leave a comment
Beginning in Katahdin, Maine, Guinness World Record holder and endurance athlete, Brendan Walsh embarked on a challenge that involved climbing and cycling over 700 miles between the six tallest summits New England had to offer. This was the NE6.
To keep himself focused and pedaling forward, Walsh was inspired by the thought that he was doing this challenge for the greater good. By completing this challenge, Walsh was raising money for the Alzheimer's Association as well as hoping to inspire others to follow his footsteps and in this case: his tire tracks.
"This journey, more than any other I have done before, was powered by belief," said Walsh. "Things got hard, with challenges I had never faced before, but my belief was unwavering. Even in the darkest, hardest moments, I pulled out the strength to continue. This was not just to raise money but something that people can hang their hat on."
Walsh pushed deeper and dug further than he had ever done before with any challenge. There were periods he spent hours without water in the Vermont summer heat. Despite these challenges, Walsh completed the NE6 in four days, 15 hours, and 34 minutes.
Throughout the challenge, Walsh received constant support from his family, friends and the Kulkea team. Walsh recently joined Kulkea as a brand ambassador, which helped him reach his fundraising goals by donating 25% of proceeds to the cause.
In the past, Walsh broke a Guinness World Record while raising over $10 thousand for the National Alliance on Mental Illness (NAMI). Walsh traveled from Madawaska, Maine to Key West, Florida in 11 days, nine minutes, and 30 seconds; making him the fastest person to cross the U.S. from North to South by bicycle.
To learn more about Brendan Walsh and the NE6 visit his website here.
About Kulkea
KULKEA was founded by New Englanders with Finnish roots to solve the shortcomings of traditional outdoor gear bags. Their pioneering prototype quickly became the go-to for avid skiers. KULKEA stands for a renewed heritage of cleverly designed, premium gear bags that last for your adventure lifetime. KULKEA (cool-ke-ah) is named after the Finnish word meaning "to go" and "to travel," and its goal is to free the adventurous spirit within all of us. It can be found online at www.kulkea.com or on Instagram @kulkea.
SOURCE Kulkea
tagged with Alzheimer's Association, basil & salt Magazine, Brendan Walsh, cycling, Endurance Athlete, Guinness World Records, Kulkea, NE6


When your body starts accumulating excess fat the syndrome is called obesity. Obesity does not see age or gender. There are set standards to determine obesity. Obesity among children is becoming increasingly common in the present times. It causes a lot of trauma to children as they go through a lot of social, emotional and physical problems. These problems dwell in them for a long time and sometimes life time.
It is always good to look at the causes for anything before getting into the solutions. Obesity is ruled by many causes. For instance, if your said intake for a day is around 60 calories and you take around 100 calories of food, the regular intake of 40calories per day would lead to obesity. So, make sure you just eat what is required and not more than that. Else you would not be able to avoid getting over weight and eventually becoming obese.
Genetic issues could be one of the main reasons for obesity among children. It could be possible that the parent or sibling is obese and that has taken to the child too. This could be one of the most viable reasons for obesity. These days junk food has become the food of the hour. There would not be a single child in this world who would refrain from junk food. This causes obesity again. Junk food is not like healthy food which gives nutrition. Junk food increases body fat beyond count and thus causes obesity.
There are ways to find out if your child is suffering from obesity or not. The basic method is to find out the ratio of your child's weight as compared to his/her height. There are other ways of checking obesity. The percentage of body fat also helps determine obesity. This is an inaccurate method if proper instruments are not used. Body Mass Index is the best indicator of your body fat. There are BMI calculators available that help check the level of obesity in the body.
You can also calculate the BMI on your own. Record the weight of your child in pounds and then multiply it by 705. Get your child's height in inches and divide the weight you got by multiplying with this height. Perform this division again and you will get the BMI of your child. Waist circumference is another best way to measure your child's obesity level.
Obesity is not a natural disorder or uncontrollable disorder. It can definitely be curbed and solved. Parents need to be strict while dealing with obese children. Enforce a strictly healthy diet that includes taste and goodness of nutrition. Obviously you cannot make your child have it alone so make sure your entire family is involved in this diet. The eating habits should be as healthy as possible. Your child needs to have four meals a day, which include a healthy breakfast, good lunch, bright dinner and light supper. When your child feeds healthy he or she remains healthy.
Make sure if you want your child to entertain exercises to reduce obesity levels you need to practice it too. It's obviously the parent who acts as a guide for the child. So, make sure you practice the exercises you are preaching. Rewards need not be food at the restaurants it could also include small treats like a trip to some nearby park etc.
We all are aware of the fact that Inactivity can be dangerous for our health. Thus, ensure your child is active enough throughout the day. Encourage him to go and play with other kids. Make sure you do not make your child lose confidence at any time. Your sole responsibility as a parent is to encourage your child to participate in outdoor activity just like other children.
Obesity is natural with the habits of the present time. Only a parent can curb the obesity issues in a child. Thus, it is important you take the right steps and solve the issues forever.


Resumes don't carry the weight that they used to. Students and unemployed people spend days writing them, focusing on how to re-word, "[Job applicant] is an excellent communicator, with a passion for problem solving and strategic thinking." Then employers spend days reading through run-on sentences and jargon-laced sentences that don't speak to the true potential and personality of the individual they were meant to describe.
The biggest problem with resumes, however, is that they group you, the applicant, with "the masses." Securing your dream job is hard – when you walk into that office, and ask the secretary where you can put your resume, you enter a competition. Suddenly your unique set of skills is put in a stack of 100 other names and skills. And all of them are "excellent communicators, with a passion for problem solving." By using a resume to get a job, you're playing by someone else's rules in a game that has you at 1–100 odds.
So how can you really catch an employer's eye? Build a portfolio.
This weekend I was driving home from Tahoe with one of my friends who is a junior at a very good school in California. He gets better-than-average grades. He loves his field of study, mechanical engineering. And he has an impressive amount of real world experience. But he's still concerned that he won't get an internship this summer. That's because he's playing someone else's game.
Because all of my work was on a website that I controlled, I didn't have to describe myself in typical resume form. Instead I was able to let my work speak for itself. If the hiring manager wanted to learn more after the first page, they could navigate to another piece of writing, and another, and another. My thought process and experience wasn't limited to one page, it was all encompassing.
We found three projects he could put on a portfolio website. In a Philosophy of Design course, he had designed a washing machine that automatically moved clothes into the dryer. Perfect. He'd also designed, prototyped and manufactured a physical product after High School. Even better. We even turned a job he had last summer as a camp counselor — a negative on your typical engineering resume — into a portfolio page. It turns out he was teaching elementary students how to write code and had to design the courses himself.
All of these experiences were nothing without the stories that made them interesting. But the resume my friend was thinking about writing didn't have any room for storytelling.
So here's my advice: sign up for a squarespace account and make two pages: "About me" and "My work." Spend a couple hours uploading some of your past work and take the time to write out your process of thinking. Then send the CEO of your 5 favorite companies an email describing what you can do for the company and include the link to your portfolio. The funny thing is that you'll get a better response rate from a CEO with that email than a HR manager sifting through a hundred resumes. After all, the world rewards the creative and the different.
Michael Thomas is a product marketer at Highfive. Previously he was the Founder and CEO of SkyRocket. He writes about startups and a life outside the box on his personal blog.


text:
Animal Crossing's Small Acts of Faithfulness
Bethany Keeley-Jonker • December 21, 2017
The everyday interactions in Animal Crossing remind us that faithfulness doesn't have to be dramatic.
The Animal Crossing series is kind of unusual as video games go. There is no fighting or shooting, as there aren't any enemies. The game play involves taking care of a place and chatting with animal citizens. Players catch fish and bugs, harvest fruit, purchase and arrange furniture. Maybe after selling enough of their gathered items they might pay off their mortgage (really) and take out a new one to expand their house.
The new Animal Crossing mobile game, Pocket Camp, continues most of these elements, while casting players as a campsite manager with their own (expandable, customizable) camper van. The main way to progress through the game is to visit animals who are camping and give them items they request, such as bugs, fish, fruit, and seashells. Mostly, goals are achieved through repetitive but rewarding tasks. When players help animals, they are given bells and materials that can be used to craft furniture for their campsites or campers.
One thing I like about these games is that they reward in-game behavior that builds relationships and helps others. Succeeding in Animal Crossing means prudent management of your own resources, but also hospitality and generosity with others. This reminds me of the early church disciple Tabitha (also known as Dorcas) in the book of Acts, who is resurrected by Peter. To express their love for her, the people in her community show Peter the clothes she had made for them. I love this image of others attesting to the everyday faithfulness of this woman. The small, relational interactions in Animal Crossing remind me that although faithfulness can look like a dramatic action, like David leading his army, it can also look like Tabitha making clothes for her church family.
One thing I like about these games is that they reward behavior that builds relationships and helps others.
The slow, meditative, repetitive tasks in the game also remind me of the monastic tradition. In some monasteries, acts of communal hospitality, such as cooking and cleaning, are considered a part of prayerful practice. When a game like Animal Crossing elevates similarly simple activities to the main substance of the game, it reminds me of the beauty of everyday offerings in my daily life. I think of the Carrie Newcomer song that names "folding sheets like folding hands / to pray as only laundry can."
Like all games, the Animal Crossing series isn't for everyone. In fact, it can become the kind of thing that distracts players from the everyday faithfulness it simulates. However, by helping us form habits of care and hospitality in the tradition of Tabitha, these games encourage a biblical attentiveness to others. This is a practice we can bring outside of the gaming world and into the real one, which is in desperate need of it.
Topics: Games
Bethany Keeley-Jonker is an Assistant Professor of Communication Arts at Trinity Christian College in Palos Heights, Ill. She lives nearby with her husband and daughter.
More Articles by Bethany Keeley-Jonker
Pokémon Go and our longing for the world to be transformed
Chad Thornhill
Thomas Was Alone and Embracing Your Spiritual Gift
Seeking the Sabbath in Zelda: Breath of the Wild
The fruit of the Spirit found in Lilly Looking Through
Kevin Schut
More in Games
Victoria Grace Howell
Martin Antoon
My Brother's Smasher: Competition and Camaraderie in Super Smash Bros. Ultimate