Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Linear Programs with Polynomial Coefficients and Applications to 1D
  Cellular Automata   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.
  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$).
  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
in Makur, Mossel, Polyanskiy (ISIT 2021).

24
The categories of this paper are: dg-ga
9
The categories of this paper are: nlin
19
The categories of this paper are: eess
6
The categories of this paper are: astro-ph
4
The categories of this paper are: cond-mat
35
The categories of this paper are: mtrl-th
27
The categories of this paper are: comp-gas
3
The categories of this paper are: physics
10
The categories of this paper are: q-bio
22
The categories of this paper are: chao-dyn
14
The categories of this paper are: math-ph
7
The categories of this paper are: hep-th
13
The categories of this paper are: quant-ph
37
The categories of this paper are: supr-con
26
The categories of this paper are: bayes-an
5
The categories of this paper are: gr-qc