text:
\section{Introduction}

\subsection{Background and Motivation}
\label{sect:background}
Stochastic local search algorithms \cite{AaLe97,HoSt05} have
in practice proven to be surprisingly efficient in solving
instances of difficult constraint satisfaction
problems (see \cite{ArAu06,SeAO05} for recent examples).
Yet the basic analytical principles underlying the success or failure
of local search heuristics are far from being understood.

The objective of the present work is to shed new analytical light
into the combinatorial phenomena that can occur in
``energy landscapes'' \cite{ReSt02} governing the operation of
most local search algorithms used in practice. Indeed, the
difficulty in analyzing even the most elementary heuristics largely
stems from the fact that the energy landscapes induced by the problem
instances do not easily yield to combinatorial analysis.

To set the stage, certainly among the most well-understood
settings for constraint satisfaction problems is a system of linear
equations $Ax\equiv b\pmod 2$ over $n$ variables $x_1,x_2,\ldots,x_n$
assuming 0/1 values (that is, ``XORSAT'').
The following example will provide to be illustrative.
\begin{equation}
\label{eq:example-system}
\hspace*{0.4in}
\left[\begin{array}{cccc}
0&1&1&1\\
1&0&1&1\\
1&1&0&1\\
1&1&1&0
\end{array}\right]
\left[\begin{array}{c}
x_1\\
x_2\\
x_3\\
x_4
\end{array}\right]\equiv
\left[\begin{array}{c}
0\\
0\\
0\\
0
\end{array}\right]\pmod 2.
\end{equation}

A local search algorithm can now be viewed as a stochastic
process that traverses a sequence of adjacent states in the
\dtext{energy landscape} associated with the problem instance.
For a linear system $Ax\equiv b\pmod 2$, the \dtext{states} of the
landscape consist of the $2^n$ possible
assignments $s=(s_1,s_2,\ldots,s_n)$ of 0/1 values to the
variables $x_1,x_2,\ldots,x_n$.
Any two states are \dtext{adjacent} if they differ in the value of
exactly one variable; the \dtext{distance} between two states is
the number of variables having different values in the two states.
Associated with each state $s$ is an \dtext{energy} $E(s)$ equal
to the number of equations violated by the assignment $x=s$.
For example, with lines indicating adjacency and energy indicated
by subscripts, the landscape associated with (\ref{eq:example-system})
is depicted below.
\begin{equation}
\label{eq:example-landscape}
\begin{minipage}{6in}
\begin{center}
\input{example-landscape.input}
\end{center}
\end{minipage}
\end{equation}

The ``simple'' setting of linear equations
is motivated because it provides direct insight into
landscape phenomena in less tractable settings, in particular,
in the context of the
\dtext{$k$-satisfiability problem ($k$-SAT)} \cite{DuGP97}.
Indeed, a linear equation with $k$ variables is logically equivalent
to a conjunction of $2^{k-1}$ SAT clauses of length $k$ that exclude the
0/1 assignments violating the equation. Furthermore, assuming that energy
in SAT is defined as the number of violated clauses, the landscape
of the SAT encoding of $Ax\equiv b\pmod 2$
is \emph{identical} to the linear landscape.
Thus, any landscape phenomenon that occurs in the context of linear
equations also occurs in SAT.

In the present work we seek to understand what an energy
landscape ``can look like'' to local search
heuristics, in the worst case.
The two standard heuristics that occur in most local
search algorithms are:
(a) \dtext{energy bias}---the algorithm prefers (in probability) moving
into adjacent states with lower energy over those with higher energy; and
(b) \dtext{focusing}---the algorithm prefers moving into adjacent
states such that the move affects the constraints that are violated
in the current state.

Exerting an energy bias does not always guide a search
towards a solution, as can be immediately seen from
(\ref{eq:example-landscape}).
To study the worst-case extent of this phenomenon,
we consider two standard combinatorial measures of ``ruggedness'' in
a landscape:
(a) the \dtext{local minimum} states,
that is, the states with positive energy whose adjacent states all
have strictly higher energy, and
(b) the global \dtext{energy barrier} separating
a state $s$ from a state $t$, that is, the minimum increase in
energy over $E(s)$ required by \emph{any} walk from $s$ to $t$
consisting of successive adjacent states.
Of special interest are the barriers separating local minima from
\dtext{ground states}, that is, the zero-energy solution states.
For example, in (\ref{eq:example-landscape}) the local minimum
states are $1110$, $1101$, $1011$, and $0111$, each
separated by a barrier of $3-1=2$ from the unique ground state $0000$.

From the perspective of the focusing heuristic,
a benchmark algorithm is the \dtext{focused random walk} \cite{Papa91}
(in each step, select uniformly at random one violated constraint,
and flip the value of one variable selected uniformly at random
among the variables occurring in the constraint).
Also focusing can perform poorly, as can be seen by
considering the transition probabilities
in (\ref{eq:example-system}) and (\ref{eq:example-landscape})
for the focused random walk.

The subsequent analysis paints a grim picture of the worst-case
topography that heuristics face already in the ``simple'' case
of $k$-regular linear equations, and hence, in the case of $k$-SAT.
The present results constitute apparently the first rigorous
topographical analysis of the energy landscapes induced by a
nontrivial random ensemble.
(See \S\ref{sect:related} for a discussion of related work.)

\subsection{Statement of Results}
Throughout this work we assume that $k=3,4,\ldots$ is fixed.
In particular, any asymptotic notation
$O(\cdot)$, $\Omega(\cdot)$, $o(\cdot)$ always refers to the parameter
$n$ growing without bound and $k$ remaining fixed.
Furthermore, the constants hidden by the asymptotic notation in
general depend on the fixed parameters, such as $k$ and $\epsilon$ in
Theorem \ref{thm:main}.

An $n\times n$ matrix with 0/1 entries
is $k$-\dtext{regular} if every row and every column has exactly
$k$ nonzero entries. For a given $n$, a \dtext{random $k$-regular matrix}
refers to a $k$-regular $n\times n$ matrix selected uniformly at random
from the set of all such matrices. Similarly,
a \dtext{random $k$-regular landscape} refers to the energy landscape
associated with a system $Ax\equiv 0\pmod 2$, where $A$ is
a random $k$-regular matrix.

\begin{Thm}[Energy barriers and local minima]
\label{thm:main}
For each fixed $k=3,4,\ldots$ and $\epsilon>0$ it holds that
a random $k$-regular landscape has with probability
at least\/ $1-\epsilon$ the following three properties:
\begin{itemize}
\item[(i)]
the number of ground states is $O(1)$;
\item[(ii)]
any two distinct ground states have distance $\Omega(n)$
and are separated by an $\Omega(n)$ energy barrier from each other;
\item[(iii)]
there exists a set of\/ $2^{\Omega(n)}$ local minima such that
each local minimum is separated by an $\Omega(n)$ energy
barrier from every ground state.
\end{itemize}
\end{Thm}
Thus, an energy landscape can be very uneven indeed.
Furthermore, Theorem \ref{thm:main} leaves no possibility
for ``trivial'' barriers caused by large local fluctuations of energy.
Indeed, because each variable occurs in $k=O(1)$ equations,
it follows that moving from one state into an adjacent state changes
the energy by at most $k$ units, implying that the extensive
energy barriers are a global phenomenon apparently not easily
circumvented with local heuristics.
Due to the connection with $k$-SAT, identical lower bounds hold
for $k$-SAT landscapes in the worst case. Interestingly, this worst-case
phenomenon occurs at a ratio $\alpha=2^{k-1}$ of clauses to variables,
which is well below the SAT/UNSAT threshold \cite{AcPe04,Frie99,MeMZ05a}
for the ``random $k$-SAT'' \cite{ChKT91,ChSz88,MiSL92} ensemble.

Also the focused random walk can be shown to fail systematically
for random $k$-regular systems.

\begin{Thm}[Lower bound for focused random walk]
\label{thm:main2}
For each fixed $k=6,7,\ldots$ and $\epsilon>0$ it holds that
the system $Ax\equiv 0\pmod 2$ defined by a random
$k$-regular matrix $A$ has with probability
at least\/ $1-\epsilon$ the property
that the focused random walk
requires\/ $2^{\Omega(n)}$ expected steps to arrive at a ground state
when started from an initial state selected uniformly at random.
\end{Thm}

The main technical hurdle in establishing Theorems \ref{thm:main}
and \ref{thm:main2} is the following result, which we expect to be
of independent interest (see \S\ref{sect:related}) in particular due
to its role in establishing the existence of strong $k$-regular boundary
expanders with almost full linear rank.
\begin{Thm}
\label{thm:kernel}
The expected size of the kernel of a random $k$-regular matrix
over\/ $\ensuremath{\mathrm{GF}}(2)$ is $O(1)$.
\end{Thm}

A matrix $A$ is a $(k,\omega,\eta)$-\dtext{boundary expander} if
(a) the number of nonzero entries in every column is at most $k$,
and
(b) for all $w=1,2,\ldots,\lfloor\omega\rfloor$, every submatrix
    consisting of $w$ columns of $A$ has at least $\lceil\eta w\rceil$ rows
    containing exactly one nonzero value.
The following theorem is well known (cf.~\cite[Theorem~4.16(2)]{HoLW06}).

\begin{Thm}
\label{thm:expansion}
For each fixed $k=3,4,\ldots$ and $\delta>0$
there exists a $\beta>0$ such that a random $k$-regular matrix
is a\/ $(k,\beta n,k-2-\delta)$-boundary expander with
probability\/ $1-o(1)$.
\end{Thm}

\vspace*{-\smallskipamount}

\textbf{[[} N.B.~A proof of
Theorem \ref{thm:expansion} is provided in
Appendix \ref{sect:expansion-proof}.
\textbf{]]}

\medskip

Applying Markov's inequality to Theorem \ref{thm:kernel}
and combining with Theorem \ref{thm:expansion}, it follows
that for each fixed $k=3,4,\ldots$, $\delta>0$, and
$\epsilon>0$ there exist constants $d>0$ and $\beta>0$ such that
with probability at least $1-\epsilon$ a random $k$-regular matrix both
(a) has a kernel of size at most $2^d$
and
(b) is a $(k,\beta n,k-2-\delta)$-boundary expander.
This provides the technical foundation for
Theorems \ref{thm:main} and \ref{thm:main2}.

\subsection{Connections and Related Work}
\label{sect:related}
Random ensembles of constraint satisfaction problems such as
``\dtext{random $k$-XORSAT}'' \cite{CrDa99,RiWZ01,Scha78} and
``\dtext{random $k$-SAT}'' \cite{ChKT91,ChSz88,MiSL92}
have received extensive attention both from the computer science
and the statistical physics communities
\cite{AcNP05,DMSZ01,GoSe05,HoHW96,KiSe94,MePZ02,MZKS99}.
In particular, the random $k$-XORSAT ensemble is by
now well-understood as regards rigorous analysis of the transition
phenomena as the ratio $\alpha$ of the number of equations to variables
is increased \cite{CoDM03,CrDa99,DuMa02,MeRZ03}, and a similar rigorous
foundation is emerging for random $k$-SAT
\cite{AcPe04,AcRi06,Frie99,MeMZ05b},
where the corresponding control parameter $\alpha$
is the ratio of the number of clauses to variables.
The present work differs from these studies by
(a) considering an essentially different random ensemble, and
(b) focusing on the topography of the complete energy landscape,
whereas most of the recent effort,
e.g.~\cite{AcRi06,MeMZ05b,MePR05,MoMe06,MoMZ05}, in studies
of random $k$-XORSAT and random $k$-SAT has gone to investigating
``only'' the distance distribution between the ground states akin to
Theorem \ref{thm:main}(ii). (An exception is \cite{MoSe06a}, where
it is shown that in the limit $n\rightarrow\infty$ the energy barriers
in random $k$-XORSAT between nearby ground states are bounded from
below by $-C\log(\alpha_\mathrm{d}-\alpha)$ for some constant $C>0$
as the control parameter $\alpha$ approaches the dynamical transition
point $\alpha_\mathrm{d}$ \cite{MeRZ03}.)
The growth of energy barriers and local minima
as a function of the system size $n$ has apparently
not been rigorously investigated in random ensembles
until the present work.

