  Given a matrix $A$ and vector $b$ with polynomial entries in $d$ real
variables $\delta=(\delta_1,\ldots,\delta_d)$ we consider the following notion
of feasibility: the pair $(A,b)$ is locally feasible if there exists an open
neighborhood $U$ of $0$ such that for every $\delta\in U$ there exists $x$
satisfying $A(\delta)x\ge b(\delta)$ entry-wise. For $d=1$ we construct a
polynomial time algorithm for deciding local feasibility. For $d \ge 2$ we show
local feasibility is NP-hard. This also gives the first polynomial-time
algorithm for the asymptotic linear program problem introduced by Jeroslow in
1973.
  As an application (which was the primary motivation for this work) we give a
computer-assisted proof of ergodicity of the following elementary 1D cellular
automaton: given the current state $\eta_t \in \{0,1\}^{\mathbb{Z}}$ the next
state $\eta_{t+1}(n)$ at each vertex $n\in \mathbb{Z}$ is obtained by
$\eta_{t+1}(n)= \text{NAND}\big(\text{BSC}_\delta(\eta_t(n-1)),
\text{BSC}_\delta(\eta_t(n))\big)$. Here the binary symmetric channel
$\text{BSC}_\delta$ takes a bit as input and flips it with probability $\delta$
(and leaves it unchanged with probability $1-\delta$). It is shown that there
exists $\delta_0>0$ such that for all $0<\delta<\delta_0$ the distribution of
$\eta_t$ converges to a unique stationary measure irrespective of the initial
condition $\eta_0$.
  We also consider the problem of broadcasting information on the 2D-grid of
noisy binary-symmetric channels $\text{BSC}_\delta$, where each node may apply
an arbitrary processing function to its input bits. We prove that there exists
$\delta_0'>0$ such that for all noise levels $0<\delta<\delta_0'$ it is
impossible to broadcast information for any processing function, as conjectured
by Makur, Mossel and Polyanskiy.
