Encoding Arguments
Public Deposited- Resource Type
- Creator
- Abstract
We study encoding arguments using partial prefix-free codes, which allow us to prove probabilistic statements using the basic fact that uniformly chosen elements from a set of size n cannot be encoded with fewer than log_2 n bits on average. This technique, in the end, is a more direct version of the incompressibility method from the study of Kolmogorov complexity. We use our technique to produce short original proofs for several results. We also explore extensions of the technique to non-uniform input distributions. Finally, we offer a new manner of encoding which allows for real-valued codeword lengths, thereby refining every other result obtained through encoding.
- Subject
- Language
- Publisher
- Thesis Degree Level
- Thesis Degree Name
- Thesis Degree Discipline
- Identifier
- Rights Notes
Copyright © 2016 the author(s). Theses may be used for non-commercial research, educational, or related academic purposes only. Such uses include personal study, research, scholarship, and teaching. Theses may only be shared by linking to Carleton University Institutional Repository and no part may be used without proper attribution to the author. No part may be used for commercial purposes directly or indirectly via a for-profit platform; no adaptation or derivative works are permitted without consent from the copyright owner.
- Date Created
- 2016
Relations
- In Collection:
Items
Thumbnail | Title | Date Uploaded | Visibility | Actions |
---|---|---|---|---|
reddad-encodingarguments.pdf | 2023-05-04 | Public | Download |