The structure of energy landscapes associated with local search
algorithms and spin-glass models of statistical physics
\cite{BoBo07,MePV87} have been the focus of many empirical and
quasi-rigorous statistical-physics studies,
e.g.~\cite{BaHW03,BKMT06,DaSi03,FHSW02,FrCS97,SeMo03},
however, rigorous results are more scarce. In this connection at
least one result exists, namely in \cite{NeMo99} it is shown
that a deterministic 3-regular matrix family based on a triangular
lattice has an associated landscape with local minima separated by an
$\Omega(\log(n))$ barrier from the ground state;
a benchmark study of SAT-solvers using $3$-SAT instances derived
from this family is carried out in \cite{JiMS05}.
A general survey of combinatorial landscapes in various contexts
is \cite{ReSt02}.

From the perspective of computer science and statistical physics,
the ``random satisfiable $k$-regular XORSAT''
(``ferromagnetic $k$-spin model
with Ising spins and fixed connectivity $k$'')
ensemble studied in the present work
has apparently been the focus of only relatively few studies,
despite the fact that the study of random $k$-regular matrices
(equivalently, random $k$-regular bipartite graphs with a fixed
bipartition) has a long history in mathematics \cite{Boll01,Worm99}.
To the best of our knowledge, from a computational / statistical physics
perspective the few works addressing the present ensemble are
\cite{MoSe06b}, where an analysis of the correlation times of the
Glauber dynamics on a corresponding spin-glass model is carried out,
and \cite{HJKN06}, where clausal encodings for the $k=3$ case
are used to empirically benchmark SAT-solvers; further experiments
for the $k>3$ case are reported in \cite{Jarv06}.
Statistical physics studies on analogous fixed-connectivity models
include \cite{FLRZ01,FMRW01,MoRi04,RiKi92}.

From a mathematical perspective it is immediate that the analysis of
$k$-regular matrices over $\ensuremath{\mathrm{GF}}(2)$ is closely related to the study
of \dtext{low-density parity-check codes (LDPC codes)}
\cite{Gall63,RiUr06} in coding theory.
In coding-theoretic language, Theorem \ref{thm:kernel}
states that the expected total number of codewords
in a linear code defined by a parity-check matrix drawn from
the $k$-regular matrix ensemble is $O(1)$
(indicating that such codes have very limited applicability
from a coding-theoretic perspective).
From a methodological perspective, however, the tools used to
analyze the average weight distribution of the codewords in
standard LDPC code ensembles are analogous to the tools used
to prove Theorem \ref{thm:kernel}
(cf.~\cite{BaBu05,BuMi04,DiRU06,LiSh02,OrVZ05,Rath06}),
the main difference being that we want to bound the
expected \emph{total} number of codewords rather than the
number of codewords with a specific relative weight,
necessitating uniform upper bounds that enable summation over
all the weights $w=0,1,\ldots,n$.

Theorems \ref{thm:main} and \ref{thm:main2} are apparently the
first results where expansion is employed in lower bound results
aimed at understanding local search, despite the fact that expansion
is a basic tool in numerous lower bound constructions in, e.g.,
proof complexity \cite{ABRW04,BeWi01,ChSz88,Urqu87},
where many constructions are based on clausal encodings of linear
equations. In particular, the probabilistic full-rank boundary
expander constructions in \cite{ABBI05,AlHI05} apparently
provide an analogue of Theorem \ref{thm:main} in the special case
$k=3$; however, this is not immediate due to lack of regularity.
In the converse direction, the present Theorem \ref{thm:kernel}
and Theorem \ref{thm:expansion} imply
(by stripping dependent rows and columns)
the existence of full-rank boundary expanders for every $k\geq 3$,
thereby providing partial progress to the open lower bound
questions in \cite[\S 5]{ABBI05}.
An interesting technical contrast to the present lower bound
results is that the \emph{upper bound} for the focused
random walk in \cite{AlBS03} also relies on typical expansion
properties of random $3$-SAT instances.
A recent survey of expansion and its applications is
\cite{HoLW06}.

A large number of stochastic local search algorithms
for the $k$-SAT problem are based on variations and combinations
of the energy bias and focusing heuristics.
Arguably the two central algorithm families in this respect are
(a) algorithms in the ``WalkSAT family'' \cite{McSK97,SeKC96}
(e.g. \cite{Hoos02,Papa91,Scho02,SeLM92}),
and
(b) algorithms based on variations of the Metropolis dynamics
\cite{MeRR53} (e.g.~\cite{ArAu06,Cern85,KiGV83,SeAO05}).
(The recent survey propagation algorithm
\cite{BrMZ05,MePZ02,MoMe02} for random $k$-SAT also employs local
search, but only as a postprocessing step after a ``global'' form of
belief propagation \cite{AuGK05,MaMW05}.)

Only relatively few rigorous upper and lower bound results are
known for the running time of local search algorithms for
$k$-SAT. For the focused random walk with restarts,
it is known \cite{Scho02} that a satisfying assignment in
any satisfiable instance of $k$-SAT is found in $O(n(2-2/k)^n)$
expected steps, $k\geq 3$. In \cite{AlBS03} it is shown that
the focused random walk finds a satisfying assignment in
$O(n)$ steps with high probability for a typical instance
drawn from the random 3-SAT ensemble for $\alpha\leq 1.63$.
An exponential upper bound improving upon the trivial $O(2^n)$
is derived in \cite{Hirs00} for a ``cautious'' randomized greedy
approach. In terms of lower bounds, families of crafted instances
whose solution requires an expected exponential number of steps
of the focused random walk
are known; see \cite{AlBS03} and \cite[\S11.5.6]{Papa94}.
Explicit families of instances forcing exponential expected running
times for certain randomized greedy heuristics are constructed
in \cite{Hirs00}. Quasi-rigorous statistical physics studies
considering local search heuristics include \cite{BaHW03,SeMo03}.

From the perspective of local search algorithms for $k$-SAT,
the present Theorem \ref{thm:main2} apparently provides the first
example of a nontrivial random ensemble with exponential lower bounds
on the expected running time for the focused random walk.
Furthermore, the energy barriers and local minima demonstrated in
Theorem \ref{thm:main}(iii) constitute a step towards
rigorous lower bounds for more complex heuristics relying on a
combination of energy bias and focusing.
In this regard the subsequent proof of Theorem \ref{thm:main2}
actually provides a meager first step---for large enough
$k$ it is immediate from (\ref{eq:drift}) that a comparably ``small''
energy bias is insufficient to overcome the systematic drift away
from ground states caused by focusing and expansion.

As regards energy bias heuristics alone, the convergence
properties of nonfocused variants of the Metropolis dynamics
(simulated annealing \cite{Cern85,KiGV83} in particular)
have been extensively analyzed; see
\cite{AaKo89,Cato99,DiSe05,Haje88,HaCK06,SaSF02}
and the references therein. However, these analyses typically
adopt a worst-case setting necessitating that a ground state
is found with significant probability from every possible initial state.
To arrive at a rigorous analysis of the typical behavior from a random
initial state akin to Theorem \ref{thm:main2}, a study of the landscape
structure beyond the properties in Theorem \ref{thm:main} is apparently
required. In particular, the structure of the attraction basins
(see \cite{FHSW02}) of the local minima in Theorem \ref{thm:main}(iii)
in relation to the attraction basins of the ground states need to be
better understood.

\subsection{Organization}
The remainder of this work is organized as follows.
The conventions and mathematical preliminaries
are reviewed in \S\ref{sect:preliminaries}.
Theorem \ref{thm:kernel} is proved in \S\ref{sect:kernel}.
Theorems \ref{thm:main} and \ref{thm:main2} are proved
in \S\ref{sect:topo}.

\subsection{Acknowledgments}
The author would like to thank Mikko Alava, Pekka Orponen, and Sakari Seitz
for useful discussions, and Jukka Kohonen for insight with the
proof of Lemma \ref{lem:tau}.
This research was supported in part by the Academy of Finland, Grant 117499.

\section{Preliminaries}
\label{sect:preliminaries}

\subsection{Conventions}
A \dtext{vector} always refers to
an $n$-dimensional column vector with elements in the
finite field $\ensuremath{\mathrm{GF}}(2)=\{0,1\}$. All arithmetic on vectors is over $\ensuremath{\mathrm{GF}}(2)$.
For $j=1,2,\ldots,n$, denote by $e_j$ the \dtext{standard basis}
vector with the $j$th element equal to $1$ and all other elements equal
to $0$. A \dtext{state} is a synonym for vector when landscapes are discussed.
The \dtext{weight} $W(u)$ of a vector $u$ is the number of nonzero elements.
In accordance with the definitions in \S\ref{sect:background},
the \dtext{energy} of a state $s$ with respect to the system
$Ax\equiv 0\pmod 2$ is defined by $E(s)=W(As)$.
The \dtext{distance} between states $s$ and $t$ is $D(s,t)=W(s+t)$.
A state $s$ is a \dtext{local minimum} if
$E(s)>0$ and $E(s+e_j)>E(s)$ holds for all $j=1,2,\ldots,n$.

\subsection{Asymptotics}
All logarithms are to the natural base
$\exp(1)=\sum_{k=0}^{\infty}1/k!$.
We recall a variant \cite{Robb55} of Stirling's formula,
valid for all positive integers $n$,
\begin{equation}
\label{eq:stirling}
\frac{1}{\sqrt{2\pi}}\exp\biggl(n\log(n)-n+\frac{\log(n)}{2}+\frac{1}{12n+1}\biggr)
\leq n! \leq
\frac{1}{\sqrt{2\pi}}\exp\biggl(n\log(n)-n+\frac{\log(n)}{2}+\frac{1}{12n}\biggr).
\end{equation}
For $0<\lambda<1$, define the entropy function
$H(\lambda)=-\lambda\log(\lambda)-(1-\lambda)\log(1-\lambda)$.
From (\ref{eq:stirling}) we have the following upper bounds
for the binomial coefficients, valid
for all integers $n,k\geq 3$ and $w=1,2,\ldots,n-1$:
\begin{equation}
\label{eq:binom-bounds}
\binom{n}{w}\leq\exp\biggl(nH\biggl(\frac{w}{n}\biggr)\biggr),
\qquad
\binom{n}{w}\binom{kn}{kw}^{-1}\leq
\sqrt{k}\exp\biggl(-(k-1)nH\biggl(\frac{w}{n}\biggr)+\frac{1}{6kw}\biggr).
\end{equation}

In what follows we require asymptotic approximations for coefficients of
large powers of certain polynomials. For a polynomial $P(z)$, denote by
$[z^N]\bigl\{P(z)\bigr\}$ the coefficient of the term $z^N$ in $P(z)$.
For example, $[z^2]\bigl\{1+6z^2+z^4\bigr\}=6$ and
$[z]\bigl\{1+3z^2\bigr\}=0$.
The following theorem is a well-known ``local limit analogue''
\cite{Bend73,GnKo54} of the central limit theorem in probability theory;
see \cite[Chap.~IX]{FlSe06}.

