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 δ=(δ₁,…,δ subscript 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. Fo...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Published: |
Massachusetts Institute of Technology
2022
|
| Online Access: | https://hdl.handle.net/1721.1/144875 |
| _version_ | 1826198304871940096 |
|---|---|
| author | Guo, Chenghao |
| author2 | Bresler, Guy |
| author_facet | Bresler, Guy Guo, Chenghao |
| author_sort | Guo, Chenghao |
| collection | MIT |
| description | Given a matrix A and vector b with polynomial entries in d real variables δ=(δ₁,…,δ subscript 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 ηₜ∈{0,1}ℤ the next state ηₜ₊₁(n) at each vertex n∈ superscript ℤ is obtained by ηₜ₊₁(n)=NAND(BSCδ(ηₜ(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−δ). It is shown that there exists 𝛿₀ > 0 such that for all 0 < 𝛿 < 𝛿₀ the distribution of 𝜂ₜ converges to a unique stationary measure irrespective of the initial condition 𝜂₀.
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 such that for all noise levels 0<δ<δ′₀ it is impossible to broadcast information for any processing function, as conjectured in Makur, Mossel, Polyanskiy (ISIT 2021). |
| first_indexed | 2024-09-23T11:02:46Z |
| format | Thesis |
| id | mit-1721.1/144875 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T11:02:46Z |
| publishDate | 2022 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1448752022-08-30T03:44:50Z Linear Programs with Polynomial Coefficients and Applications to 1D Cellular Automata Guo, Chenghao Bresler, Guy Polyanskiy, Yury Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Given a matrix A and vector b with polynomial entries in d real variables δ=(δ₁,…,δ subscript 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 ηₜ∈{0,1}ℤ the next state ηₜ₊₁(n) at each vertex n∈ superscript ℤ is obtained by ηₜ₊₁(n)=NAND(BSCδ(ηₜ(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−δ). It is shown that there exists 𝛿₀ > 0 such that for all 0 < 𝛿 < 𝛿₀ the distribution of 𝜂ₜ converges to a unique stationary measure irrespective of the initial condition 𝜂₀. 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 such that for all noise levels 0<δ<δ′₀ it is impossible to broadcast information for any processing function, as conjectured in Makur, Mossel, Polyanskiy (ISIT 2021). S.M. 2022-08-29T16:17:51Z 2022-08-29T16:17:51Z 2022-05 2022-06-21T19:25:58.408Z Thesis https://hdl.handle.net/1721.1/144875 0000-0002-4440-3229 In Copyright - Educational Use Permitted Copyright MIT http://rightsstatements.org/page/InC-EDU/1.0/ application/pdf Massachusetts Institute of Technology |
| spellingShingle | Guo, Chenghao Linear Programs with Polynomial Coefficients and Applications to 1D Cellular Automata |
| title | Linear Programs with Polynomial Coefficients and Applications to 1D Cellular Automata |
| title_full | Linear Programs with Polynomial Coefficients and Applications to 1D Cellular Automata |
| title_fullStr | Linear Programs with Polynomial Coefficients and Applications to 1D Cellular Automata |
| title_full_unstemmed | Linear Programs with Polynomial Coefficients and Applications to 1D Cellular Automata |
| title_short | Linear Programs with Polynomial Coefficients and Applications to 1D Cellular Automata |
| title_sort | linear programs with polynomial coefficients and applications to 1d cellular automata |
| url | https://hdl.handle.net/1721.1/144875 |
| work_keys_str_mv | AT guochenghao linearprogramswithpolynomialcoefficientsandapplicationsto1dcellularautomata |