Encoding Arguments

It appears your Web browser is not configured to display PDF files. Download adobe Acrobat or click here to download the PDF file.

Click here to download the PDF file.

Creator: 

Reddad, Tommy

Date: 

2016

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: 

Computer Science
Mathematics

Language: 

English

Publisher: 

Carleton University

Thesis Degree Name: 

Master of Computer Science: 
M.C.S.

Thesis Degree Level: 

Master's

Thesis Degree Discipline: 

Computer Science

Parent Collection: 

Theses and Dissertations

Items in CURVE are protected by copyright, with all rights reserved, unless otherwise indicated. They are made available with permission from the author(s).