Broadcasting on Random Directed Acyclic Graphs
© 1963-2012 IEEE. We study the following generalization of the well-known model of broadcasting on trees. Consider an infinite directed acyclic graph (DAG) with a unique source vertex X. Let the collection of vertices at distance k from X be called the k th layer, and suppose every non-source vertex...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2021
|
| Online Access: | https://hdl.handle.net/1721.1/136548 |
| _version_ | 1826190322792660992 |
|---|---|
| author | Makur, Anuran Mossel, Elchanan Polyanskiy, Yury |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Makur, Anuran Mossel, Elchanan Polyanskiy, Yury |
| author_sort | Makur, Anuran |
| collection | MIT |
| description | © 1963-2012 IEEE. We study the following generalization of the well-known model of broadcasting on trees. Consider an infinite directed acyclic graph (DAG) with a unique source vertex X. Let the collection of vertices at distance k from X be called the k th layer, and suppose every non-source vertex has indegree d2. At layer 0, the source vertex is given a random bit. At layer k1, each vertex receives d bits from its parents in the (k-1) th layer, which are transmitted along edges that are independent binary symmetric channels (BSCs) with crossover probability δ 012. Each vertex combines its d noisy inputs using a deterministic d -ary Boolean processing function that generates the value at the vertex. The goal is to be able to reconstruct the original bit X with probability of error bounded away from 12 using the values of all vertices at an arbitrarily deep layer k. This question is closely related to models of reliable computation and storage, and information flow in biological networks. In this paper, we treat the case of randomly constructed DAGs, for which we show that broadcasting is only possible if the BSC noise level δ is below a certain (degree and function dependent) critical threshold. For d3, and random DAGs with layers of size Ω k and majority processing functions, we identify the critical threshold. For d = 2, we establish a similar result for the NAND processing function. We also prove a partial converse result for odd d3 illustrating that the identified thresholds are impossible to improve by selecting different processing functions if the decoder is restricted to using a single vertex's value. Finally, for any BSC noise level δ, we construct explicit DAGs (using regular bipartite lossless expander graphs) with bounded degree and layers of size Θk admitting reconstruction. In particular, we show that the first r layers of such DAGs can be generated in either deterministic quasi-polynomial time or randomized polylogarithmic time in r. These results portray a doubly-exponential advantage for storing a bit in bounded degree DAGs compared to trees, where d = 1 but layer sizes need to grow exponentially with depth in order for broadcasting to be possible. |
| first_indexed | 2024-09-23T08:38:30Z |
| format | Article |
| id | mit-1721.1/136548 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T08:38:30Z |
| publishDate | 2021 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/1365482023-12-22T19:05:53Z Broadcasting on Random Directed Acyclic Graphs Makur, Anuran Mossel, Elchanan Polyanskiy, Yury Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Department of Mathematics © 1963-2012 IEEE. We study the following generalization of the well-known model of broadcasting on trees. Consider an infinite directed acyclic graph (DAG) with a unique source vertex X. Let the collection of vertices at distance k from X be called the k th layer, and suppose every non-source vertex has indegree d2. At layer 0, the source vertex is given a random bit. At layer k1, each vertex receives d bits from its parents in the (k-1) th layer, which are transmitted along edges that are independent binary symmetric channels (BSCs) with crossover probability δ 012. Each vertex combines its d noisy inputs using a deterministic d -ary Boolean processing function that generates the value at the vertex. The goal is to be able to reconstruct the original bit X with probability of error bounded away from 12 using the values of all vertices at an arbitrarily deep layer k. This question is closely related to models of reliable computation and storage, and information flow in biological networks. In this paper, we treat the case of randomly constructed DAGs, for which we show that broadcasting is only possible if the BSC noise level δ is below a certain (degree and function dependent) critical threshold. For d3, and random DAGs with layers of size Ω k and majority processing functions, we identify the critical threshold. For d = 2, we establish a similar result for the NAND processing function. We also prove a partial converse result for odd d3 illustrating that the identified thresholds are impossible to improve by selecting different processing functions if the decoder is restricted to using a single vertex's value. Finally, for any BSC noise level δ, we construct explicit DAGs (using regular bipartite lossless expander graphs) with bounded degree and layers of size Θk admitting reconstruction. In particular, we show that the first r layers of such DAGs can be generated in either deterministic quasi-polynomial time or randomized polylogarithmic time in r. These results portray a doubly-exponential advantage for storing a bit in bounded degree DAGs compared to trees, where d = 1 but layer sizes need to grow exponentially with depth in order for broadcasting to be possible. 2021-10-27T20:35:53Z 2021-10-27T20:35:53Z 2020 2021-03-09T20:06:12Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/136548 en 10.1109/TIT.2019.2935772 IEEE Transactions on Information Theory Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) arXiv |
| spellingShingle | Makur, Anuran Mossel, Elchanan Polyanskiy, Yury Broadcasting on Random Directed Acyclic Graphs |
| title | Broadcasting on Random Directed Acyclic Graphs |
| title_full | Broadcasting on Random Directed Acyclic Graphs |
| title_fullStr | Broadcasting on Random Directed Acyclic Graphs |
| title_full_unstemmed | Broadcasting on Random Directed Acyclic Graphs |
| title_short | Broadcasting on Random Directed Acyclic Graphs |
| title_sort | broadcasting on random directed acyclic graphs |
| url | https://hdl.handle.net/1721.1/136548 |
| work_keys_str_mv | AT makuranuran broadcastingonrandomdirectedacyclicgraphs AT mosselelchanan broadcastingonrandomdirectedacyclicgraphs AT polyanskiyyury broadcastingonrandomdirectedacyclicgraphs |