Asymptotic Solutions to Problems Arising in Computer Science and Information Theory

University Of Illinois At Chicago, Chicago IL

Investigators

Abstract

Knessl 0202815 The investigator, together with colleagues and students, studies a variety of problems in computer science, information theory, and applied probability. These have the common feature that they can be reduced to solving recursion or differential equations. Sometimes these equations can be solved exactly using transform methods. Then one can obtain asymptotic information by expanding the results using methods such as the Laplace or saddle point methods, the Euler-Maclaurin and Poisson summation formulas, Watson transformations, etc. Many applied problems of interest (especially nonlinear ones) cannot be solved exactly. For these the investigator and colleagues develop appropriate asymptotic techniques that analyze directly the governing equations. These are variants of applied mathematics methods, such as WKB expansions and matched asymptotic expansions. The latter are especially useful for asymptotic problems that involve several different scales. The focus is on problems in combinatorics, data compression, analysis of algorithms, digital and binary trees, queuing, and coding. Computers play a progressively greater role in all of our lives. Important problems in computer science include sorting and searching, efficient data storage, and data compression. To decide on what is a good method to search out a given item in some database, or a good method for storing music or video with minimal use of memory, it is important to analyze the method or algorithm. For example, one might ask for the average search time, or for the likelihood that the search time will be very long, exceeding some prescribed tolerance. Such questions involve the "analysis of algorithms." They can frequently be reduced to solving certain classes of equations. The investigator and colleagues develop mathematical tools for obtaining solutions of these equations, either exact ones or accurate approximations. Approximations are often sufficient, because for example the searching problem is most important if the total number of items stored is very large. This "largeness" shows up as a parameter in the governing equation that facilitates its solution. Related mathematical problems arise in other important areas such as molecular biology and communications, and the investigators' methods and results should thus find applicability to a wide range of problems.