Upcoming Seminars by Szpankowski
Seminar I: Is the Internet Fractal? The Multicast Power Law RevisitedSeminar II: Combinatorial Patter Matching Problems
Presenter: Wojciech Szpankowski, Professor, Department of Computer Science, Purdue University
Host: Alon Orlitsky, Professor, Department of Electrical and Computer Engineering, UC San Diego - contact Alon Orlitsky through Lori Unruh at lunruh@soe.ucsd.edu.
Date: Tuesday, August 13, 2002
Time: Seminar I - 11:00 AM, Seminar II - 2:30 PM
Location: CMRR Auditorium, UC San Diego Campus, La Jolla, CA [Directions] [Parking Information]
Abstract for Seminar I
Is the Internet Fractal? The Multicast Power Law Revisited
One of the main benefits of multicast communication is the overall reduction of network load. To quantify this reduction, when compared to traditional unicast, experimental studies by Chuang and Sirbu indicated the so called power law which asserts that the number of links L(n) in a multicast delivery tree connecting a source to n sites satisfies a power law, that is, L(n) grows approximately as n to the power 0.8. In order to explain theoretically this behavior, Phillips, Shenker, and Tangmunarunkit examined approximately L(n) for a V-ary complete tree topology, and concluded that it grows nearly linearly with n. In this talk, we first re-examine their analysis and provide precise asymptotic expansion for L(n) that confirms the nearly linear (with some wobbling) growth. We then claim that the essence of the problem lies in the modeling assumptions, and replace the V-ary complete tree topology by a self-similar tree. In such a tree a node at level k is replicated proportionally to the number of leaves reached through this node with the scaling factor t. Under this assumption, we analyze again L(n) and prove that it satisfies a power law with the exponent 1-t. We also examine more general conditions for general trees, under which the power law still holds. We also discuss some experimental results in real networks that reaffirm the power law and show that in these networks the general conditions hold. In particular, we experimentally establish that for the studied network t=0.12. Our theoretical findings have been established by analytical techniques of the precise analysis of algorithms such as Mellin transform and complex asymptotics. **Joint work with C. Adjih (INRIA, France), L. Georgiadis (U. Thessaloniki,Greece) and P. Jacquet (INRIA, France).**
Abstract for Seminar II
Combinatorial Patter Matching Problems
Let H be a pattern and T be a text generated over a finite alphabet. Two basic problems in combinatorial pattern matching are: (i) how many times does H occur in T; and (ii) how long does one have to wait until H occurs in T. We consider pattern matching in various settings: (1) In the string matching problem the pattern H is considered to be a string (consisting of consecutive symbols), while in the subsequence matching problem the pattern H is a subsequence; (2) Exact or approximate occurrences of pattern H; (3) The text is assumed to be generated by a random source while the pattern is given, except in the repetitive pattern matching problem, where we assume that the pattern is part of the text; and (4) In the restricted pattern matching problem we assume that the text satisfies some additional constraints (e.g., in (d,k) sequences there are no runs of 0's shorter than d and longer than k). In this talk we review analyses of these pattern matching problems. We show how to compute moments, limiting distributions and large deviations for the number of pattern occurrences and the waiting time (i.e., the first occurrence of the pattern), as well as the Shannon capacity of $(d,k)$ sequences. Throughout, we use combinatorial (e.g., formal calculus) and analytic methods (e.g., generating function, singularity analysis, Mellin transform, saddle point method) of analysis of algorithms.
Bio: W. Szpankowski is a Professor in the Department of Computer Science at Purdue University. Before coming to Purdue, Professor Szpankowski was Assistant Professor at the Technical University of Gdansk, and in 1984 he was Assistant Professor at the McGill University, Montreal. During 1992/1993 he was Professeur Invité at INRIA, Rocquencourt, France. His research interests cover analysis of algorithms, data compression, information theory, analytic combinatorics, random structures, networking, stability problems in distributed systems, modeling of computer systems and computer communication networks, queuing theory, and operations research. His recent work is devoted to the probabilistic analysis of algorithms on words, analytic information theory, and designing efficient multimedia data compression schemes based on approximate pattern matching. He is a recipient of the Humboldt Fellowship. He has been guest editors for special issues in IEEE Transactions on Automatic Control, Theoretical Computer Science, Random Structures & Algorithms, and Algorithmica. Currently, he is editing a special issue on "Analysis of Algorithms" in Algorithmica. He serves on the editorial boards of Theoretical Computer Science, Discrete Mathematics and Theoretical Computer Science, and book series Advances in the Theory of Computation and Computational Mathematics.