\begin{Thm}[Local limit law for coefficients of a polynomial power]
\label{thm:local-limit}
Let $P(z)$ be a polynomial of degree $d\geq 1$ with
a positive constant term and positive coefficients
such that the greatest common divisor of the degrees of the
nonzero terms of $P(z)$ is\/ $1$, let
\[
\mu=\frac{P'(1)}{P(1)},\quad
\sigma^2=\frac{P''(1)}{P(1)}+\mu-\mu^2,\quad
\sigma>0,
\]
and let\/ $0<\delta<2/3$.
Then, for all large enough $n$, it holds uniformly
for all integers of the form $N=\mu n+\nu$ with $|\nu|\leq n^{\delta}$
that
\begin{equation}
\label{eq:gaussianpower}
[z^N]\bigl\{P(z)^n\bigr\}=
\frac{1}{\sqrt{2\pi n}\sigma}P(1)^n
\exp\biggl(-\frac{\nu^2}{2\sigma^2 n}\biggr)\bigl(1+o(1)\bigr).
\end{equation}
\end{Thm}

\textbf{[[} N.B.~A proof of
Theorem \ref{thm:local-limit} is provided in
Appendix \ref{sect:gaussian-proof}.
\textbf{]]}

\subsection{The Configuration Model for $k$-Regular Matrices}
\label{sect:configuration}
For integers $n\geq k\geq 3$,
let $X$ and $Y$ be two $kn$-element sets of \dtext{points},
both of which are partitioned into $n$ \dtext{cells} of $k$ points each.
A $(k,n)$-\dtext{configuration} is a bijection $\gamma:X\rightarrow Y$.
Denote by $\mathcal{I}$ the set of cells in $X$ and by $\mathcal{J}$
the set of cells in $Y$. Associated with a $(k,n)$-configuration
$\gamma$ there is a $n\times n$ integer matrix $A=(a_{I\!J})$ defined
for all $I\in \mathcal{I}$ and $J\in \mathcal{J}$ by
$a_{I\!J}=|\{i\in I: \gamma(i)\in J\}|$.
We clearly have $\sum_{J} a_{I\!J}=k$ for all $I\in \mathcal{I}$ and
$\sum_{I} a_{I\!J}=k$ for all $J\in\mathcal{J}$.
A configuration is \dtext{simple} if $A$ is a 0/1 matrix.

The following theorem is
due to
B\'ek\'essy, B\'ek\'essy, and Koml\'os \cite{BeBK72}
and O'Neil \cite{Onei69};
early related results are due to
Erd\H os and Kaplansky \cite{ErKa46} and Read \cite{Read59}.

\begin{Thm}
\label{thm:simple}
A random $(k,n)$-configuration is simple with probability
$\mathrm{exp}(-(k-1)^2/2)+o(1)$.
\end{Thm}
It is well known that any given $k$-regular matrix is obtained
from exactly $(k!)^{2n}$ simple $(k,n)$-configurations,
enabling one to access the uniform distribution on
the set of all $k$-regular $n\times n$ matrices via the uniform
distribution on the set of all simple $(k,n)$-configurations.

Also considerable extensions of Theorem \ref{thm:simple} are known, see
\cite{Boll01,GoCr77,GrMW06,Worm99}.

\section{Expected Size of The Kernel}
\label{sect:kernel}

We proceed with the proof of Theorem \ref{thm:kernel}.

\begin{Proof}
By linearity of expectation, we can express the expected size of the
kernel as a sum of expectations of 0/1 indicator variables, one
indicator for each of the $2^n$ vectors.
The expectation of each indicator is equal to the
probability of the corresponding vector occurring in the kernel.
By symmetry, for each weight $w=0,1,\ldots,n$, all the
$\binom{n}{w}$ vectors of weight $w$ have equal probability
of occurring in the kernel. Denote by $P_k(n,w)$ the probability
that a given vector $x$ of weight $w$ occurs in the kernel.

We proceed to derive an upper bound for $P_k(n,w)$ using the
configuration model.
We have that $x$ occurs in the kernel of $A$ if and only if
the columns of $A$ corresponding to the $w$ nonzero coordinates of
$x$ form a submatrix with an even number of nonzero entries in every
row. Let $e_i=0,2,\ldots,2\lfloor k/2\rfloor$ be the number of nonzero
entries in row $i$ of this submatrix. Because $A$ is $k$-regular,
$\sum_{i=1}^n e_i=kw$.
The number of simple $(k,n)$-configurations that induce an $A$ meeting
a given nonnegative even composition $e_1+e_2+\ldots+e_n=kw$
is at most
$(kw)!\cdot(k(n-w))!\cdot\prod_{i=1}^n\binom{k}{e_i}$.
To obtain an upper bound for the total number of simple $(k,n)$-configurations
that induce an $A$ with $x$ in the kernel, let
\begin{equation}
\label{eq:ek}
E_k(z)=
\sum_{j=0}^{\lfloor k/2\rfloor}\binom{k}{2j}z^{2j}=\frac{(1+z)^k+(1-z)^k}{2},
\qquad
B_k(n,w)=[z^{kw}]\bigl\{E_k(z)^n\bigr\}.
\end{equation}
Now observe that the total number of simple $(k,n)$-configurations that
induce an $A$ with $x$ in the kernel is at most
$(kw)!\cdot(k(n-w))!\cdot B_k(n,w)$,
where $B_k(n,w)$ in effect sums the product $\prod_{i=1}^n\binom{k}{e_i}$
over all the eligible compositions $e_1+e_2+\ldots+e_n=kw$.
By Theorem \ref{thm:simple}, for all large enough $n$ there are at
least $\rho\cdot(kn)!$ simple $(k,n)$-configurations, where $\rho$ is any
positive constant less than $\exp(-(k-1)^2/2)$.
We thus have the upper bound
$P_k(n,w)\leq \rho^{-1}\binom{kn}{kw}^{-1}B_k(n,w)$.

Taking the sum of $P_k(n,w)$ over all vectors of weight $w$ and all
weights $w=0,1,\ldots,n$, we have that the expected size of the kernel
of a random $k$-regular matrix of size $n\times n$ is at
most $\rho^{-1}S_k(n)$, where
\begin{equation}
\label{eq:sk}
S_k(n)=\sum_{w=0}^n \binom{n}{w}\binom{kn}{kw}^{-1}B_k(n,w).
\end{equation}
The rest of this section provides an asymptotic analysis establishing
that $S_k(n)=O(1)$.
\end{Proof}

\begin{Thm}
\label{thm:sk}
$S_k(n)=2+o(1)$ if $k$ is odd and
$S_k(n)=4+o(1)$ if $k$ is even.
\end{Thm}
\begin{Proof}
Partition the sum (\ref{eq:sk}) into the following intervals:
\begin{alignat}{2}
\notag
0\leq w&<n/(2k),                  &\qquad &\text{(left extreme deviation)}\\
\notag
n/(2k)\leq w&<(n-n^{3/5})/2,      &\qquad &\text{(left large deviation)}\\
\label{eq:regions}
(n-n^{3/5})/2\leq w&\leq(n+n^{3/5})/2, &\qquad &\text{(central region)}\\
\notag
(n+n^{3/5})/2<w&\leq n(1-1/(2k)), &\qquad &\text{(right large deviation)}\\
\notag
n(1-1/(2k))<w&\leq n.             &\qquad &\text{(right extreme deviation)}
\end{alignat}
Observe that $B_k(n,w)=0$ if $kw$ is odd. Furthermore,
if $k$ is even, we have $B_k(n,w)=B_k(n,n-w)$ by symmetry of the
binomial coefficients, implying that left and right regions are identical
if $k$ is even.
If $k$ is odd, then $E_k$ has degree $k-1$, implying
that $B_k(n,w)=0$ for all $w>(k-1)n/k$
and that the sum is zero in the right extreme region.

\begin{Cla}
The sum in the central region is\/ $1+o(1)$ if $k$ is odd
and\/ $2+o(1)$ if $k$ is even.
\end{Cla}
\begin{Proof}
Using Theorem \ref{thm:local-limit}, we first derive
Gaussian approximations to the terms $\binom{n}{w}$,
$\binom{kn}{kw}$, and $B_k(n,w)$ in the central region.
To this end, let $\delta=3/5$.
From the binomial theorem it follows that
$\binom{an}{aw}=[z^{aw}]\bigl\{(1+z)^{an}\bigr\}$
for nonnegative integers $a,n,w$.
Setting $P(z)=(1+z)^a$, we have $\mu=a/2$ and $\sigma=\sqrt{a}/2$
in Theorem \ref{thm:local-limit}. We obtain that
\begin{equation}
\label{eq:binomial-gaussian}
\binom{an}{aw}=
\frac{1}{\sqrt{2\pi na}}2^{an+1}\exp\biggl(-\frac{a(2w-n)^2}{2n}\biggr)(1+o(1))
\end{equation}
uniformly for all integers $w$ in the central region
$(n-n^{3/5})/2\leq w\leq (n+n^{3/5})/2$.
To approximate $B_k(n,w)$, let $P(z)=E_k(\sqrt{z})$
and observe that $P(z)$ is a polynomial meeting the requirements of Theorem
\ref{thm:local-limit} with $\mu=k/4$ and $\sigma=\sqrt{k}/4$.
We obtain
\begin{equation}
\label{eq:bknw-gaussian}
B_k(n,w)=
\begin{cases}
\frac{2\sqrt{2}}{\sqrt{\pi nk}}2^{(k-1)n}\exp\bigl(-\frac{k(2w-n)^2}{2n}\bigr)(1+o(1)) & \text{if $kw$ is even,}\\[\medskipamount]
0 & \text{if $kw$ is odd,}
\end{cases}
\end{equation}
uniformly for all integers $w$ in the central region.
From (\ref{eq:binomial-gaussian}) and (\ref{eq:bknw-gaussian}) we
have,
\[
\binom{n}{w}\binom{kn}{kw}^{-1}B_k(n,w)=
\begin{cases}
\frac{2\sqrt{2}}{\sqrt{\pi n}}\exp\bigl(-\frac{(2w-n)^2}{2n}\bigr)(1+o(1)) & \text{if $kw$ is even,}\\[\medskipamount]
0 & \text{if $kw$ is odd.}
\end{cases}
\]
Thus, for $w$ in the central region,
\[
\begin{split}
\sum_{w}\binom{n}{w}\binom{kn}{kw}^{-1}B_k(n,w)&=
\bigl(1+o(1)\bigr)\frac{2\sqrt{2}}{\sqrt{\pi n}}
\sum_{w}\exp\biggl(-\frac{(2w-n)^2}{2n}\biggr)\\
&=
\bigl(1+o(1)\bigr)\frac{2\sqrt{2}}{\sqrt{\pi}}
\sum_{t}\frac{1}{\sqrt n}
\exp\biggl(-2\biggl(\frac{t}{\sqrt{n}}\biggr)^2\biggr)\\
&\longrightarrow
\begin{cases}
\frac{2\sqrt{2}}{\sqrt{\pi}}
\int_{-\infty}^{\infty}\exp\bigl(-2s^2\bigr)\,ds=2, & \text{if $k$ is even},%
\\[\medskipamount]
\frac{\sqrt{2}}{\sqrt{\pi}}
\int_{-\infty}^{\infty}\exp\bigl(-2s^2\bigr)\,ds=1, & \text{if $k$ is odd},%
\\
\end{cases}
\end{split}
\]
where the second equality follows from the change of variables
$t=w-n/2$, and the limit as $n\rightarrow\infty$ follows from the
observation that for $w$ in the central region,
$t/\sqrt n$ ranges over $-n^{1/10}/2\leq t\leq n^{1/10}/2$;
the halving when $k$ is odd is due to the terms associated with
odd $w$ being zero if $k$ is odd.
\end{Proof}

\begin{Cla}
\label{cla:leftlarge}
The sum in the left and right large deviation regions is $o(1)$.
\end{Cla}
\begin{Proof}
First we use an approximate variant of the saddle point method
(see e.g.~\cite[Chap.~VIII]{FlSe06}) to derive an upper bound
for $B_k(n,w)$. By Cauchy's coefficient formula,
\[
B_k(n,w)=\frac{1}{2\pi i}\oint\frac{E_k(z)^n}{z^{kw+1}}\,dz,
\]
where the integration contour can be taken to be a positively
oriented circle of radius $\xi>0$ centered at the origin of the complex
plane. Because $E_k(z)$ is a polynomial with positive coefficients,
the integrand assumes its maximum modulus on the contour at $z=\xi$.
Consequently, letting $\lambda=w/n$,
\begin{equation}
\label{eq:saddle-ub}
B_k(n,w)\leq
\frac{1}{2\pi i}\oint\frac{E_k(\xi)^n}{\xi^{kw+1}}\,dz=
\frac{E_k(\xi)^n}{\xi^{kw}}=
\biggl(\frac{E_k(\xi)}{\xi^{k\lambda}}\biggr)^n.
\end{equation}
As an approximation to a saddle point contour,
let $\xi=(\lambda/(1-\lambda))^{(k-1)/k}$ and observe that
\begin{equation}
\label{eq:xi-trick}
\exp\bigl(-(k-1)H(\lambda)\bigr)=
\frac{\xi^{\lambda k}}{\bigl(1+\xi^{k/(k-1)}\bigr)^{k-1}}.
\end{equation}
Combining
(\ref{eq:binom-bounds}), (\ref{eq:saddle-ub}) and (\ref{eq:xi-trick})
we have
\begin{equation}
\label{eq:largedev-bound}
\binom{n}{w}\binom{kn}{kw}^{-1}B_k(n,w)\leq
\sqrt k\biggl(\frac{E_k(\xi)}{\bigl(1+\xi^{k/(k-1)}\bigr)^{k-1}}\biggr)^n
\exp\biggl(\frac{1}{6kw}\biggr).
\end{equation}
Let $\tau^{k-1}=\xi$.
\begin{Lem}
\label{lem:tau}
For all $\tau>0$ it holds that
$E_k(\tau^{k-1})\leq \bigl(1+\tau^k\bigr)^{k-1}$,
with equality if and only if $\tau=1$.
\end{Lem}

\begin{Proof}
Recalling (\ref{eq:ek}) and using the binomial theorem,
the inequality $E_k(\tau^{k-1})\leq \bigl(1+\tau^k\bigr)^{k-1}$
is easily seen to be equivalent to
\begin{equation}
\label{eq:tau-ineq1}
\sum_{j=0}^{\lfloor k/2\rfloor}\binom{k}{2j}\tau^{2j(k-1)}\leq
\sum_{j=0}^{k-1}\binom{k-1}{j}\tau^{jk}.
\end{equation}
In what follows we assume that $e$ is an even nonnegative integer;
in particular, if $e$ is used as the index of summation, then it is assumed
that $e$ runs over all even nonnegative integers.
Recalling that $\binom{k}{j}=\binom{k-1}{j}+\binom{k-1}{j-1}$
for all nonnegative integers $k$ and $j$,
it is straightforward to check that (\ref{eq:tau-ineq1}) is equivalent
to
\begin{equation}
\label{eq:tau-ineq2}
\sum_e\biggl(\binom{k-1}{e}\tau^{e(k-1)}+\binom{k-1}{e-1}\tau^{e(k-1)}\biggr)
\leq
\sum_e\biggl(\binom{k-1}{e}\tau^{ek}+\binom{k-1}{e-1}\tau^{(e-1)k}\biggr).
\end{equation}
The $e=0$ terms cancel in (\ref{eq:tau-ineq2}), so we may assume $e>0$.
To establish (\ref{eq:tau-ineq2}), we show that
\begin{equation}
\label{eq:tau-ineq3}
\binom{k-1}{e}\bigl(\tau^{ek}-\tau^{e(k-1)}\bigr)+
\binom{k-1}{e-1}\bigl(\tau^{(e-1)k}-\tau^{e(k-1)}\bigr)
\geq 0
\end{equation}
holds for each $e>0$, with equality if and only if $\tau=1$.
To this end, divide both sides of (\ref{eq:tau-ineq3})
by $\binom{k-1}{e-1}\tau^{k(e-1)}/e$ to obtain
\begin{equation}
\label{eq:tau-ineq4}
f(\tau)=(k-e)\tau^k-k\tau^{k-e}+e\geq 0.
\end{equation}
Now observe that for $e>0$ we have $f(0)=e>0$,
$f(1)=0$, and $f(\infty)=\infty$.
Taking the derivative of $f$, the real zeroes of
$f'(\tau)=k(k-e)\tau^{k-e-1}(\tau^e-1)$ are $-1$, $0$, and $1$.
Thus, for $\tau>0$ we have $f(\tau)\geq 0$, with equality
if and only if $\tau=1$.
\end{Proof}

We now continue the proof of Claim \ref{cla:leftlarge}.
Observe that $\lambda\in(0,1)$ implies $\xi,\tau\in(0,\infty)$,
with $\lambda=1/2$ if and only if $\xi=\tau=1$.
Thus, for $w$ in the large deviation regions,
that is, for $\lambda=w/n$ with $n^{-2/5}/2<|\lambda-1/2|\leq (k-1)/(2k)$,
we have
$E_k(\xi)/\bigl(1+\xi^{k/(k-1)}\bigr)^{k-1}<1$
in (\ref{eq:largedev-bound}) by Lemma \ref{lem:tau}.
Developing $E_k(\xi)/\bigl(1+\xi^{k/(k-1)}\bigr)^{k-1}$
into a truncated Taylor series at $\lambda=1/2$ and evaluating
at $\lambda=(1\pm n^{-2/5})/2$, we obtain
\begin{equation}
\label{eq:largedev-bound2}
\biggl(\frac{E_k(\xi)}{\bigl(1+\xi^{k/(k-1)}\bigr)^{k-1}}\biggr)^n
\leq \exp\biggl(-\frac{(k-1)n^{1/5}}{2k}\biggr)\bigl(1+o(1)\bigr)
\end{equation}
uniformly for all $w$ in the left and right large deviation regions.
The claim now follows from (\ref{eq:largedev-bound}) and
(\ref{eq:largedev-bound2}) because the regions have $O(n)$ summands.
\end{Proof}

\begin{Cla}
The sum in the left extreme deviation region is $1+o(1)$.
\end{Cla}
\begin{Proof}
For $w=0$ the term in the sum is $1$.
For $w=1,2$ the terms are $O(n^wn^{-kw}n^{kw/2})$.
Thus, in what follows we may restrict to $3\leq w<n/(2k)$.
Observe that
\begin{equation}
\label{eq:bknw-roughbound}
B_k(n,w)\leq \binom{kw/2+n-1}{n-1}\binom{k}{2}^{kw/2}.
\end{equation}
Indeed, $\binom{kw/2+n-1}{n-1}$ counts the number of integer
compositions of $kw$ into $n$ even nonnegative parts, and
$\binom{k}{2}^{kw/2}$ provides an upper bound for the product
$\prod_{i=1}^n\binom{k}{e_i}$ associated with each
composition $e_1+e_2+\ldots+e_n=kw$ into even nonnegative parts
at most $k$.

Observe by (\ref{eq:binom-bounds}) and (\ref{eq:bknw-roughbound}) that
\[
\log\biggl(\binom{n}{w}\binom{kn}{kw}^{-1}B_k(n,w)\biggr)\leq G_k(n,w)+O(1),
\]
where
\[
G_k(n,w)=
-(k-1)n H\biggl(\frac{w}{n}\biggr)+
\biggl(\frac{kw}{2}+n-1\biggr)H\biggl(\frac{n-1}{kw/2+n-1}\biggr)+
\frac{kw}{2}\log\binom{k}{2}.
\]
Differentiating twice with respect to $w$, we have
\[
G_k''(n,w)=\frac{k(kn-1)w+n(n-1)(k-2)}{(n-w)w(kw+2n-2)}
\]
is positive for $0<w<n$, implying that $G_k$ is convex
in the extreme deviation region. In particular,
$G_k$ assumes its maximum at the boundaries of the region. Evaluating
$G_k$ at $w=3$ and $w=n/(2k)$, we find
$G_k(n,w)\leq -3/2\log(n)+O(1)$ uniformly for all $w$ in the region.
The claim follows because the number of terms in the region is $O(n)$.
\end{Proof}

Combining the results for all the regions, we have
that $S_k(n)=2+o(1)$ if $k$ is odd and $S_k(n)=4+o(1)$ if $k$ is even.
This completes the proof of Theorem \ref{thm:sk}.
\end{Proof}

\section{Topographical Properties}
\label{sect:topo}

Throughout this section we consider
the landscape associated with a system $Ax\equiv 0\pmod 2$,
where $A$ is a $k$-regular matrix of size $n\times n$
that both (a) has a kernel of size at most
$2^d$ and (b) is a $(k,\beta n,k-2-\delta)$-boundary expander,
where $0<\beta<1/2$, $d>0$, and $0<\delta<1/3$ are constants independent
of $n$.

\subsection{Energy Barriers and Local Minima}
\label{sect:main-sketch}

The intuition underlying Theorem \ref{thm:main} is as follows.
The boundary expansion property in effect ``surrounds'' a ground state
with a ``perimeter'' of radius $\lfloor\beta n\rfloor$ in the $n$-dimensional
hypercube, where the energy (``wall'') at every perimeter
state is at least $(k-2-\delta)\lfloor\beta n\rfloor$, so any state
outside the perimeter with considerably lower energy has a
considerable barrier separating it from the ground state.

Let us now make this intuition formally precise and prove
Theorem \ref{thm:main}.

Property (i) is immediate by assumption.
To establish property (ii), let $g_1$ and $g_2$ be any two
distinct ground states.
Clearly, $D(g_1,g_2)=W(g_1+g_2)>0$ and $Ag_1=Ag_2=0$.
Thus, it follows from the boundary expansion property that
$D(g_1,g_2)=W(g_1+g_2)>\beta n$.
(Indeed, we cannot have $0=W(A(g_1+g_2))\geq (k-2-\delta)W(g_1+g_2)>0$.)
Thus, any walk of successive adjacent states from $g_1$ to $g_2$ must
have a ``perimeter'' state $p$ with
$D(g_1,p)=W(g_1+p)=\lfloor \beta n\rfloor$.
By the boundary expansion property,
\[
E(p)-E(g_1)=W(Ap)-W(Ag_1)=W(Ap)=W(A(g_1+p))\geq (k-2-\delta)W(g_1+p)=
(k-2-\delta)\lfloor \beta n\rfloor.
\]
Since $g_1$ and $g_2$ were arbitrary, we have thus established that
distinct ground states are at distance $\Omega(n)$ and separated by
an $\Omega(n)$ energy barrier.

To establish property (iii),
we first require a large enough set of local minima.
With foresight, select any constant $\gamma$ such that
\[
0<\gamma<\min\biggl(\frac{\beta(k-2-\delta)}{4}\,,\,
                    \frac{1}{2^d(k(k-1)+1)}\biggr).
\]
Because the kernel of $A$ has dimension at most $d$,
by elementary linear algebra there is a linearly independent
set of $n-d$ columns of $A$.
Furthermore, $A$ restricted to these columns has a linearly
independent set of $n-d$ rows.
By permuting the rows if necessary, we can assume that these rows
occur first in $A$.
Applying Gaussian elimination to the selected $n-d$ linearly
independent columns, we find $n-d$ vectors $y_1,y_2,\ldots,y_{n-d}$
with the property that $Ay_j=e_j+r_j$, where
$r_j$ is a vector with the first $n-d$ entries equal to $0$,
and $e_j$ is the $j$th vector in the standard basis.
Observe that the vectors $y_1,y_2,\ldots,y_{n-d}$ are linearly
independent.

We say that $y_j$ \dtext{marks} the rows that contain a 1 in $A$
in at least one of the columns containing a 1 in row $j$.
In other words, denoting by $a_{pq}$ the entry of $A$ at row $p$, column $q$,
we have that $y_j$ marks the rows $\{i:\exists\,q\ a_{iq}=a_{jq}=1\}$.
Observe that because $A$ is $k$-regular, each vector $y_j$ marks
at most $k(k-1)+1$ rows.

There are at most $2^d$ different vectors $r_j$. Thus,
because $d$ is a fixed constant independent of $n$,
there exist at least $(n-d)/2^d$ vectors $y_j$ that have identical
associated vectors $r_j$.
Among these vectors, start selecting vectors one by one
and marking associated rows subject to the constraint
that no row is marked more than once, until no more vectors can be selected.
Let $m$ be the number of vectors selected in this way.
Clearly, $(n-d)/(2^d(k(k-1)+1))\leq m\leq n$.
By re-indexing the vectors and permuting the rows and columns of $A$
if necessary, we can assume that the selected vectors are
$y_1,y_2,\ldots,y_m$.

We now claim that every state $u$ of the form
$u=\sum_{j=1}^m\chi_j y_j$ with $\chi_j\in\{0,1\}$ and
$\sum_{j=1}^m\chi_j\equiv 0\pmod 2$ is a local minimum.
To see this, observe first that $Au=\sum_{j=1}^m\chi_j e_j$
and that $E(u)=\sum_{j=1}^m\chi_j$.
Now the marking constraint implies that if we flip the value of
any one variable in $u$, we satisfy at most one violated equation
and introduce at least $k-1$ new violated equations. Thus,
$u$ is a local minimum.

We proceed to construct an auxiliary graph that we eventually
use to establish the energy barriers separating certain
local minima from all the ground states.
For $j=1,2,\ldots,m-1$, let $z_j=y_j+y_m$.
Observe that the vectors $z_1,z_2,\ldots,z_{m-1}$ are linearly
independent. Furthermore, the $\binom{m-1}{2}$
sums of the form $z_i+z_j$ with
$1\leq i<j\leq m-1$ clearly satisfy $W(A(z_i+z_j))=2$.

Because $A$ is $k$-regular,
there are at most $\binom{k}{2}n=O(n)=O(m)$ vectors
$y$ with $W(Ay)=2$ and $W(y)\leq 2/(k-2-\delta) < 3$.
To see this, observe that the two columns selected by
any vector $y$ with $W(y)=2$ and $W(Ay)=2$ must have at least
one row containing a $1$ in both columns, and the total
number of such ``$11$''-patterns in $A$ is $\binom{k}{2}n$.
Thus, by the expansion property $\binom{m-1}{2}-O(m)$ of
the sums $z_i+z_j$ satisfy $W(z_i+z_j)> \beta n$.

Form an auxiliary graph with the vertex set $\{z_1,z_2,\ldots,z_{m-1}\}$
such that any two distinct vertices, $z_i$ and $z_j$, are adjacent
if and only if $W(z_i+z_j)\leq \beta n$.
Because the number of edges in the auxiliary graph is $O(m)$,
for all sufficiently large $n$ the auxiliary graph has an independent
set of size $2^d+1$, which---by relabeling if necessary---can be
assumed to consist of the vectors $z_1,z_2,\ldots,z_{2^d+1}$.

We now construct the local minima meeting property (iii).
Let $g_1,g_2,\ldots,g_s$ be the ground states, $s\leq 2^d$.
Observe that any sum consisting of a subset of
the linearly independent vectors $z_1,z_2,\ldots,z_{m-1}$ is a
local minimum. Furthermore, the energy of such a minimum is at most
the number of summands plus one.
Select any $\lceil\gamma n\rceil$ of the vectors
$z_{2^d+2},z_{2^d+3},\ldots,z_{m-1}$.
(Note that for all sufficiently large $n$ this is possible due to
the choice of $\gamma$.)

Consider now any state $u$ formed as the sum of a nonempty subset of
the $\lceil\gamma n\rceil$ selected vectors.
The energy of $u$ is $E(u)=W(Au)\leq \lceil\gamma n\rceil+1$.
The state $u$ does not necessarily have extensive barriers separating
it from each of the ground states. However,
if the following condition holds, then $u$ is separated by
extensive barriers from the ground states.
If the condition does not hold, then
adding one of the (independent) vectors $z_1,z_2,\ldots,z_{2^d+1}$
to $u$ will produce a local minimum that is separated by
extensive barriers from the ground states.

Suppose that $D(u,g_j)>\beta n/2$ holds for all $j=1,2,\ldots,s$.
Thus, for every solution state $g_j$, any walk from $u$ to $g_j$
consisting of successive adjacent states must
contain a ``perimeter'' state $p$ at distance
$D(p,g_j)=W(p+g_j)=\lceil \beta n/2\rceil$
By the boundary expansion property,
the energy of $p$ is
\[
E(p)=W(Ap)=W(Ap+Ag_j)=W(A(p+g_j))\geq
(k-2-\delta) W(p+g_j)\geq\frac{(k-2-\delta)\beta n}{2}.
\]
In particular, the increase in energy at $p$ compared with
the energy of $u$ is
\[
E(p)-E(u)=
W(Ap)-W(Au)\geq
\frac{(k-2-\delta)\beta n}{2}-\lceil\gamma n\rceil-1>
\gamma n.
\]
Thus, the energy barrier separating $u$
from $g_j$ is at least $\gamma n$,
assuming that $D(u,g_j)>\beta n/2$ holds for all $j=1,2,\ldots,s$.

Suppose that $D(u,g_j)\leq \beta n/2$ holds for at least one
$j=1,2,\ldots,s$. Then, we claim that there exists
at least one $\ell=1,2,\ldots,2^d+1$ such that
$D(u+z_\ell,g_j)>\beta n/2$ holds for all $j=1,2,\ldots,s$.
To reach a contradiction, suppose that this is not the case.
Then, by the pigeonhole principle, there exists
a $j=1,2,\ldots,s$ and $1\leq\ell_1<\ell_2\leq 2^d+1$
such that $D(u+z_{\ell_1},g_j)\leq\beta n/2$ and
$D(u+z_{\ell_2},g_j)\leq\beta n/2$.
By the triangle inequality,
$D(u+z_{\ell_1},u+z_{\ell_2})\leq \beta n$,
which by $D(z_{\ell_1},z_{\ell_2})=D(u+z_{\ell_1},u+z_{\ell_2})$
contradicts the fact that $z_1,z_2,\ldots,z_{2^d+1}$ form an independent
set in the auxiliary graph.
Therefore, there exists at least one $\ell=1,2,\ldots,2^d+1$
such that $D(u+z_\ell,g_j)>\beta n/2$ holds for all $j=1,2,\ldots,s$.
Applying the argument in the previous paragraph to the state $u+z_\ell$,
we have that $u+z_\ell$ is separated from every solution state
by an energy barrier at least $\gamma n$.

Because the vectors $z_1,z_2,\ldots,z_{m-1}$ are linearly independent,
we have thus established the existence of at least $2^{\gamma n}-1$
distinct local minima, each separated from every ground state by an
energy barrier of at least $\gamma n$. This establishes property (iii).

\subsection{Lower Bound for the Focused Random Walk}

The intuition underlying Theorem \ref{thm:main2} is as follows.
Consider any ground state $g$.
In any state $s\neq g$ with $D(s,g)\leq\lfloor\beta n\rfloor$,
the boundary expansion
property implies that most equations violated by $s$ in the system
$Ax\equiv 0\pmod 2$ have \emph{exactly one} variable that assumes
different values in $s$ and $g$. In particular, the focused
random walk is unlikely to flip this variable
(there are $k-1$ other choices), thereby exerting a systematic
drift away from $g$. Thus, expansion in effect induces a region
of entropic repulsion around every ground state.

Let us now make this intuition formally precise and prove
Theorem \ref{thm:main2}. As was demonstrated in \S\ref{sect:main-sketch},
all ground states in the landscape have distance at least
$\lceil\beta n\rceil$.
Because $\beta<1/2$, it follows by standard tail bounds for the
binomial distribution (see e.g.~\cite[\S 1]{Boll01}) that
with probability $1-2^{-\Omega(n)}$ the random initial state for
the focused random walk has distance at least $\lceil\beta n\rceil$
to each of the at most $2^d$ ground states.
It thus suffices to show that the expected number of steps
to reach the ground state from the perimeter of a region of repulsion
is $2^{\Omega(n)}$. To this end, let $g$ be any ground state, and
consider any state $s\neq g$ with
$D(s,g)=W(s+g)\leq\lfloor\beta n\rfloor$.
Because $Ag=0$, the number of violated
equations in $s$ is $E(s)=W(As)=W(A(s+g))=E(s+g)$.
By $k$-regularity, $E(s+g)\leq k W(s+g)$. By the expansion property
and $As=A(s+g)$, at least $(k-2-\delta)W(s+g)$ equations violated
by $s$ contain exactly one variable having a different value in
$s$ and $g$. Thus, assuming that the focused random walk is in
the state $s$, the random step will increase the distance to $g$
by $1$ with probability at least
\begin{equation}
\label{eq:drift}
\frac{(k-1)(k-2-\delta)W(s+g)}{kE(s)}
\geq
\frac{(k-1)(k-2-\delta)W(s+g)}{k^2W(s+g)}\geq
\frac{(k-1)(k-2-\delta)}{k^2},
\end{equation}
otherwise the distance to $g$ decreases by $1$.
For $k\geq 6$ the probability (\ref{eq:drift}) is at least $55/108$,
thereby establishing a systematic drift away from $g$ for
every state $s\neq g$ with $D(s,g)\leq\lfloor\beta n\rfloor$.
A standard analysis of the gambler's ruin problem
(see e.g.~\cite[Chap.~XIV]{Fell57}) with one absorbing ruin state
and one reflecting barrier now establishes that,
starting from a (reflecting) state $s$ at distance
$D(s,g)\geq\beta n$ from each ground state $g$,
the expected number of steps required to reach a ground
(ruin) state is $2^{\Omega(n)}$.

redpajama_set_name: RedPajamaArXiv


text:
accelerated FDA approval for both first-line and second-line treatment in bladder cancer; however, preliminary reports on the phase III IMvigor 211 trial data do not support a significant improvement in overall survival in the second-line setting, which was the primary endpoint.
The ongoing phase III IMvigor 130 trial seeks to confirm the findings in the platinum-ineligible population.
Avelumab and durvalumab are both FDA approved in patients with disease progression after prior chemotherapy and demonstrated objective response rates of 13 percent and 17 percent, respectively. 13, 14
Durvalumab is being evaluated as first-line therapy alone and in combination with tremelimumab in the phase III Danube trial. Pembrolizumab is also approved in this space based on results from KEYNOTE-045, with improvement in overall survival from 7. 4 to 103 months (hazard ratio 0.73, p = 0.002). 15 The benefit was independent of measurement of PD-L1 expression.
The anti-PD- 1 nivolumab was the second agent approved by the FDA as a second-line agent after a prior platinum-containing regimen. Check Mate
275 confirmed the findings from the phase 1/2 trial (CheckMate 032), with an objective response in 20 percent of patients and complete response rate of 2. 6 percent, with mediation duration of response of 10. 3 months. 16
The efficacy of novel immunotherapeutics, particularly checkpoint inhibitors, hold promise for a wide variety of tumor types. The next critical steps will be identifying the patients most likely to benefit from therapy and to develop and validate relevant biomarkers. In addition, these drugs will likely be used in combination with many others to optimize outcomes while minimizing side effects.
Open Alliance trials can be viewed at www. allianceforclinicaltrialsinoncology.org/main/public/ standard.xhtml?path=%2FPublic%2FAlliance-Trials. ♦
10. American Society of Clinical Oncology. Meeting abstracts. A phase I/II study to assess the safety and efficacy of pazopanib (PAZ) and pembrolizumab (PEM) in patients (pts) with advanced renal cell carcinoma (aRCC). Available at: abstracts.asco. org/199/ AbstView_199_180924.html. Accessed June 26, 2017.
11. Rosenberg JE, Hoffman-Censitis J, Powles T, et al.
Atezolizumab in patients with locally advanced and metastatic urothelial carcinoma who have progressed following treatment with platinum-based chemotherapy: A single-arm, multicenter, phase 2 trial. Lancet. 2016;387:1909-1920.
12. Balar AV, Galsky MD, Rosenberg JE, et al.
Atezolizumab as first-line treatment in cisplatin-ineligible patients with locally advanced and metastatic urothelial carcinoma: A single-arm, multicenter, phase 2 trial. Lancet. 2017;389: 67-76.
13. Apolo AB, Infante JR, Balmanoukian A, et al.
Avelumab, an anti-programmed death-ligand 1 antibody, in patients with refractory metastatic urothelial carcinoma: Results from a multicenter, phase Ib study. J Clin Oncol. 2017; 35( 19):2117-2124. doi: 10.1200/JCO.2016.71.6795.
14. Massard C, Gordon MS, Sharma S, et al. Safety and efficacy of durvalumab (MEDI4736), an anti-programmed cell death ligand- 1 immune checkpoint inhibitor, in patients with advanced urothelial bladder cancer. J Clin Oncol. 2016; 34( 26):3119-3125.
15. Bellmunt J, de Wit R, Vaughn DJ, et al.
Pembrolizumab as a second-line therapy for advanced urothelial carcinoma.
N Engl J Med. 2017;376( 11):1015-1026.
16. Sharma P, Retz M, Siefker-Radtke A, et al. Nivolumab in metastatic urothelial carcinoma after platinum therapy (Check Mate 275): A multicentre, single-arm, phase 2 trial. Lancet Oncol. 2017; 18( 3):312-322.
REFERENCES, CONTINUED
The efficacy of novel immunotherapeutics, particularly checkpoint inhibitors, hold promise for a wide variety of tumor types.

redpajama_set_name: RedPajamaCommonCrawl


Actually question #1 isn't easy for me. I often wish that I had more time to read, but the truth is that if I had more time to read, I'm not sure I'd use it for reading. The thing is, I love reading (clearly), but there's a limit to what I can read before I need to give my mind a break. I can only absorb so much before I feel overwhelmed. So as much as I sometimes long for hours and hours in which to read, the reality is that if I had them, I'd find myself getting restless and losing focus.
I think the issue for me is that I need a significant amount of time to process the stories and ideas I've read. I'm similar in the way I deal with people — I love seeing with friends, but I need plenty of time afterward to process what happened, to think it through, maybe to turn it into a little narrative, to figure out how I might recount the day to Hobgoblin or to another friend. Books are like friends in this way — I need plenty of time with them and plenty of time without them.
Anyway, if I magically had more time to read, and also had more endurance and focus for reading, I'd read more of … well, everything. More classics, more contemporary fiction, more comfort reading, more nonfiction, more mysteries, more philosophy, more biographies, more essays. A little bit of everything, please.
I squeeze my reading in wherever I can, but rarely is it for more than an hour at most. When I do have a rare day off that doesn't need to be spent in part doing errands or other things and I can spend the whole afternoon with a book it almost feels weird. I think it is a case where I feel guilty (terrible, I know). I think I should be doing something else industrious like cleaning a closet or the basement (sick, I know). But maybe in part it is similar to what you experience–needing to process what I've read. I'm soon going to be on my vacation from work and of course I have three or four books that I hope to read, but we'll see how much reading I actually get in! If I did all of a sudden have extra time I would want to read more classics and more NF.
Actually, having a blog has helped me process what I read more efficiently. I find that I think in a more organized way about what I read as I'm reading it, choosing important lines, recounting the plot to myself, finding flaws or gems to tell about when I review it. I rarely read passively any more.
I think I would answer these questions pretty much as you did. The time school takes up these days used to be partially spent in reading so I would like a little more time just to get back what I have lost. More than that though doesn't seem necessary as I would likely spend it doing other things.
I think this explains why I read about the same number of books now I have more time at home than I did when I was working fulltime. My brain can only cope with so much reading in one go and also like Danielle I feel a bit guilty if I just sit and read for hours – that awful work ethic thing! I have to give myself permission to do it – sad!
I agree with this one hundred percent. I am always trying to encourage the students to take more time to digest their reading, as it's the only way you can really get something out of it. And I feel exactly the same way about seeing people. I need lots of time to process.
Of course I'd like more time to read (amongst many, many other things). I've been using the http://www.dailyreader.net service to keep up with some reading during the day, but while it's help me put away a couple of classics this year I still need to find more time to read. Every once in a while I pick up a new book and just binge all weekend (usually staying up all Saturday night), but these occurrences are few and far between.
This year has been quite a surprise for me given that I haven't been working. I thought for sure I'd be reading a lot more books but I think by the time I do my end of reading stats I'll have read the same amount of books. I guess, I really have been getting a lot more involved in other things.
Danielle — I feel that guilt too, and sometimes I'll end up wasting time because I feel too guilty to read but too lazy to do any real work — stupid, right? But I do think the processing takes time, and I happen to be a particularly slow processor, so I'll just have to resign myself to not being able to fly through books.
Jenny — you're right about blogging helping to process books — I've found that's true for me too. Certainly I read more books now that I'm blogging than I did before, although that also has a lot to do with not being in grad school anymore (the moment I finished grad school I began blogging). But yes, the blog does get me to think more carefully as I'm reading.
Stefanie — I'm glad to hear that you wouldn't necessarily spend extra time on reading (setting school aside, of course) — I hear of people and their incredible bouts of reading, and I wonder if something's wrong with me, but nothing is, of course.
BooksPlease — oh, yes, the work ethic. I'm doing my best to overcome that 🙂 It's interesting to hear that you read the same number of books as you did before — I'm vindicated in my suspicion that the same would be true for me too!
Litlove — I'm so glad you see what I mean and are the same way! Figuring out the true meaning of introvert (not someone who doesn't want to be around people, but someone who needs lots of time to recover from seeing people) helped explain a lot about me.
John — I don't think I could binge in quite that way! I could never stay up all night to read. I prefer to read a little bit at a time.
Iliana — well, it sounds nice to me that you are getting involved in other things — it sounds like a good balance. That's a very good reason not to increase the number of books you read for the year.


