Probabilistic Binning Transforms with Applications to Computer Science and Coding Theory

Speaker: Olgica Milenkovic, University of Colorado, BoulderAbstract: Binning schemes are important combinatorial models used for studying problems arising in biology, financial market analysis, engineering, communication theory, and computer science. When analyzing random binning schemes, it is usually of interest to evaluate some statistics that depends on the characteristics of the distribution of objects (balls) into bins. Due to the inherent mutual dependence of the variables describing the occupancy of the bins, determining the statistics of interest may represent a challenging mathematical task. Often, asymptotic approximation techniques are used instead of a complicated - and usually intractable - exact analysis.We describe a class of invertible probabilistic transforms that result in mapping dependent bin occupancies into independent random variables. When using these transforms, certain statistics of interest can be evaluated in the transform domain and afterwards appropriately inverted to obtain exact expressions. Or, for problems with large parameter sizes, the behavior of the statistics can be deduced directly from the result in the transform domain by referring to a new class of Tauberian theorems. We demonstrate the application of the transform techniques on examples taken from theoretical computer science (finding closed form expressions for combinatorial sums), coding theory (analyzing raptor codes), and bioinformatics (demonstrating the non-randomness of certain repeats in DNA sequences).This is a joint work with Kevin Compton from the University of Michigan, Ann Arbor.Biography: Olgica Milenkovic received her MS degree in mathematics and PhD in electrical engineering from the University of Michigan, Ann Arbor, in 2001 and 2002, respectively. In August 2002, she joined the University of Colorado, Boulder, where she is an Assistant Professor in the Department of Electrical and Computer Engineering. In the summer of 2005, she was a Discrete Mathematics and Theoretical Computer Science (DIMACS) Visitor at Bell Labs, Lucent Technologies. Currently, she is a Visiting Professor at the Center for Information Theory and Applications at the University of California, San Diego. Her research interests include error-control and constrained coding, analysis of algorithms, combinatorics, probability theory, and bioinformatics. For the research on these subjects, she received the NSF Career Award and the DARPA Young Faculty Award.Host: Keith Chugg, chugg@usc.edu

Location: Hughes Aircraft Electrical Engineering Center (EEB) - 248

Audiences: Everyone Is Invited

Contact: Gerrielyn Ramos