Polynomial Time Algorithm for Constructing Optimal Binary AIFV-m Codes

The Hong Kong University of Science and Technology
Department of Computer Science and Engineering

Final Year Thesis Oral Defense

Title: "Polynomial Time Algorithm for Constructing Optimal Binary AIFV-m 
        Codes"

By

PATUPAT Albert John Lalim

Abstract:

Binary Almost-Instantaneous Fixed-to-Variable-length m-bit-delay codes 
(binary AIFV-m codes) generalize prefix-free binary codes by allowing at 
most m code trees and at most m bits of delay in the decoding process. It 
has been proven that optimal binary AIFV-m codes provide better worst-case 
redundancy than optimal prefix-free binary codes, such as the well-known 
Huffman codes.

However, constructing optimal binary AIFV-m codes on n source symbols is a 
difficult problem; the known approaches split the task into two subtasks - 
local optimization and global optimization - and yield exponential-time 
algorithms. Improving on this approach, this FYT presents the first-ever 
polynomial-time algorithm for constructing optimal binary AIFV-m codes. 
The running time of local optimization was improved from O(n^(2m+1)) to 
O(n^(m+2)) by applying dynamic programming that is, unusually, based on 
asymmetric operations. On the other hand, the running time of global 
optimization was improved from exponential-time to polynomial-time by 
translating the problem into convex optimization in (m-1)-dimensional 
Euclidean space.

The novel techniques introduced in this theoretical work might be 
applicable to similar problems, such as optimization of binary search 
trees and constrained Markov chains.

Date            : 5 May 2022 (Thursday)

Time            : 09:40-10:20

Zoom Link:
https://hkust.zoom.us/j/93306848754?pwd=UmEvZWFXSnFBMDdyTHhyVHpQQkx0UT09

Meeting ID      : 933 0684 8754

Passcode        : 571821

Advisor         : Prof. GOLIN Mordecai J.

2nd Reader      : Prof. ARYA Sunil