Everything you need is found online. But if you still need to contact use, well, here's how to do it!
Microcontroller.com provides a comprehensive listing of select web resources to assist embedded developers. Microcontroller.com has a unique technical focus of the Embedded Systems market.
Microcontroller.com carefully screens all external links to provide you with the highest quality information.
Due to the volume of email received, I can not respond to anonymous emails, or emails with no subject. For fastest response, email me from your corporate or school email account.
To submit a site to be listed, please email me from the domain you wish to be listed.
Any feedback or suggestions (good or bad) about Microcontroller.com are always welcome!
Submit a news item or press release related to the Embedded Industry. This includes microcontrollers, microprocessors, DSPs, and related products which includes development tools. (note: we do not cover the board products industry, except for those boards used exclusively for development or evaluation purposes).
Unless communicating with a client under contract, or specifically noted by an authorized representative of Microcontroller.com, all communications with Microcontroller.com, are considered to be on the record and may be used at the sole descretion of Microcontroller.com. This includes, but is not limited to, email, telephone, face-to-face, and fax communications.
News items may be in text or .DOC format - no PDFs. Graphics files may be in JPEG or GIF format only (no TIFFs please). Please review the news items posted in order to understand the type of news content we post. This address is for News items only. Our News department will reject all other inquiries.
For materials you email or otherwise provide to CPU Technologies or Microcontroller.com (a "Submission"), you grant CPU Technologies and Microcontroller.com permission to (1) use, copy, distribute, transmit, publicly display, publicly perform, reproduce, edit, modify, translate and reformat your Submission, each in connection with CPU Technologies or the Microcontroller.com Web Site, and (2) sublicense these rights, to the maximum extent permitted by applicable law. Microcontroller.com will not pay you for your Submission. Microcontroller.com may remove your Submission at any time. For each Submission, you represent that you have all rights necessary for you to make the grants in this section.
Microcontroller.com maintains strict anti-spam policies. The sending of unsolicited commercial bulk email to a Microcontroller.com address designated for official business is strictly forbidden.


