Linear Programs with Polynomial Coefficients and Applications to 1D Cellular Automata
share
Given a matrix A and vector b with polynomial entries in d real variables δ=(δ_1,…,δ_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 δ∈ U there exists x satisfying A(δ)x≥ b(δ) entry-wise. For d=1 we construct a polynomial time algorithm for deciding local feasibility. For d ≥ 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 η_t ∈{0,1}^ℤ the next state η_t+1(n) at each vertex n∈ℤ is obtained by η_t+1(n)= NAND(BSC_δ(η_t(n-1)), BSC_δ(η_t(n))). Here the binary symmetric channel BSC_δ takes a bit as input and flips it with probability δ (and leaves it unchanged with probability 1-δ). We also consider the problem of broadcasting information on the 2D-grid of noisy binary-symmetric channels BSC_δ, where each node may apply an arbitrary processing function to its input bits. We prove that there exists δ_0'>0 such that for all noise levels 0<δ<δ_0' it is impossible to broadcast information for any processing function, as conjectured in Makur, Mossel, Polyanskiy (ISIT 2021).
READ FULL TEXT