FROM SEARCH TO CODING (AND BACK): TWO SIDES OF THE SAME COIN

THIS THESIS INVESTIGATES THE DEEP CONNECTION BETWEEN DETERMINISTIC SEARCH PROCEDURES AND VARIABLE-LENGTH CODES, SHOWING THAT THESE TWO DOMAINS—TRADITIONALLY TREATED AS DISTINCT—ARE FUNDAMENTALLY EQUIVALENT. ANY SEARCH ALGORITHM BASED ON MEMBERSHIP OR COMPARISON QUERIES NATURALLY INDUCES A BINARY VARIABLE-LENGTH CODE, AND CONVERSELY, EVERY VARIABLE-LENGTH CODE IMPLICITLY REPRESENTS A SEARCH STRATEGY. THIS CORRESPONDENCE ALLOWS CLASSICAL SEARCH PROBLEMS TO BE REFORMULATED THROUGH THE MATHEMATICAL LANGUAGE OF CODING THEORY AND ANALYZED USING TOOLS FROM INFORMATION THEORY. WITHIN THIS FRAMEWORK, THE THESIS INVESTIGATES SEVERAL FAMILIES OF ALPHABETIC AND PREFIX CODES ARISING FROM DIFFERENT STRUCTURAL OR COST CONSTRAINTS. FIRST, IT ESTABLISHES NEW AND TIGHTER UPPER BOUNDS FOR OPTIMAL ALPHABETIC CODES AND INTRODUCES LINEAR-TIME ALGORITHMS THAT ACHIEVE THEM, YIELDING IMPROVED BOUNDS FOR \AC{BSTS} AS WELL. SECOND, IT PROPOSES AND ANALYZES A NOVEL CLASS OF CODES MOTIVATED BY SEARCH PROBLEMS WITH ASYMMETRIC TEST OUTCOME COSTS, AND PROVIDES POLYNOMIAL-TIME ALGORITHMS FOR THEIR CONSTRUCTION. THIRD, IT STUDIES PREFIX CODES THAT USE A SYMBOL ONLY AS A TERMINATION CHARACTER, DERIVING LINEAR-TIME NEAR-OPTIMAL CONSTRUCTION METHODS AND NEW ENTROPIC BOUNDS. MOREOVER, IT EXPLICITLY CONNECTS THESE CODES TO SEARCH PROCEDURES USING COMPARISON AND EQUALITY TESTS. OVERALL, THE THESIS SHOWS THAT SEARCH CAN BE UNDERSTOOD AS AN ACT OF COMPRESSION: EFFICIENT INFORMATION ACQUISITION AND EFFICIENT INFORMATION REPRESENTATION ARE GOVERNED BY THE SAME PRINCIPLE OF MINIMIZING UNCERTAINTY. THIS PERSPECTIVE PROVIDES A POWERFUL, GENERAL METHODOLOGY FOR TRANSLATING SEARCH PROBLEMS INTO CODE PROBLEMS.