{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/30162"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/30162","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"Network coding","abstract":"In the network coding problem, there are k commodities each with an associated message Mi, a set of sources that know Mi and a set of sinks that request Mi. Each edge in the graph may transmit any function of the messages. These functions define a network coding solution. We explore three topics related to network coding. First, for a model in which the messages and the symbols transmitted on edges are all from the same alphabet [sigma], we prove lower bounds on [the absolute value of sigma]. In one case, we prove [the absolute value of sigma] needs to be doubly-exponential in the size of the network. We also show that it is NP-hard to determine the smallest alphabet size admitting a solution. We then explore the types of functions that admit solutions. In a linear solution over a finite field F the symbol transmitted over each edge is a linear combination of the messages. We show that determining if there exists a linear solution is NP-hard for many classes of network coding problems. As a corollary, we obtain a solvable instance of the network coding problem that does not admit a linear solution over any field F. We then define a model of network coding in which messages are chosen from one alphabet, [gamma], and edges transmit symbols from another alphabet, [sigma]. In this model, we define the rate of a solution as log [gamma absolute value]/ log [sigma absolute value]. We then explore techniques to upper bound the maximum achievable rate for instances defined on directed and undirected graphs. We present a network coding instance in an undirected graph in which the maximum achievable rate is strictly smaller than the sparsity of the graph.","abstract_html":"In the network coding problem, there are k commodities each with an associated message Mi, a set of sources that know Mi and a set of sinks that request Mi. Each edge in the graph may transmit any function of the messages. These functions define a network coding solution. We explore three topics related to network coding. First, for a model in which the messages and the symbols transmitted on edges are all from the same alphabet [sigma], we prove lower bounds on [the absolute value of sigma]. In one case, we prove [the absolute value of sigma] needs to be doubly-exponential in the size of the network. We also show that it is NP-hard to determine the smallest alphabet size admitting a solution. We then explore the types of functions that admit solutions. In a linear solution over a finite field F the symbol transmitted over each edge is a linear combination of the messages. We show that determining if there exists a linear solution is NP-hard for many classes of network coding problems. As a corollary, we obtain a solvable instance of the network coding problem that does not admit a linear solution over any field F. We then define a model of network coding in which messages are chosen from one alphabet, [gamma], and edges transmit symbols from another alphabet, [sigma]. In this model, we define the rate of a solution as log [gamma absolute value]/ log [sigma absolute value]. We then explore techniques to upper bound the maximum achievable rate for instances defined on directed and undirected graphs. We present a network coding instance in an undirected graph in which the maximum achievable rate is strictly smaller than the sparsity of the graph.","abstract_has_math":false,"creators":["Lehman, April Rasala, 1977-"],"institution":"Massachusetts Institute of Technology","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":"Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science","school":null,"contributors":[],"advisors":["Madhu Sudan."],"committee_chairs":[],"committee_members":[],"year":2005,"date_issued":"2005","date_published":"2005","updated_at":"2026-07-22T22:21:30Z","subjects":["Electrical Engineering and Computer Science."],"languages":["eng"],"rights":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."],"rights_urls":["http://dspace.mit.edu/handle/1721.1/7582"],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/1721.1/30162","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Madhu Sudan."]},{"key":"dc:contributor.department","label":"Department","values":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science"]},{"key":"dc:contributor.other","label":"Dc Contributor Other","values":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."]},{"key":"dc:creator","label":"Author","values":["Lehman, April Rasala, 1977-"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2006-03-24T18:25:21Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2006-03-24T18:25:21Z"]},{"key":"dc:date.issued","label":"Date","values":["2005"]},{"key":"dc:publisher","label":"Institution","values":["Massachusetts Institute of Technology"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Electrical Engineering and Computer Science."]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://dspace.mit.edu/handle/1721.1/7582"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/1721.1/30162"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2005.","Includes bibliographical references (p. 115-118)."]},{"key":"dc:description.abstract","label":"Abstract","values":["In the network coding problem, there are k commodities each with an associated message Mi, a set of sources that know Mi and a set of sinks that request Mi. Each edge in the graph may transmit any function of the messages. These functions define a network coding solution. We explore three topics related to network coding. First, for a model in which the messages and the symbols transmitted on edges are all from the same alphabet [sigma], we prove lower bounds on [the absolute value of sigma]. In one case, we prove [the absolute value of sigma] needs to be doubly-exponential in the size of the network. We also show that it is NP-hard to determine the smallest alphabet size admitting a solution. We then explore the types of functions that admit solutions. In a linear solution over a finite field F the symbol transmitted over each edge is a linear combination of the messages. We show that determining if there exists a linear solution is NP-hard for many classes of network coding problems. As a corollary, we obtain a solvable instance of the network coding problem that does not admit a linear solution over any field F. We then define a model of network coding in which messages are chosen from one alphabet, [gamma], and edges transmit symbols from another alphabet, [sigma]. In this model, we define the rate of a solution as log [gamma absolute value]/ log [sigma absolute value]. We then explore techniques to upper bound the maximum achievable rate for instances defined on directed and undirected graphs. We present a network coding instance in an undirected graph in which the maximum achievable rate is strictly smaller than the sparsity of the graph."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["Ph.D."]},{"key":"dc:format.mimetype","label":"Dc Format Mimetype","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Network coding"]}]}],"canonical_facts":{"dc:contributor.advisor":["Madhu Sudan."],"dc:contributor.department":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science"],"dc:contributor.other":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."],"dc:creator":["Lehman, April Rasala, 1977-"],"dc:date.accessioned":["2006-03-24T18:25:21Z"],"dc:date.available":["2006-03-24T18:25:21Z"],"dc:date.issued":["2005"],"dc:description":["Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2005.","Includes bibliographical references (p. 115-118)."],"dc:description.abstract":["In the network coding problem, there are k commodities each with an associated message Mi, a set of sources that know Mi and a set of sinks that request Mi. Each edge in the graph may transmit any function of the messages. These functions define a network coding solution. We explore three topics related to network coding. First, for a model in which the messages and the symbols transmitted on edges are all from the same alphabet [sigma], we prove lower bounds on [the absolute value of sigma]. In one case, we prove [the absolute value of sigma] needs to be doubly-exponential in the size of the network. We also show that it is NP-hard to determine the smallest alphabet size admitting a solution. We then explore the types of functions that admit solutions. In a linear solution over a finite field F the symbol transmitted over each edge is a linear combination of the messages. We show that determining if there exists a linear solution is NP-hard for many classes of network coding problems. As a corollary, we obtain a solvable instance of the network coding problem that does not admit a linear solution over any field F. We then define a model of network coding in which messages are chosen from one alphabet, [gamma], and edges transmit symbols from another alphabet, [sigma]. In this model, we define the rate of a solution as log [gamma absolute value]/ log [sigma absolute value]. We then explore techniques to upper bound the maximum achievable rate for instances defined on directed and undirected graphs. We present a network coding instance in an undirected graph in which the maximum achievable rate is strictly smaller than the sparsity of the graph."],"dc:description.degree":["Ph.D."],"dc:format.mimetype":["application/pdf"],"dc:identifier.uri":["http://hdl.handle.net/1721.1/30162"],"dc:language.iso":["eng"],"dc:publisher":["Massachusetts Institute of Technology"],"dc:rights":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."],"dc:rights.uri":["http://dspace.mit.edu/handle/1721.1/7582"],"dc:subject":["Electrical Engineering and Computer Science."],"dc:title":["Network coding"],"dc:type":["Thesis"]},"updated_at":"2026-07-22T22:21:30Z"}