Your Number One Source For FREE Games with no viruses EVER On The Net!
This site contains links to other sites. We are not responsible for the content these sites may contain. The ONLY information we collect from you is the information you submit by signing the guestbook. Submissions on the guestbook that contain any badwords, rude comments, racial comments, or anything bad will be deleted immediately! This site is free from viruses, spyware, adaware, greyware, malware and other web pests. If for some unknown reason you encounter a virus while using our site it is NOT our fault and we will NOT be held responsible. Though the odds of this happening are extremely slim this can still happen.
If you do not agree with the text above please leave.


text:
Home » Third batch of Community of St. Anselm conclude their 'year in God's time'
Third batch of Community of St. Anselm conclude their 'year in God's time'
The community this year included young Christians from Pakistan, the United States, France, Ghana, New Zealand, Zimbabwe, Kenya, Australia, India, United Kingdom and South Africa; and from five denominations: Pentecostal, Anglican, Roman Catholic, Baptist, and Methodist. Photo: Lambeth Palace
By Anglican Communion News Service on June 26, 2018
The third group of young people to spend "a year in God's time" as members of the Community of St Anselm – the new monastic order based at Lambeth Palace – have been commissioned to "be Jesus to the world" at the end of their year. Lambeth Palace is the official London residence and offices of the Archbishop of Canterbury. The Community was started by Archbishop Justin Welby, who serves as abbot of the community, as part of his priority of renewing prayer and spiritual life.
At a special service in the Lambeth Palace chapel last week, friends and family members heard testimonies of how the year had transformed those who took part. During the service, Welby said that his prayer was that each member had grown so close to Jesus "that his call becomes your call, and his cause your cause."
Answering this call, he said, means "being to the world what Jesus has been to you – so that you indeed might be Jesus to the world."
He added: "For we are called, each of us, not only to proclaim the call of Christ to discipleship and obedience, to conversion and faith; but prophetically to show what that means, and in this Community of St Anselm, that is what we seek to happen day by day by day."
Concluding his sermon, the Archbishop said: "What you will do in the future is unknown. Yet I am profoundly confident that those who follow Christ will be caught up in the cause of justice – and that final justice which comes with reconciliation with God – and will live out that cause in the reality of love for those who are the victims of injustice; and that they will live out that cause in proclaiming the good news of Jesus to those who live without the love and light of Christ.
"Brothers and sisters, go in faith! Go and live your lives in the strength of Him who makes you alive!"
Drawing on the riches of ancient traditions, the Community of St. Anselm invites Christians aged 20-35 spend a year praying, studying and serving those on the margins. The community welcomes young Christians from many countries, traditions and denominations. "It aims to be a symbol of God's desire for unity and reconciliation; and a place where that reconciliation becomes reality in shared daily life," Lambeth Palace said.
The community this year included young Christians from Pakistan, the United States, France, Ghana, New Zealand, Zimbabwe, Kenya, Australia, India, United Kingdom and South Africa; and from five denominations: Pentecostal, Anglican, Roman Catholic, Baptist, and Methodist.
Each year the community includes resident members from the U.K. and around the world – who live together at Lambeth Palace – and U.K.-based non-resident members who combine the community with their work or studies. They all commit to the same Rule of Life, which gives them a shared focus on walking closely with Jesus.
Most of this year's members will return to their home contexts and churches, to share and live out what they have learned and received over the last 10 months. Several members are exploring ordination, and several more are going on to explore further the religious life in various contexts.
Community of St. Anselm celebrates third intake
SSJD Companions challenged, transformed by year of convent life


