Show simple item record

dc.contributor.authorDanielsen, Lars Eirikeng
dc.date.accessioned2009-02-23T12:04:47Z
dc.date.available2009-02-23T12:04:47Z
dc.date.issued2008-05-28eng
dc.identifier.isbn978-82-308-0573-2 (print version)en_US
dc.identifier.urihttps://hdl.handle.net/1956/3162
dc.description.abstractWe study objects that can be represented as graphs, error-correcting codes, quantum states, or Boolean functions. It is known that self-dual additive codes, which can also be interpreted as quantum states, can be represented as graphs, and that two codes are equivalent when the corresponding graphs are equivalent with respect to local complementation (LC). We give classifications of such codes. Circulant graph codes are introduced, and it is shown that some of these codes have highly regular graph representations. We show that the orbit of a bipartite graph under edge local complementation (ELC) corresponds to the equivalence class of a binary linear code. We classify ELC orbits, give a new method for classifying binary linear codes, and show that the information sets and the minimum distance of a code can be derived from the corresponding ELC orbit. Self-dual additive codes over GF(4) can also be interpreted as quadratic Boolean functions. In this context we define PARIHN, peak-to-average power ratio with respect to the {I, H, N}n transform, and prove that PARIHN equals the size of the maximum independent set over the associated LC orbit of graphs. We define the aperiodic propagation criteria (APC) of a Boolean function, and show that it is related to the minimum distance of a self-dual additive code over GF(4), and to the degree of entanglement in the associated quantum state. We give a generalization to non-quadratic Boolean functions, and relate APC to known cryptographic criteria. Interlace polynomials encode many properties of the LC and ELC orbits of a graph. We enumerate interlace polynomials and circle graphs, show that there exist non-unimodal interlace polynomials, and relate properties of interlace polynomials to properties of codes and quantum states. We define self-dual bent functions, and provide constructions and classifications.en_US
dc.language.isoengeng
dc.publisherThe University of Bergenen_US
dc.relation.haspartPaper I: Danielsen, Lars Eirik; Parker, Matthew G., On the Classification of All Self-Dual Additive Codes over GF (4) of Length up to 12. Authors peer-reviewed version. Published in Journal of Combinatorial Theory, Series A 113(7): 1351-1367. Copyright 2006 Elsevier. The published version is available at: <a href="http://dx.doi.org/10.1016/j.jcta.2005.12.004" target="blank">http://dx.doi.org/10.1016/j.jcta.2005.12.004</a>en_US
dc.relation.haspartPaper II: Danielsen, Lars Eirik, Graph-Based Classification of Self-Dual Additive Codes over Finite Fields. Authors preprint version. Published in Advances in Mathematics 3(4): 329–348. Copyright 2009 American Institute of Mathematical Sciences. The published version is available at: <a href="http://dx.doi.org/10.3934/amc.2009.3.329" target="blank">http://dx.doi.org/10.3934/amc.2009.3.329</a>en_US
dc.relation.haspartPaper III: Danielsen, Lars Eirik; Parker, Matthew G., Edge Local Complementation and Equivalence of Binary Linear Codes. Authors preprint version. Published in Designs, Codes and Cryptography 49(1-3): 161-170. Copyright 2008 Springer. The published version is available at: <a href="http://dx.doi.org/10.1007/s10623-008-9190-x" target="blank">http://dx.doi.org/10.1007/s10623-008-9190-x</a>en_US
dc.relation.haspartPaper IV: Danielsen, Lars Eirik; Parker, Matthew G., Spectral Orbits and Peak-to-Average Power Ratio of Boolean Functions with Respect to the {I, H, N}n Transform 95. Authors peer-reviewed version. Published as a book chapter in Lecture Notes in Computer Science 3486/2005: 373-388. Copyright 2005 Springer. The published version is available at: <a href="http://dx.doi.org/10.1007/11423461_28" target="blank">http://dx.doi.org/10.1007/11423461_28</a>en_US
dc.relation.haspartPaper V: Information and Computation 204(5), Danielsen, Lars Eirik; Gulliver, T. Aaron; Parker, Matthew G., Aperiodic Propagation Criteria for Boolean Functions, pp. 741-770. Authors peer-reviewed version. Copyright 2006 Elsevier. The published version is available at: <a href="http://dx.doi.org/10.1016/j.ic.2006.01.004" target="blank">http://dx.doi.org/10.1016/j.ic.2006.01.004</a>en_US
dc.relation.haspartPaper VI: Discrete Applied Mathematics Volume 158(6), B, Danielsen, Lars Eirik; Parker, Matthew G., Interlace Polynomials: Classification, Unimodality, and Connections to Codes, pp. 636-648. Authors preprint version. Copyright © 2009 Elsevier B.V. All rights reserved. The published version is available at: <a href="http://dx.doi.org/10.1016/j.dam.2009.11.011" target="blank">http://dx.doi.org/10.1016/j.dam.2009.11.011</a>en_US
dc.relation.haspartPaper VII: Carlet, Claude; Danielsen, Lars Eirik; Parker, Matthew G.; Solé, Patrick, Self-Dual Bent Functions. Authors preprint version. Copyright 2008 the authors.en_US
dc.titleOn Connections Between Graphs, Codes, Quantum States, and Boolean Functionsen_US
dc.typeDoctoral thesis
dc.subject.nsiVDP::Matematikk og Naturvitenskap: 400::Informasjons- og kommunikasjonsvitenskap: 420nob


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record