{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/95346"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/95346","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Combinatorial channels from partially ordered sets","abstract":"A central task of coding theory is the design of schemes to reliably transmit data though space, via communication systems, or through time, via storage systems. Our goal is to identify and exploit structural properties common to a wide variety of coding problems, classical and modern, using the framework of partially ordered sets. We represent adversarial error models as combinatorial channels, form combinatorial channels from posets, identify a structural property of posets that leads to families of channels with the same codes, and bound the size of codes by optimizing over a family of equivalent channels. A large number of previously studied coding problems that fit into this framework. This leads to a new upper bound on the size of s-deletion correcting codes. We use a linear programming framework to obtain sphere-packing upper bounds when there is little underlying symmetry in the coding problem. Finally, we introduce and investigate a strong notion of poset homomorphism: locally bijective cover preserving maps. We look for maps of this type to and from the subsequence partial order on q-ary strings.","abstract_html":"A central task of coding theory is the design of schemes to reliably transmit data though space, via communication systems, or through time, via storage systems. Our goal is to identify and exploit structural properties common to a wide variety of coding problems, classical and modern, using the framework of partially ordered sets. We represent adversarial error models as combinatorial channels, form combinatorial channels from posets, identify a structural property of posets that leads to families of channels with the same codes, and bound the size of codes by optimizing over a family of equivalent channels. A large number of previously studied coding problems that fit into this framework. This leads to a new upper bound on the size of s-deletion correcting codes. We use a linear programming framework to obtain sphere-packing upper bounds when there is little underlying symmetry in the coding problem. Finally, we introduce and investigate a strong notion of poset homomorphism: locally bijective cover preserving maps. We look for maps of this type to and from the subsequence partial order on q-ary strings.","abstract_has_math":false,"creators":["Cullina, Daniel Francis"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Electrical & Computer Engr","degree_department":null,"school":null,"contributors":["Kiyavash, Negar","Barg, Alexander","Hajek, Bruce","Milenkovic, Olgica","Srikant, R."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2017,"date_issued":"2017-03-01T15:49:08Z","date_published":"2017-03-01T15:49:08Z","updated_at":"2026-07-22T22:26:37Z","subjects":["coding theory","combinatorics, partially ordered set","deletion errors"],"languages":["en"],"rights":["Copyright 2016 Daniel Cullina"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/95346","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Kiyavash, Negar","Barg, Alexander","Hajek, Bruce","Milenkovic, Olgica","Srikant, R."]},{"key":"dc:creator","label":"Author","values":["Cullina, Daniel Francis"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2017-03-01T15:49:08Z","2016-11-28","2016-12"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical & Computer Engr"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["coding theory","combinatorics, partially ordered set","deletion errors"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2016 Daniel Cullina"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/95346"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["A central task of coding theory is the design of schemes to reliably transmit data though space, via communication systems, or through time, via storage systems. Our goal is to identify and exploit structural properties common to a wide variety of coding problems, classical and modern, using the framework of partially ordered sets. We represent adversarial error models as combinatorial channels, form combinatorial channels from posets, identify a structural property of posets that leads to families of channels with the same codes, and bound the size of codes by optimizing over a family of equivalent channels. A large number of previously studied coding problems that fit into this framework. This leads to a new upper bound on the size of s-deletion correcting codes. We use a linear programming framework to obtain sphere-packing upper bounds when there is little underlying symmetry in the coding problem. Finally, we introduce and investigate a strong notion of poset homomorphism: locally bijective cover preserving maps. We look for maps of this type to and from the subsequence partial order on q-ary strings.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2017-02-28 without embargo terms","The student, Daniel Cullina, accepted the attached license on 2016-11-23 at 09:35.","The student, Daniel Cullina, submitted this Dissertation for approval on 2016-11-23 at 09:41.","This Dissertation was approved for publication on 2016-11-28 at 13:39.","DSpace SAF Submission Ingestion Package generated from Vireo submission #10308 on 2017-02-28 at 14:52:38","Made available in DSpace on 2017-03-01T15:49:08Z (GMT). No. of bitstreams: 2 CULLINA-DISSERTATION-2016.pdf: 588682 bytes, checksum: 75dfab2a1da71d31d6ba8ffbb6d43056 (MD5) LICENSE.txt: 4211 bytes, checksum: 33e797f5d6ec173f1b9a7c8c922f70fd (MD5) Previous issue date: 2016-11-28"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Combinatorial channels from partially ordered sets"]}]}],"canonical_facts":{"dc:contributor":["Kiyavash, Negar","Barg, Alexander","Hajek, Bruce","Milenkovic, Olgica","Srikant, R."],"dc:creator":["Cullina, Daniel Francis"],"dc:date":["2017-03-01T15:49:08Z","2016-11-28","2016-12"],"dc:description":["A central task of coding theory is the design of schemes to reliably transmit data though space, via communication systems, or through time, via storage systems. Our goal is to identify and exploit structural properties common to a wide variety of coding problems, classical and modern, using the framework of partially ordered sets. We represent adversarial error models as combinatorial channels, form combinatorial channels from posets, identify a structural property of posets that leads to families of channels with the same codes, and bound the size of codes by optimizing over a family of equivalent channels. A large number of previously studied coding problems that fit into this framework. This leads to a new upper bound on the size of s-deletion correcting codes. We use a linear programming framework to obtain sphere-packing upper bounds when there is little underlying symmetry in the coding problem. Finally, we introduce and investigate a strong notion of poset homomorphism: locally bijective cover preserving maps. We look for maps of this type to and from the subsequence partial order on q-ary strings.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2017-02-28 without embargo terms","The student, Daniel Cullina, accepted the attached license on 2016-11-23 at 09:35.","The student, Daniel Cullina, submitted this Dissertation for approval on 2016-11-23 at 09:41.","This Dissertation was approved for publication on 2016-11-28 at 13:39.","DSpace SAF Submission Ingestion Package generated from Vireo submission #10308 on 2017-02-28 at 14:52:38","Made available in DSpace on 2017-03-01T15:49:08Z (GMT). No. of bitstreams: 2 CULLINA-DISSERTATION-2016.pdf: 588682 bytes, checksum: 75dfab2a1da71d31d6ba8ffbb6d43056 (MD5) LICENSE.txt: 4211 bytes, checksum: 33e797f5d6ec173f1b9a7c8c922f70fd (MD5) Previous issue date: 2016-11-28"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/95346"],"dc:language":["en"],"dc:rights":["Copyright 2016 Daniel Cullina"],"dc:subject":["coding theory","combinatorics, partially ordered set","deletion errors"],"dc:title":["Combinatorial channels from partially ordered sets"],"dc:type":["text"],"thesis:degree_discipline":["Electrical & Computer Engr"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:26:37Z"}