Current Affairs 27th August 2017 (today). the below are the current affairs of 27th August of this year. For more current affairs on National, International and other current affairs in India stay updated to the current affairs pages in the Indi job alert. Current affairs today, GK today.
For more Current Affairs 27th August 2017 and Quizzes for the preparation of SBI PO & Clerk, UPSC, RRB, IBPS, RBI, Railways, Postal and other Competitive Exams. More Current affairs of June 2017, for competitive exams by experts, are available on IndiJobAlert.com. current affairs today Our Current Affairs June 2017 of the IndiJobAlert page covers various current affairs today sections of business & economy, banking & finance, Indian and International affairs, persons, defense, environment and many for competitive exams preparing aspirants.
With an aim to promote renewable energy in Odisha, chief minister Naveen Patnaik on Wednesday launched grid connected rooftop solar projects.
Taiwan has launched Formosat-5, the first homegrown observation satellite, from an air base in the US, the island nation's National Space Organisation (NSO) announced.
32-year-old Ronaldo has given Real Madrid the second consecutive Champions League title, as well as the top scorer of the tournament with 12 goals in the previous season.
England has been awarded the right to host the 2018 Table Tennis Team World Cup, which will be held in London.
UIDAI has joined hands with CSC India for launching door step enrolment facility in the national capital for the elderly, patients and others who cannot travel the Aadhar centres.
For more Current Affairs 27th August 2017 and Quizzes and current affairs India, current affairs of 2017, current affairs pdf download for the preparation of SBI PO & Clerk, UPSC, RRB, IBPS, RBI, Railways, Postal and other Competitive Exams. More current affairs today, Current affairs of June 2017, for competitive exams by experts, are available on IndiJobAlert.com. Our Current Affairs June 2017 and current affairs today of the IndiJobAlert page covers various sections of business & economy, banking & finance, Indian and International current affairs, persons, defense, environment and many for competitive exams preparing aspirants.


text:
Show | 1pm // Doors | 11:30am
Reserve your spot at the NEW Slater's VIP Club here.
Get tickets to the Indian Princess Preshow Cruise here.
VIP Parking available here.
Doors 11:30 AM // Show 1:00 PM
Corral Stage begins at 11:45 AM
Opening Act: Alisan Porter
Corral Stage Band: Anne Brobst
After winning Season Ten of American Idol in 2011, McCreery made history when he became the youngest male artist of any genre, and the first country music artist ever, to have his debut album enter at No. 1 on the Billboard Top 200 chart. In 2011, he won the New Artist of the Year award at both the Academy of Country Music (ACM) Awards and the American Country Awards, and also received the Country Music Television's (CMT) Award for Breakthrough Video of the Year for "The Trouble with Girls" in 2012.
With his third album, Seasons Change released in 2018 (plus a chart-topping Christmas record), the young star has taken a huge creative step forward. He co-wrote all 11 songs on Seasons Change, working with some of the finest songwriters in Nashville to express a wide range of emotions and musical styles. The 2018 album features McCreery's most recent top singles including, "Five More Minutes" which ranked No. 2 on the iTunes country singles chart and No. 9 on the iTunes all-genre singles chart, and "This Is It" an emotional song McCreery wrote about his marriage proposal to his fiancé, Gabi.
In addition to headlining his own tours, McCreery has toured with Brad Paisley and Rascal Flatts and earned industry and fan adoration when he was voted as, "Country Music's Hottest Bachelor" and "Country Music's Sexiest Man" by the readers of NASH Country Weekly Magazine in September 2017.
FOR HANDICAP ACCESSIBLE SEATING, PLEASE CALL THE INDIAN RANCH AMPHITHEATRE AT 508-943-3871.
No coolers, beach chairs, large bags or backpacks allowed into the venue. Small purses are acceptable. If you are bringing in beach towels and/or other items for the beach, a clear plastic bag is acceptable. No food or drinks, with the exception of a sealed bottle of water. Shirts and shoes required


