Linear Programs with Polynomial Coefficients and Applications to 1D Cellular Automata

Guy Bresler, Chenghao Guo, Yury Polyanskiy

Given a matrix $A$ and vector $b$ with polynomial entries in $d$ real variables $\delta =({\delta }_1,\dots ,{\delta }_d)$ we consider the following notion of feasibility: the pair $(A,b)$ is locally fe…