text:
Q: Flexible-PCBs: what data is needed for manufacturers? Can someone explain more about how you generate data for flexible or flexi-rigid PCBs for manufacture? Do I just make more layers and export more gerber files? Is there anything I need to keep in mind when sending these to be manufactured?
I've made a decent number of medium-complexity 2-layer boards and had them manufactured by producing gerber files. I use Pulsonix, but am familiar with Eagle as well.

A: Mostly the same stuff as for rigid FR4 boards. Material will often be polyimide or polyester. Of course you'll want to bend the PCB, so check with the manufacturer what the minimum bend radius is for different thicknesses. In general this radius is small, like 6 to 10 times the circuit's thickness for a double layer FPC, that's a couple mm, and shouldn't be a real limitation for most applications.
Provide drawings of stiffeners, and their material (often FR4). Also of contact areas, with data on finishing (like gold, and its thickness).

A: A flexible PCB is just a one- or two-layer device with a different material specification (polyimide instead of some sort of FR4). The Gerber files are no different.
Flex-rigid-combinations are similar: You'll give them a pretty regular Gerber stack, as with rigid PCBs.
In addition, you send them a specification for the layer stack and tell them which layers are to be fabricated on polyimide. Flex in the middle or your stack? Flex on an outside layer? An additional Gerber layer with the dimensions for the entire PCB and the parts that are flexible might help.
Note (a): Talk to your PCB shop. They will let you know what specification will work best for them.
Note (b): A specification of the stack including all the details is a good idea even for rigid two-layer or multi-layer boards: Tg of the FR4, thickness of the individual FR4 cores and prepregs, finish (HAL, ENIG, ...) copper thickness for each layer, ...

A: I am not a PCB design engineer, but I am working in PCB industry.
To manufacture a board, we generally require Gerber data. We will need the following:
A gerber layer for every physical layer, including solder masks, and an NC drill file with drill tool sizes. Excellon format is the most common drill file format.
Gerber data should be in ASCII format, preferable in imperial units, with a preferred precision of at least (2,4). The drill file should be the same precision as the gerber data. We can use RS274D data with an aperture table, but RS274X is preferred, as it is the latest standard. Metric units are acceptable with a preferred minimum precision of (3,3)
A readme file and fab drawing are recommended. A sample readme.txt file is available. If the board is multilayer, we will require the layer order. The readme should also have any other information not in the file set, such as material type, copper thickness, etc...
All the data files should be put into a single archive file, *.zip files are the most common. We need this for error protection for anything sent through the internet. It's best to name the *.zip file after the part number of the board (ie LCDDriver.zip)

redpajama_set_name: RedPajamaStackExchange


First Marination: Skin the chicken and make a few slits of about 2cm/¾in long on the flesh. Add half quantity of ginger & garlic paste, salt, chilli powder and lemon juice mix well. Cover and refrigerate for eight hours or overnight.
Second Marination: Mix all the remaining ingredients into a smooth paste and rub the marinade generously all over the chicken skin. Leave it aside for one hour.
It is traditionally roasted in Tandoor (charcoal heated clay oven) but for your ease you can do the same in an oven.
Place the chicken in a roasting tin and cover with foil. Roast in the centre of the oven for 9 minutes. Halfway through cooking, baste with little butter.
After 90 minutes, remove chicken from the oven and leave in a warm place to rest for 20 minutes.
As the chicken cooks make the chutney. For the chutney, place all the chutney ingredients in a blender and blend until the mixture becomes a coarse paste. Add 4-5 tablespoons of cold water to ease blending. Alternatively, use a pestle and mortar. This chutney can be stored in an airtight, non-metallic container for up to four days in the refrigerator.


text:
Casey's opens in Gravette
Casey's General Store opens its doors in Gravette after years of planning and months of building
by: Crystal Martinez
Posted: May 9, 2020 / 10:00 PM CDT / Updated: May 10, 2020 / 01:55 PM CDT
GRAVETTE, Ark. (KNWA/KFTA) – Casey's General Store opens its doors in Gravette after years of planning and months of building.
Mayor Kurt Maddox says business is off to a good start. He anticipates it'll attract even more business once construction on the bypass is complete.
He says the opening is not only a sign of the town's growth – but it also helps generate more sales tax dollars.
"Anything you can get in that helps your sales tax, of course, helps what we can do for the community – including roads, sidewalks, parks," Maddox said.
He says CDC protocols are in place – employees are wearing masks and you'll need to practice social distancing inside.
News / 1 min ago
More KNWA Stories
by Tristan Hill / Jan 17, 2021
UPDATE: Fayetteville Police Department announced Sunday that an arrest was made in connection to the shooting that left a man injured near the intersection of Bradstreet Ln. and Keats Dr. in Fayetteville.
Jarren Brown, 20, was arrested Saturday on charges of engaging in violent criminal activity, aggravated assault and a terroristic act.


text:
Could Nokia Be Sold?
by Nick Kolakowski June 18, 2013 3 min read
AppscloudDataHuaweiMicrosoftNokiaSmartphonesWindows Phone
Nokia is betting on devices such as the Lumia 620 to help it make a comeback.
After several quarters of desperate struggle, Nokia might be in the acquisition crosshairs of Huawei Technologies, the Chinese networking and telecommunications firm.
The Financial Times quoted Richard Yu, head of Huawei's consumer business, as saying that his company was interested in acquisitions and that Nokia would offer "some synergies." However, he also called out sales of Windows Phone, which powers Nokia's current generation of handsets, as "weak."
"That's not good," he said, according to the newspaper. "[Google] Android is free."
Huawei later emailed Bloomberg to say it had "no plans" to acquire Nokia. A Nokia spokesperson declined to comment.
Once a reigning champ of mobile devices, Nokia has fallen on harsher times thanks to Google Android, which is well on its way to dominating the market for low-cost and midrange smartphones that once made up the lion's share of Nokia's business. In a bid to remain competitive, Nokia dropped its homegrown operating systems such as Symbian in favor of Microsoft's Windows Phone, which owns a small sliver of the mobile OS market.
For a few months after Nokia began that transition, it seemed as if the company had bet on the wrong horse: sales of Windows Phone-equipped Nokia devices spiked briefly, to 4 million units in the second quarter of 2012, before tumbling to 2.9 million units in the third quarter. Earlier this year, research firm IDC reported that Samsung was outselling Nokia in Finland, the latter's home turf. But Windows Phone sales have also stabilized somewhat, according to reports, which could give Nokia some hope for the future.
Rumors have abounded for quite some time that, if any company was going to swoop in and purchase Nokia, it would be Microsoft. Given Nokia's wholehearted transition to Windows Phone, however, there's little reason for Microsoft to spend the time and capital necessary to acquire the manufacturer outright: as it stands, it earns all the licensing fees from each Nokia/Windows Phone device sold, without any worries about overhead or hardware costs.
But for firms such as Huawei, hungry for new markets, a weak Nokia could present a tempting target. It all hinges on whether Nokia finally decides to stop fighting.
Image: Nokia
Nokia Windows Phone 7 Released This Month?
Nokia's Windows Phone Sales Pick Up, As Symbian Lingers
Nokia Getting Sick of Windows Phone?
Enterasys Takes Half-Step to Software-Defined Datacenter
What to Do When You Don't Know the Answer


4" Phenolic.Plain Bore Wheel. Shown in photo with 5" wheels.
Photos & graphics are for informational purposes only. Actual product may vary slightly from those shown.
Wheel colors may vary unless specified. If wheel color is important, please contact us for current inventory.
Copyright © Caster City - All Rights Reserved.


text:
Contact [X]
The project and the website are maintained by
Enrico Glaab
School of Computer Science, Nottingham University, UK
webmaster@arraymining.net
Help [X]
Cross-Study Normalization - Help
Features: To overcome the problem of low sample sizes in typical microarray studies the cross-study normalization module provides various methods to combine data from different studies and different platforms together. Since microarray studies can be affected by a great variety of different sources of non-biological bias and variance and the genetic probes often only have a small overlap, cross-study normalization methods are based on simplified assumptions and are limited in their applicability and quality. However, in many cases the benefit of an increased sample size outweighs the loss of information due to the normalization process (e.g. see the paper by Shabalin et al., Bioinformatis, 2008). Please click on the question marks behind each normalization method to obtain a short description of each available approach. You can either upload your own microarray data (see uploading your own data) or first download the example data set.
Settings: Some of the methods don't require any parameters, but others depend on settings for which standard parameters are suggested on the interface and can be adjusted by the user. The help windows for the different methods provide more information on the possible adjustments.
Output: The main output of the module is the downloadable transformed dataset resulting from the algorithmic combination of the two input data sets. The combined data can also directly be forwarded to one of the other analysis modules (clustering, prediction, feature selection, etc.). Additionally, various plots are generated to evaluate the normalization results. Density plots show the estimated densities of the input data sets and the transformed output data sets and quantile-quantile plots compare the distributions before and after the transformation. For the parametric version of the Empirical Bayes (EB) method, the validity of the parametric model can be verified based on similar plots to decide whether the non-parametric variant of the algorithm should be preferred to the parametric variant.
Uploading your own data: In order to use ArrayMining.net with your own data you need to upload a compressed zip-file containing two tab- or space-delimited text-files with pre-normalized Microarray data in the following simple matrix-format (see Fig. 1):
You can download an example data file here (use right-click and "Save as"). The columns must correspond to the samples and the rows to the genes. The first column contains the gene identifiers (a unique label per gene) and the last row the class information for the samples (multiple samples can have the same class label). The rest of the matrix should contain normalized expression values obtained using any of the common Microarray normalization methods (e.g. VSN, RMA, GCRMA, MAS, dChip, etc.). The gene identifiers can be any one of the following: Affymetrix ID, ENTREZ ID, GENBANK ID. You can also use your own identifiers; however, in this case you won't obtain any links to functional annotation data bases. The class labels are only needed if a supervised analysis will be performed after cross-study normalization. They can be any alphanumeric strings or symbols (e.g. "tumour" and "healthy", or "1","2", "3", or "leukemia1", "leukemia2", "leukemia3", etc.) and the symbols for the same classes need to match within and across the data sets. The last row containing the class labels has to begin with a user-defined "sample type"-label, e.g. "phenotypes", "tumours" or just "labels".
Please contact us, should you experience any kind of problems when uploading or analyzing your data.
Terms and Conditions [X]
This is ArrayMining version 1.0
This service is free for academic and non-commercial use.
If you intend to use results obtained with ArrayMining.net for a publication, please acknowledge/cite our paper:
E. Glaab, J. Garibaldi, N. Krasnogor
ArrayMining: a modular web-application for microarray analysis combining ensemble and consensus methods with cross-study normalization
BMC Bioinformatics, Vol. 10, No. 1. (2009), 358.
We cannot give any guarantee that ArrayMining is free of errors or bugs, but we perform integretiy checks and provide validition measures for each analysis module.
If you have any comments or experience problems accessing the server, please do not hesitate to contact us.
We take reasonable measures to protect your data, which includes your dataset, tasks, results and all further information that you provide us, and we will not make them available to any third party.
We collect some data for statistical purposes, which includes your IP address and the tasks performed. This data is never forwarded to third parties.
All your data, apart from data that we keep for statistical purposes, will be deleted after the expiration time.
Empirical Bayes method [X]
The Empirical Bayes (EB, ComBat) method by Johnson et al. combines microarray data sets by employing parametric and non-parametric empirical Bayes methods to filter out batch effects. The parameters for a location- and scale-adjustment model (which represent the additive and multiplicative batch effects) are estimated by pooling information across genes in each batch to shrink the parameter estimates towards the overall mean of the estimates across genes. This approach provides an increased robustness against outliers and can be therefore be applied to data sets with small samples sizes (for more details see the references).
- Johnson, W.E. and Li, C. and Rabinovic, A. (2007), Adjusting batch effects in microarray expression data using empirical Bayes methods, Biostatistics, 8, p. 118
XPN method [X]
The XPN cross-study normalization method by Shabalin et al. uses linked clustering of the genes and samples and a maximum likelihood approach to estimate the parameters of a block-linear error model. The underlying assumption is that the observed expression values for the genes in samples of different studies can be interpreted as scaled and shifted block means (plus additional gaussian noise), where the block means are constant across several genes and samples, and the same in each study. For more details about the method and a comparative evaluation with other approaches, please refer to the original publication by Shabalin et al. (see references)
- Shabalin , A. A., Tjelmeland, H., Fan, C., Perou, C. M., and Nobe, A. B. (2008). Merging two gene-expression studies via cross-platform normalization. Bioinformatics, 24, p. 1154-1160
Median Rank Score Normalization (MNORM) [X]
The Median Rank Score Normalization method (MNORM) by Warnat et al. is a very fast and simple approach which replaces the expression values for a single study by median expression values of genes from another study (the "reference" study). First, the relative rank of the expression values to be replaced in the non- reference set is computed. In the second step, these expression values are replaced by the median-expression values from the reference-study whose positions in a sorted vector correspond to the ranks in the non-reference set. More details can be found in the paper by Warnat et al.
- Warnat, P. and Eils, R. and Brors, B. (2005), Cross-platform analysis of cancer microarray data improves gene expression based classification of phenotypes, BMC Bioinformatics, 6, p. 265
Quantile discretization normalization [X]
The quantile discretization method for cross-study normalization by Warnat et al. combines microarray data sets by first discretizing them. The expression values for each study are assigned to 8 different bins given by the the quantiles of the array expression values as cut-points. To obtain the final discretized values, the two central bins are merged and all expression values are replaced by the number of the bin they were assigned to. This simple approach can result in a considerable loss of information, but can be useful when the data is very noisy or the user is intending to apply statistical analysis methods which require discretized values as input.
NorDi discretization normalization [X]
The NorDi method by Martinez et al. is a discretization approach, which can also be used as a simply means to combine data from different studies (similar to the QDISC method). NorDi (= Normalized Discretization) improves the normality of the gene expression values (on logarithmic scale) by removing outliers using the Grubbs method and the Jaque�Bera normality test. The method then determines significantly over- or under-expressed genes by computing z-scores (Yang et al., 2002) for each gene. The original gene expression values are then discretized based on z-score thresholds using three intervals ("under-expressed", "normal", "over-expressed").
- Martinez, R. and Pasquier, N. and Pasquier, C. (2008), GenMiner: mining non-redundant association rules from integrated gene expression data and annotations, Bioinformatics, 24, p. 2643
ArrayMining - Online Microarray Data Mining
Ensemble and Consensus Analysis Methods for Gene Expression Data
Cross-Study Normalization
This module provides methods to combine microarray data from different studies and platforms together into a single data set. The input data sets need to be derived from the same tissue type under comparable biological conditions and the genetic probes must overlap. To obtain instructions click help.
1) Data Sets
Upload your data:
Please select a zip-file on your computer that contains both input data sets:
Get help on the input format Download example data
2) Cross-study normalization method
EB XPN
MNORM QDISC
NorDi
3) Parameters
EB Parameters:
Use parametric adjustments: yes no
Create prior plots: yes no
4) E-Mail Notification (optional)
XPN Parameters:
Number of gene clusters:
Number of sample clusters:
Number of iterations (runtime/quality trade-off):


text:
Bob's Burgers Review: "The Kids Rob a Train"
(Episode 4.15)
By Robert Ham | March 31, 2014 | 2:01pm
I never thought I'd see the day when I'd be underwhelmed by a Bob's Burgers episode, yet … it's happened this week. All thanks to the Belcher gang getting on a train together and letting some pretty silly hijinks ensue.
The train in question is a wine train, a four-hour rail trip through the woods and back. The ideal place for Bob and Linda to have a babysitter and lots of alcohol at their disposal, and for the kids to have an adventure trying to steal the kitchen's store of chocolate.
It's always fun to put Bob and Linda into these types of situations, the working class couple trying to punch above their weight, so to speak. And in this case, the show didn't disappoint. The two try to make friends with Rick, a snooty oenophile who is on board to swish and slurp and gargle his way through a wine flight. Linda invites him over to their table ("You can give us tips on how to get tipsy!") and things go quickly awry as Bob gets frustrated with his attitude. The natural solution? A wine-off.
Poor Bob has no hope of winning, but it allowed for plenty of hilarious chatter from Rick coaxing the name of his wine out of his tastebuds. ("Hmmm…you have got a lot going on girl … speak to me….") The contest comes down to a final winner-take-all bonus round where Linda presents them both with a glass, and Bob nails it on the first sip. Rick keeps drinking and drinking trying to figure it out before it is revealed that they both sipped on wine culled from the spit bucket. How did Bob know that? Says Linda: "Because we went and saw Sideways and then went to a winery and I bet Bob he wouldn't drink from the spit bucket and he did!"
Shame that the episode didn't just stick with the adults as the whole train robbery bit with the kids wasn't all that exciting. The three gang up with Regular-Sized Rudy who is stuck in the juice caboose while his dad is on a date to liberate the bars of chocolate from the front of the train. It's a deeply silly idea and seemed, as ever, just an excuse for the kids to toss off as many weird asides as they could. Though a success in that regard, I probably laughed less at this episode than any of the 14 that preceded it. A better batting average than most sitcoms, to be sure, but a slight disappointment for one of TV's finest half-hours.
Robert Ham is a Portland-based freelance writer and regular contributor to Paste. You can follow him on Twitter.
fox broadcasting
h. jon benjamin
Also in TV
Miss Scarlet and the Duke: A Placidly Pleasant Victorian Crime Series By Allison Keene January 15, 2021 | 11:37am
WandaVision: A Mesmerizing, Technicolor-Tinged Emotional Horror By Allison Keene January 14, 2021 | 12:00pm
Search Party Season 4: HBO Max's Millennial Satire Takes A Dark Turn for the Better By Fletcher Peters January 12, 2021 | 10:11am
All Creatures Great and Small on PBS Masterpiece Is Just What the Doctor Ordered By Allison Keene January 8, 2021 | 10:20am
In Season 3 American Gods Has Lost the Magic It Once Had By Rae Nudson January 7, 2021 | 11:37am
Dickinson Season 2: Smarter, Weirder, Warmer, Sexier By Alexis Gunderson January 6, 2021 | 10:46am
Seinfeld Gets an Unofficial Reunion in the Style of Twin Peaks: The Return By Garrett Martin January 11, 2021
All American: 6 Reasons to Catch Up on The CW's Soapy, Sunny High School Football Drama Right Now By Alexis Gunderson January 14, 2021
The 7 Best Shows to Stream on Discovery+ Right Now By Kaitlin Thomas January 7, 2021
Bridgerton: The 10 Most Pearl-Clutching Moments, Ranked By Radhika Menon December 25, 2020
WandaVision: A Mesmerizing, Technicolor-Tinged Emotional Horror By Allison Keene January 14, 2021
The Best Sitcoms on Netflix Right Now (January 2021) By Garrett Martin and Paste Staff January 8, 2021
Miss Scarlet and the Duke: A Placidly Pleasant Victorian Crime Series By Allison Keene January 15, 2021
The 36 Best TV Shows on HBO Max (That Aren't HBO) By Paste Staff & TV Writers January 15, 2021
More TV Most Popular
Mr. Wilford's Back in First Snowpiercer Season 2 Trailer By Jim Vorel January 11, 2021
Danny Boyle to Direct Sex Pistols Biopic Series at FX By Fletcher Peters January 11, 2021
Roku Absorbs Quibi Library, Including Never-Before-Seen Content By Fletcher Peters January 8, 2021
Bob's Burgers Lead Character Designer Dave Creek Dies After Skydiving Accident By Jim Vorel January 8, 2021
More Comedy News


or in other words the real lives behind of some your favorite bloggers!
to Mommy By Day, Crafter By Night & check it out!
I was grateful for the chance to take part in the series.
So if you missed it over there, here's my think outside of the blog post.
I am so grateful for this opportunity to "think outside the blog"!
Most of you know me from this blog, but actually I have another blog.
to keep up the craft blog would lose BIGTIME.
The blog I'm talking about is our family blog.
Annnnd yes, it wins hands down as my favorite blog.
I was determined not to let it affect our family blog.
I love keeping a journal of my little family!
They are what inspire me!
They inspire me everyday to do better & be better.
Here are a few pictures from our family blog!
My husband, Clay & I were college sweethearts.
but I seriously love him a million times more today!
He inspires me, supports me & loves me!
What else could a girl ask for??!! I feel so blessed to have him in my life.
working hard & just having a great time being together.
to be a better mom...a better person!
I love watching them grow into their own person.


text:
Hannity's No Longer A Fan Of 'Lock Her Up' Now That Pelosi's The One Chanting It
By Nicole Lafond
June 7, 2019 9:34 a.m.
House Speaker Nancy Pelosi's (D-CA) comments to her caucus about imprisoning President Trump were apparently too much for Fox News' Sean Hannity, one of the most frequent enabler of Trump's "Lock Her Up!" calls against Hillary Clinton.
During his opening monologue on Thursday evening, Hannity decried the "beyond despicable" comments from Pelosi, who reportedly told her party earlier this week that she wanted to pump the brakes on impeachment to make room for a more consequential move: a 2020 defeat and a possible indictment.
"Speaker Nancy Pelosi telling senior Democrats she would like to see Trump behind bars," he said. "Based on no actual crime she wants to a political opponent locked up in prison? Um that happens in banana republics. Beyond despicable behavior."
While Hannity may not have explicitly made calls for imprisoning Clinton, he fervently covered the investigation into her emails and has stood in support of Republican efforts to keep the Clinton probe alive.
Hannity's apparently no longer a fan of "Lock Her Up" now that Pelosi's doing it pic.twitter.com/EUmQ7ptIIu
— TPM Livewire (@TPMLiveWire) June 7, 2019
Nicole Lafond (@Nicole_Lafond) is a senior newswriter for TPM based in New York. She has a master's degree in journalism from Columbia University and previously worked as an education reporter at The News-Gazette in Illinois.
Fox NewsNancy PelosiSean Hannitytv clip


text:
Q: how to run document.getelementbyclassname() while using node js Im learning node js and i am trying to make a mega menu appear when hovering over a link in the header. I understand that 'document.getElementByClassName' won't work because of ssr but I do not know the solution to my problem.
Ive tried to use the dynamic import from the docs but dont quite get how to implement it into my code. Below is a picture.
image

A: If you are using the current version of nextjs, you don't have to worry about SSR when your page component doesn't load anything dynamically. Just leave the _app.js and _document.js to its default since you are a beginner.
create a folder called components outside of the pages folder. Inside that folder create a file named Base.js and paste this code

import React, {
  useState
} from "react";

const Menu = () => {
  const [hide, setHide] = useState(true);

  const showMenu = (e) => {
    e.preventDefault();
    setHide(false);
  };

  const hideMenu = (e) => {
    e.preventDefault();
    setHide(true);
  };

  return ( <
    div className = "container" >
    <
    div className = "dropdown"
    onMouseEnter = {
      showMenu
    }
    onMouseLeave = {
      hideMenu
    } >
    Menu <
    /div> <
    ul className = "menu-area"
    style = {
      {
        display: hide ? "none" : "block"
      }
    } >
    <
    li > Home < /li> <
    li > Home < /li> <
    li > Home < /li> <
    li > Home < /li> < /
    ul > <
    /div>
  );
};

const Base = ({
  children
}) => {
  return ( <
    div >
    <
    Menu / > {
      children
    } <
    /div>
  );
};

export default Base;
<script src="https://cdnjs.cloudflare.com/ajax/libs/react/16.6.3/umd/react.production.min.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/react-dom/16.6.3/umd/react-dom.production.min.js"></script>

Now you can import the Base component to every other component and wrap everything in those components inside the Base component like this -> <Base> /*your code */</Base>